Home(or GIF version for IE).
| Home |
Metamath Proof Explorer | < Wrap Next > |
| Bad symbols?
Use Firefox (or GIF version for IE). |
| Color key: | Metamath Proof Explorer
(1-8729)
|
Hilbert Space Explorer
(8730-10658)
|
| Type | Label | Description |
|---|---|---|
| Statement | ||
| Pre-logic | ||
| Dummy link theorem for assisting proof development | ||
| Theorem | dummylink 1 |
(Note: This theorem will never appear in a completed proof and can be
ignored if you are using this database to learn logic - please start
with the next statement, wn 2.)
This is a technical theorem to assist proof development. It provides a temporary way to add an independent subproof to a proof under development, for later assignment to a normal proof step. The Metamath program's Proof Assistant requires proofs to be developed backwards from the conclusion with no gaps, and it has no mechanism that lets the user to work on isolated subproofs. This theorem provides a workaround for this limitation. It can be inserted at any point in a proof to allow an independent subproof to be developed on the side, for later use as part of the final proof. Instructions: (1) Assign this theorem to any unknown step in the proof. Typically, the last unknown step is the most convenient, since 'assign last' can be used. This step will be replicated in hypothesis dummylink.1, from where the development of the main proof can continue. (2) Develop the independent subproof backwards from hypothesis dummylink.2. If desired, use a 'let' command to pre-assign the conclusion of the independent subproof to dummylink.2. (3) Later on, use 'improve all' to assign the independent subproof to an unknown step in the main proof that matches it. (4) After the entire proof is complete, use 'minimize */n/b/e 3syl,we?,wsb' to clean up (discard) all dummylink references automatically. This theorem was originally designed to assist importing partially completed Proof Worksheets from Mel O'Cat's mmj2 Proof Assistant GUI, but it can also be useful on its own. Interestingly, this "theorem" - or more precisely, inference - requires no axioms for its proof. |
| ⊢ φ & ⊢ ψ ⇒ ⊢ φ | ||
| Propositional calculus | ||
| Recursively define primitive wffs for propositional calculus | ||
| Syntax | wn 2 | If φ is a wff, so is ¬ φ or "not φ." Part of the recursive definition of a wff (well-formed formula). In classical logic (which is our logic), a wff is interpreted as either true or false. So if φ is true, then ¬ φ is false; if φ is false, then ¬ φ is true. Traditionally, Greek letters are used to represent wffs, and we follow this convention. In propositional calculus, we define only wffs built up from other wffs, i.e. there is no starting or "atomic" wff. Later, in predicate calculus, we will extend the basic wff definition by including atomic wffs (weq 955 and wel 957). |
| wff ¬ φ | ||
| Syntax | wi 3 | If φ and ψ are wff's, so is (φ → ψ) or "φ implies ψ." Part of the recursive definition of a wff. The resulting wff is (interpreted as) false when φ is true and ψ is false; it is true otherwise. (Think of the truth table for an OR gate with input φ connected through an inverter.) The left-hand wff is called the antecedent, and the right-hand wff is called the consequent. In the case of (φ → (ψ → χ)), the middle ψ may be informally called either an antecedent or part of the consequent depending on context. |
| wff (φ → ψ) | ||
| The axioms of propositional calculus | ||
| Axiom | ax-1 4 |
Axiom Simp. Axiom A1 of [Margaris] p.
49. One of the 3 axioms of
propositional calculus. The 3 axioms are also given as Definition 2.1
of [Hamilton] p. 28. This axiom is
called Simp or "the principle of
simplification" in Principia Mathematica (Theorem *2.02 of
[WhiteheadRussell] p. 100)
because "it enables us to pass from the joint
assertion of φ and ψ to the assertion of φ simply."
General remarks: Propositional calculus (axioms ax-1 4 through ax-3 6 and rule ax-mp 7) can be thought of as asserting formulas that are universally "true" when their variables are replaced by any combination of "true" and "false." Propositional calculus was first formalized by Frege in 1879, using as his axioms (in addition to rule ax-mp 7) the wffs ax-1 4, ax-2 5, pm2.04 30, con3 94, nega 84, and negb 86. Around 1930, Lukasiewicz simplified the system by eliminating the third (which follows from the first two, as you can see by looking at the proof of pm2.04 30) and replacing the last three with our ax-3 6. (Thanks to Ted Ulrich for this information.) The theorems of propositional calculus are also called tautologies. Tautologies can be proved very simply using truth tables, based on the true/false interpretation of propositional calculus. To do this, we assign all possible combinations of true and false to the wff variables and verify that the result (using the rules described in wi 3 and wn 2) always evaluates to true. This is called the semantic approach. Our approach is called the syntactic approach, in which everything is derived from axioms. A metatheorem called the Completeness Theorem for Propositional Calculus shows that the two approaches are equivalent and even provides an algorithm for automatically generating syntactic proofs from a truth table. Those proofs, however, tend to be long, and the much shorter proofs that we show here were found manually. Truth tables grow exponentially with the number of variables, but it is unknown if the same is true of proofs - an answer to this would resolve the P=NP conjecture in complexity theory. |
| ⊢ (φ → (ψ → φ)) | ||
| Axiom | ax-2 5 | Axiom Frege. Axiom A2 of [Margaris] p. 49. One of the 3 axioms of propositional calculus. It "distributes" an antecedent over two consequents. This axiom was part of Frege's original system and is known as Frege in the literature. It is also proved as Theorem *2.77 of [WhiteheadRussell] p. 108. The other direction of this axiom also turns out to be true, as demonstrated by pm5.41 169. |
| ⊢ ((φ → (ψ → χ)) → ((φ → ψ) → (φ → χ))) | ||
| Axiom | ax-3 6 | Axiom Transp. Axiom A3 of [Margaris] p. 49. One of the 3 axioms of propositional calculus. It swaps or "transposes" the order of the consequents when negation is removed. An informal example is that the statement "if there are no clouds in the sky, it is not raining" implies the statement "if it is raining, there are clouds in the sky." This axiom is called Transp or "the principle of transposition" in Principia Mathematica (Theorem *2.17 of [WhiteheadRussell] p. 103). We will also use the term "contraposition" for this principle, although the reader is advised that in the field of philosophical logic, "contraposition" has a different technical meaning. |
| ⊢ ((¬ φ → ¬ ψ) → (ψ → φ)) | ||
| Axiom | ax-mp 7 | Rule of Modus Ponens. The postulated inference rule of propositional calculus. See e.g. Rule 1 of [Hamilton] p. 73. The rule says, "if φ is true, and φ implies ψ, then ψ must also be true." This rule is sometimes called "detachment," since it detaches the minor premise from the major premise. |
| ⊢ φ & ⊢ (φ → ψ) ⇒ ⊢ ψ | ||
| Logical implication | ||
| Theorem | a1i 8 | Inference derived from axiom ax-1 4. See a1d 12 for an explanation of our informal use of the terms "inference" and "deduction." |
| ⊢ φ ⇒ ⊢ (ψ → φ) | ||
| Theorem | a2i 9 | Inference derived from axiom ax-2 5. |
| ⊢ (φ → (ψ → χ)) ⇒ ⊢ ((φ → ψ) → (φ → χ)) | ||
| Theorem | syl 10 |
An inference version of the transitive laws for implication imim2 14
and
imim1 15, which Russell and Whitehead call "the
principle of the
syllogism...because...the syllogism in Barbara is derived from
them"
(quote after Theorem *2.06 of [WhiteheadRussell] p. 101). Some authors
call this law a "hypothetical syllogism."
(A bit of trivia: this is the most commonly referenced assertion in our database. In second place is ax-mp 7, followed by visset 1809, bitr 173, imp 350, and ex 373. The Metamath program command 'show usage' shows the number of references.) |
| ⊢ (φ → ψ) & ⊢ (ψ → χ) ⇒ ⊢ (φ → χ) | ||
| Theorem | com12 11 | Inference that swaps (commutes) antecedents in an implication. |
| ⊢ (φ → (ψ → χ)) ⇒ ⊢ (ψ → (φ → χ)) | ||
| Theorem | a1d 12 |
Deduction introducing an embedded antecedent. (The proof was revised by
Stefan Allan, 20-Mar-2006.)
Naming convention: We often call a theorem a "deduction" and suffix its label with "d" whenever the hypotheses and conclusion are each prefixed with the same antecedent. This allows us to use the theorem in places where (in traditional textbook formalizations) the standard Deduction Theorem would be used; here φ would be replaced with a conjunction (df-an 225) of the hypotheses of the would-be deduction. By contrast, we tend to call the simpler version with no common antecedent an "inference" and suffix its label with "i"; compare theorem a1i 8. Finally, a "theorem" would be the form with no hypotheses; in this case the "theorem" form would be the original axiom ax-1 4. In propositional calculus we usually prove the theorem form first without a suffix on its label (e.g. pm2.43 63 vs. pm2.43i 64 vs. pm2.43d 65), but (much) later we often suffix the theorem form's label with "t" as in negnegt 5374 vs. negneg 5371, especially when our "weak deduction theorem" dedth 2379 is used to prove the theorem form from its inference form. When an inference is converted to a theorem by eliminating an "is a set" hypothesis, we sometimes suffix the theorem form with "g" (for somewhat overstated "generalized") as in uniex 2865 vs. uniexg 2866. |
| ⊢ (φ → ψ) ⇒ ⊢ (φ → (χ → ψ)) | ||
| Theorem | a2d 13 | Deduction distributing an embedded antecedent. |
| ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (φ → ((ψ → χ) → (ψ → θ))) | ||
| Theorem | imim2 14 | A closed form of syllogism (see syl 10). Theorem *2.05 of [WhiteheadRussell] p. 100. |
| ⊢ ((φ → ψ) → ((χ → φ) → (χ → ψ))) | ||
| Theorem | imim1 15 | A closed form of syllogism (see syl 10). Theorem *2.06 of [WhiteheadRussell] p. 100. |
| ⊢ ((φ → ψ) → ((ψ → χ) → (φ → χ))) | ||
| Theorem | imim1i 16 | Inference adding common consequents in an implication, thereby interchanging the original antecedent and consequent. |
| ⊢ (φ → ψ) ⇒ ⊢ ((ψ → χ) → (φ → χ)) | ||
| Theorem | imim2i 17 | Inference adding common antecedents in an implication. |
| ⊢ (φ → ψ) ⇒ ⊢ ((χ → φ) → (χ → ψ)) | ||
| Theorem | imim12i 18 | Inference joining two implications. |
| ⊢ (φ → ψ) & ⊢ (χ → θ) ⇒ ⊢ ((ψ → χ) → (φ → θ)) | ||
| Theorem | imim3i 19 | Inference adding three nested antecedents. |
| ⊢ (φ → (ψ → χ)) ⇒ ⊢ ((θ → φ) → ((θ → ψ) → (θ → χ))) | ||
| Theorem | 3syl 20 | Inference chaining two syllogisms. |
| ⊢ (φ → ψ) & ⊢ (ψ → χ) & ⊢ (χ → θ) ⇒ ⊢ (φ → θ) | ||
| Theorem | syl5 21 | A syllogism rule of inference. The second premise is used to replace the second antecedent of the first premise. |
| ⊢ (φ → (ψ → χ)) & ⊢ (θ → ψ) ⇒ ⊢ (φ → (θ → χ)) | ||
| Theorem | syl6 22 | A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. |
| ⊢ (φ → (ψ → χ)) & ⊢ (χ → θ) ⇒ ⊢ (φ → (ψ → θ)) | ||
| Theorem | syl7 23 | A syllogism rule of inference. The second premise is used to replace the third antecedent of the first premise. |
| ⊢ (φ → (ψ → (χ → θ))) & ⊢ (τ → χ) ⇒ ⊢ (φ → (ψ → (τ → θ))) | ||
| Theorem | syl8 24 | A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. |
| ⊢ (φ → (ψ → (χ → θ))) & ⊢ (θ → τ) ⇒ ⊢ (φ → (ψ → (χ → τ))) | ||
| Theorem | imim2d 25 | Deduction adding nested antecedents. |
| ⊢ (φ → (ψ → χ)) ⇒ ⊢ (φ → ((θ → ψ) → (θ → χ))) | ||
| Theorem | mpd 26 | A modus ponens deduction. |
| ⊢ (φ → ψ) & ⊢ (φ → (ψ → χ)) ⇒ ⊢ (φ → χ) | ||
| Theorem | syld 27 | Syllogism deduction. (The proof was shortened by O'Cat, 19-Feb-2008. |
| ⊢ (φ → (ψ → χ)) & ⊢ (φ → (χ → θ)) ⇒ ⊢ (φ → (ψ → θ)) | ||
| Theorem | imim1d 28 | Deduction adding nested consequents. |
| ⊢ (φ → (ψ → χ)) ⇒ ⊢ (φ → ((χ → θ) → (ψ → θ))) | ||
| Theorem | imim12d 29 | Deduction combining antecedents and consequents. |
| ⊢ (φ → (ψ → χ)) & ⊢ (φ → (θ → τ)) ⇒ ⊢ (φ → ((χ → θ) → (ψ → τ))) | ||
| Theorem | pm2.04 30 | Swap antecedents. Theorem *2.04 of [WhiteheadRussell] p. 100. |
| ⊢ ((φ → (ψ → χ)) → (ψ → (φ → χ))) | ||
| Theorem | pm2.83 31 | Theorem *2.83 of [WhiteheadRussell] p. 108. |
| ⊢ ((φ → (ψ → χ)) → ((φ → (χ → θ)) → (φ → (ψ → θ)))) | ||
| Theorem | com23 32 | Commutation of antecedents. Swap 2nd and 3rd. |
| ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (φ → (χ → (ψ → θ))) | ||
| Theorem | com13 33 | Commutation of antecedents. Swap 1st and 3rd. |
| ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (χ → (ψ → (φ → θ))) | ||
| Theorem | com3l 34 | Commutation of antecedents. Rotate left. |
| ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (ψ → (χ → (φ → θ))) | ||
| Theorem | com3r 35 | Commutation of antecedents. Rotate right. |
| ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (χ → (φ → (ψ → θ))) | ||
| Theorem | com34 36 | Commutation of antecedents. Swap 3rd and 4th. |
| ⊢ (φ → (ψ → (χ → (θ → τ)))) ⇒ ⊢ (φ → (ψ → (θ → (χ → τ)))) | ||
| Theorem | com24 37 | Commutation of antecedents. Swap 2nd and 4th. |
| ⊢ (φ → (ψ → (χ → (θ → τ)))) ⇒ ⊢ (φ → (θ → (χ → (ψ → τ)))) | ||
| Theorem | com14 38 | Commutation of antecedents. Swap 1st and 4th. |
| ⊢ (φ → (ψ → (χ → (θ → τ)))) ⇒ ⊢ (θ → (ψ → (χ → (φ → τ)))) | ||
| Theorem | com4l 39 | Commutation of antecedents. Rotate left. (The proof was shortened by O'Cat, 15-Aug-2004.) |
| ⊢ (φ → (ψ → (χ → (θ → τ)))) ⇒ ⊢ (ψ → (χ → (θ → (φ → τ)))) | ||
| Theorem | com4t 40 | Commutation of antecedents. Rotate twice. |
| ⊢ (φ → (ψ → (χ → (θ → τ)))) ⇒ ⊢ (χ → (θ → (φ → (ψ → τ)))) | ||
| Theorem | com4r 41 | Commutation of antecedents. Rotate right. |
| ⊢ (φ → (ψ → (χ → (θ → τ)))) ⇒ ⊢ (θ → (φ → (ψ → (χ → τ)))) | ||
| Theorem | a1dd 42 | Deduction introducing a nested embedded antecedent. (The proof was shortened by O'Cat, 15-Jan-2008.) |
| ⊢ (φ → (ψ → χ)) ⇒ ⊢ (φ → (ψ → (θ → χ))) | ||
| Theorem | mp2 43 | A double modus ponens inference. |
| ⊢ φ & ⊢ ψ & ⊢ (φ → (ψ → χ)) ⇒ ⊢ χ | ||
| Theorem | mpi 44 | A nested modus ponens inference. (The proof was shortened by Stefan Allan, 20-Mar-2006. |
| ⊢ ψ & ⊢ (φ → (ψ → χ)) ⇒ ⊢ (φ → χ) | ||
| Theorem | mpii 45 | A doubly nested modus ponens inference. |
| ⊢ χ & ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (φ → (ψ → θ)) | ||
| Theorem | mpdd 46 | A nested modus ponens deduction. |
| ⊢ (φ → (ψ → χ)) & ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (φ → (ψ → θ)) | ||
| Theorem | mpid 47 | A nested modus ponens deduction. |
| ⊢ (φ → χ) & ⊢ (φ → (ψ → (χ → θ))) ⇒ ⊢ (φ → (ψ → θ)) | ||
| Theorem | mpdi 48 | A nested modus ponens deduction. (The proof was shortened by O'Cat, 15-Jan-2008.) |
| ⊢ (ψ → χ) & ⊢ ( | ||