HomeUnicode version.
| Home |
Metamath Proof Explorer | < Wrap Next > |
| Browser slow? Try the
Unicode version. |
| Color key: | Metamath Proof Explorer
(1-10419) |
Hilbert Space Explorer
(10420-12013) |
Users' Mathboxes
(12014-17411) |
| 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) After the independent subproof is complete, use 'improve all' to assign it automatically 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 1299 and wel 1301).
|
 | ||
| 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.
|
| | ||
| 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 34, con3 110, notnot2 100, and notnot1 102. 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 34) 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 186. |
|
| ||
| 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.
Note: In some web page displays such as the Statement List, the symbols "&" and "=>" informally indicate the relationship between the hypotheses and the assertion (conclusion), abbreviating the English words "and" and "implies." They are not part of the formal language. |
| | ||
| Logical implication | ||
| Theorem | a1i 8 | Inference derived from axiom ax-1 4. See a1d 15 for an explanation of our informal use of the terms "inference" and "deduction." See also the comment in syld 30. |
| | ||
| Theorem | a1i12 9 | Add two antecedents to a wff. (Contributed by Jeff Hankins, 4-Aug-2009.) |
| | ||
| Theorem | a2i 10 | Inference derived from axiom ax-2 5. |
| | ||
| Theorem | imim2i 11 | Inference adding common antecedents in an implication. |
| | ||
| Theorem | syl 12 |
An inference version of the transitive laws for implication imim2 17
and
imim1 18, 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." (The proof was
shortened by
O'Cat, 20-Oct-2011.)
(A bit of trivia: this is the most commonly referenced assertion in our database. In second place is ax-mp 7, followed by visset 2295, bitri 190, imp 377, and ex 402. The Metamath program command 'show usage' shows the number of references.) |
| | ||
| Theorem | sylOLD 13 | An inference version of the transitive laws for implication. |
| | ||
| Theorem | com12 14 | Inference that swaps (commutes) antecedents in an implication. |
|
| ||
| Theorem | a1d 15 |
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 |
| | ||
| Theorem | a2d 16 | Deduction distributing an embedded antecedent. |
 | ||
| Theorem | imim2 17 | A closed form of syllogism (see syl 12). Theorem *2.05 of [WhiteheadRussell] p. 100. |
| | ||
| Theorem | imim1 18 | A closed form of syllogism (see syl 12). Theorem *2.06 of [WhiteheadRussell] p. 100. |
| | ||
| Theorem | imim1i 19 | Inference adding common consequents in an implication, thereby interchanging the original antecedent and consequent. |
| | ||
| Theorem | syl5 20 | A syllogism rule of inference. The second premise is used to replace the second antecedent of the first premise. |
|
| ||
| Theorem | imim12i 21 | Inference joining two implications. (The proof was shortened by O'Cat, 29-Oct-2011.) |
| | ||
| Theorem | imim12iOLD 22 | Inference joining two implications. |
| | ||
| Theorem | imim3i 23 | Inference adding three nested antecedents. |
| | ||
| Theorem | 3syl 24 | Inference chaining two syllogisms. |
| | ||
| Theorem | syl6 25 | A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. |
|
| ||
| Theorem | syl7 26 | A syllogism rule of inference. The second premise is used to replace the third antecedent of the first premise. |
| ||
| Theorem | syl8 27 | A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. |
|
| ||
| Theorem | imim2d 28 | Deduction adding nested antecedents. |
| | ||
| Theorem | mpd 29 | A modus ponens deduction. |
| | ||
| Theorem | syld 30 |
Syllogism deduction. (The proof was shortened by O'Cat, 19-Feb-2008.)
Notice that syld 30 can be obtained from syl 12 by
replacing each
hypothesis and conclusion |
| | ||
| Theorem | 3syld 31 | Triple syllogism deduction. (Contributed by Jeff Hankins, 4-Aug-2009.) |
| | ||
| Theorem | sylsyld 32 | Virtual deduction rule e12 16593 without virtual deduction symbols. (Contributed by Alan Sare, 20-Apr-2011.) |
|
| ||
| Theorem | imim1d 33 | Deduction adding nested consequents. |
| | ||
| Theorem | pm2.04 34 | Swap antecedents. Theorem *2.04 of [WhiteheadRussell] p. 100. |
|
| ||
| Theorem | pm2.83 35 | Theorem *2.83 of [WhiteheadRussell] p. 108. |
|
| ||
| Theorem | com23 36 | Commutation of antecedents. Swap 2nd and 3rd. |
|
| ||
| Theorem | com13 37 | Commutation of antecedents. Swap 1st and 3rd. |
|
| ||
| Theorem | com3l 38 | Commutation of antecedents. Rotate left. |
|
| ||
| Theorem | com3r 39 | Commutation of antecedents. Rotate right. |
| | ||
| Theorem | com34 40 | Commutation of antecedents. Swap 3rd and 4th. |
|
| ||
| Theorem | com24 41 | Commutation of antecedents. Swap 2nd and 4th. |
|
| ||
| Theorem | com14 42 | Commutation of antecedents. Swap 1st and 4th. |
|
| ||
| Theorem | com4l 43 | Commutation of antecedents. Rotate left. (The proof was shortened by O'Cat, 15-Aug-2004.) |
|
| ||
| Theorem | com4t 44 | Commutation of antecedents. Rotate twice. |
|
| ||
| Theorem | com4r 45 | Commutation of antecedents. Rotate right. |
|
| ||
| Theorem | com45 46 | Commutation of antecedents. Swap 4th and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) |
| ||
| Theorem | com35 47 | Commutation of antecedents. Swap 3rd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) |
|
| ||
| Theorem | com25 48 | Commutation of antecedents. Swap 2nd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) |
|
| ||
| Theorem | com15 49 | Commutation of antecedents. Swap 1st and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) |
|
| ||
| Theorem | com5l 50 | Commutation of antecedents. Rotate left. (Contributed by Jeff Hankins, 28-Jun-2009.) |
|
| ||
| Theorem | com52l 51 | Commutation of antecedents. Rotate left twice. (Contributed by Jeff Hankins, 28-Jun-2009.) |
|
| ||
| Theorem | com52r 52 | Commutation of antecedents. Rotate right twice. (Contributed by Jeff Hankins, 28-Jun-2009.) |
|
| ||
| Theorem | a1dd 53 | Deduction introducing a nested embedded antecedent. (The proof was shortened by O'Cat, 15-Jan-2008.) |
| | ||
| Theorem | mp2 54 | A double modus ponens inference. |
|
| ||
| Theorem | mpi 55 | A nested modus ponens inference. (The proof was shortened by Stefan Allan, 20-Mar-2006.) |
|
| ||
| Theorem | mpii 56 | A doubly nested modus ponens inference. |
|
| ||
| Theorem | mpdd 57 | A nested modus ponens deduction. |
|
| ||
| Theorem | mpid 58 | A nested modus ponens deduction. |
|
| ||
| Theorem | mpdi 59 | A nested modus ponens deduction. (The proof was shortened by O'Cat, 15-Jan-2008.) |
|
| ||
| Theorem | mpcom 60 | Modus ponens inference with commutation of antecedents. |
|
| ||
| Theorem | syldd 61 | Nested syllogism deduction. |
|
| ||
| Theorem | sylcom 62 | Syllogism inference with commutation of antecedents. (The proof was shortened by O'Cat, 2-Feb-2006 and shortened further by Stefan Allan, 23-Feb-2006.) |
|
| ||
| Theorem | syl5com 63 | Syllogism inference with commuted antecedents. |
|
| ||
| Theorem | syl6com 64 | Syllogism inference with commuted antecedents. |
|
| ||
| Theorem | syli 65 | Syllogism inference with common nested antecedent. |
|
| ||
| Theorem | syl5d 66 | A nested syllogism deduction. (The proof was shortened by Josh Purinton, 29-Dec-2000 and shortened further by O'Cat, 2-Feb-2006.) |
| | ||
| Theorem | syl6d 67 | A nested syllogism deduction. (The proof was shortened by Josh Purinton, 29-Dec-2000 and shortened further by O'Cat, 2-Feb-2006.) |
| | ||
| Theorem | syl6mpi 68 | e20 16595 without virtual deductions. (Contributed by Alan Sare, 8-Jul-2011.) |
| | ||
| Theorem | imim12d 69 | Deduction combining antecedents and consequents. (The proof was shortened by O'Cat, 30-Oct-2011.) |
| | ||
| Theorem | imim12dOLD 70 | Deduction combining antecedents and consequents. |
| | ||
| Theorem | syl9 71 | A nested syllogism inference with different antecedents. (The proof was shortened by Josh Purinton, 29-Dec-2000.) |
|
| ||
| Theorem | syl9r 72 | A nested syllogism inference with different antecedents. |
|
| ||
| Theorem | id 73 | Principle of identity. Theorem *2.08 of [WhiteheadRussell] p. 101. For another version of the proof directly from axioms, see id1 74. (The proof was shortened by Stefan Allan, 20-Mar-2006.) |
| | ||
| Theorem | id1 74 | Principle of identity. Theorem *2.08 of [WhiteheadRussell] p. 101. This version is proved directly from the axioms for demonstration purposes. This proof is a popular example in the literature and is identical, step for step, to the proofs of Theorem 1 of [Margaris] p. 51, Example 2.7(a) of [Hamilton] p. 31, Lemma 10.3 of [BellMachover] p. 36, and Lemma 1.8 of [Mendelson] p. 36. It is also "Our first proof" in Hirst and Hirst's A Primer for Logic and Proof p. 16 (PDF p. 22) at http://www.mathsci.appstate.edu/~jlh/primer/hirst.pdf. For a shorter version of the proof that takes advantage of previously proved theorems, see id 73. |
| | ||
| Theorem | idd 75 | Principle of identity with antecedent. |
| | ||
| Theorem | pm2.27 76 | This theorem, called "Assertion," can be thought of as closed form of modus ponens ax-mp 7. Theorem *2.27 of [WhiteheadRussell] p. 104. |
| | ||
| Theorem | pm2.43 77 | Absorption of redundant antecedent. Also called the "Contraction" or "Hilbert" axiom. Theorem *2.43 of [WhiteheadRussell] p. 106. (The proof was shortened by O'Cat, 15-Aug-2004.) |
| | ||
| Theorem | pm2.43i 78 | Inference absorbing redundant antecedent. (The proof was shortened by O'Cat, 28-Nov-2008.) |
| | ||
| Theorem | pm2.43d 79 | Deduction absorbing redundant antecedent. (The proof was shortened by O'Cat, 28-Nov-2008.) |
|
| ||
| Theorem | pm2.43a 80 | Inference absorbing redundant antecedent. (The proof was shortened by O'Cat, 28-Nov-2008.) |
| | ||
| Theorem | pm2.43b 81 | Inference absorbing redundant antecedent. |
|
| ||
| Theorem | sylcOLD 82 | A syllogism inference combined with contraction. (OBSOLETE - replaced by new sylc 83 21-Mar-2012. --NM) |
|
| ||
| Theorem | sylc 83 | A syllogism inference combined with contraction. |
| | ||
| Theorem | syl3c 84 | A syllogism inference combined with contraction. e111 16564 without virtual deductions. (Contributed by Alan Sare, 7-Jul-2011.) |
| | ||
| Theorem | pm2.86 85 | Converse of axiom ax-2 5. Theorem *2.86 of [WhiteheadRussell] p. 108. |
|
| ||
| Theorem | pm2.86i 86 | Inference based on pm2.86 85. |
|
| ||
| Theorem | pm2.86d 87 | Deduction based on pm2.86 85. |
|
| ||
| Theorem | loolin 88 | The Linearity Axiom of the infinite-valued sentential logic (L-infinity) of Lukasiewicz. (Contributed by O'Cat, 12-Aug-2004.) |
| | ||
| Theorem | loowoz 89 | An alternate for the Linearity Axiom of the infinite-valued sentential logic (L-infinity) of Lukasiewicz, due to Barbara Wozniakowska, Reports on Mathematical Logic 10, 129-137 (1978). (Contributed by O'Cat, 8-Aug-2004.) |
| | ||
| Logical negation | ||
| Theorem | con4i 90 | Inference rule derived from axiom ax-3 6. |
| | ||
| Theorem | con4d 91 | Deduction derived from axiom ax-3 6. |
|
| ||
| Theorem | pm2.21 92 | From a wff and its negation, anything is true. Theorem *2.21 of [WhiteheadRussell] p. 104. Also called the Duns Scotus law. |
| | ||
| Theorem | pm2.21i 93 | A contradiction implies anything. Inference from pm2.21 92. |
| | ||
| Theorem | pm2.21d 94 | A contradiction implies anything. Deduction from pm2.21 92. |
| | ||
| Theorem | pm2.24 95 | Theorem *2.24 of [WhiteheadRussell] p. 104. |
| | ||
| Theorem | pm2.24ii 96 | A contradiction implies anything. Inference from pm2.24 95. |
| | ||
| Theorem | pm2.18 97 | Proof by contradiction. Theorem *2.18 of [WhiteheadRussell] p. 103. Also called the Law of Clavius. |
| | ||
| Theorem | peirce 98 | Peirce's axiom. This odd-looking theorem is the "difference" between an intuitionistic system of propositional calculus and a classical system and is not accepted by intuitionists. When Peirce's axiom is added to an intuitionistic system, the system becomes equivalent to our classical system ax-1 4 through ax-3 6. A curious fact about this theorem is that it requires ax-3 6 for its proof even though the result has no negation connectives in it. |
|
| ||
| Theorem | looinv 99 | The Inversion Axiom of the infinite-valued sentential logic (L-infinity) of Lukasiewicz. Using dfor2 246, we can see that this essentially expresses "disjunction commutes." Theorem *2.69 of [WhiteheadRussell] p. 108. |
|
| ||
| Theorem | notnot2 100 | Converse of double negation. Theorem *2.14 of [WhiteheadRussell] p. 102. (The proof was shortened by David Harvey, 5-Sep-1999. An even shorter proof found by Josh Purinton, 29-Dec-2000.) |
| | ||
| MPE Home Contents | Copyright terms: Public domain | < Wrap Next > |