Home | Intuitionistic Logic Explorer Theorem List (p. 1 of 106) | < Previous Next > |
Browser slow? Try the
Unicode version. |
||
Mirrors > Metamath Home Page > ILE Home Page > Theorem List Contents > Recent Proofs This page: Page List |
Type | Label | Description |
---|---|---|
Statement | ||
This section includes a few "housekeeping" mechanisms before we begin defining the basics of logic. | ||
The inference rules in this section will normally never appear in a completed proof. They can be ignored if you are using this database to assist learning logic - please start with the statement wn 3 instead. | ||
Theorem | a1ii 1 |
(Note: This inference rule and the next one, idi 2, will
normally
never appear in a completed proof. It can be ignored if you are using
this database to assist learning logic - please start with the statement
wn 3 instead.)
This is a technical inference 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 inference 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 inference 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 a1ii.1, from where the development of the main proof can continue. (2) Develop the independent subproof backwards from hypothesis a1ii.2. If desired, use a 'let' command to pre-assign the conclusion of the independent subproof to a1ii.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 *' to clean up (discard) all a1ii 1 references automatically. This inference was originally designed to assist importing partially completed Proof Worksheets from the mmj2 Proof Assistant GUI, but it can also be useful on its own. Interestingly, no axioms are required for its proof. (Contributed by NM, 7-Feb-2006.) |
Theorem | idi 2 | Inference form of id 19. This inference rule, which requires no axioms for its proof, is useful as a copy-paste mechanism during proof development in mmj2. It is normally not referenced in the final version of a proof, since it is always redundant and can be removed using the 'minimize *' command in the metamath program's Proof Assistant. (Contributed by Alan Sare, 31-Dec-2011.) |
Syntax | wn 3 | If is a wff, so is or "not ." Part of the recursive definition of a wff (well-formed formula). 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 1408 and wel 1410). |
Syntax | wi 4 | If and are wff's, so is or " implies ." Part of the recursive definition of a wff. 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. |
Axiom | ax-1 5 |
Axiom Simp. Axiom A1 of [Margaris] p.
49. One of the axioms of
propositional calculus. 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."
The theorems of propositional calculus are also called tautologies. Although classical propositional logic tautologies can be proved using truth tables, there is no similarly simple system for intuitionistic propositional logic, so proving tautologies from axioms is the preferred approach. (Contributed by NM, 5-Aug-1993.) |
Axiom | ax-2 6 | Axiom Frege. Axiom A2 of [Margaris] p. 49. This axiom "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 244. (Contributed by NM, 5-Aug-1993.) |
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. (Contributed by NM, 5-Aug-1993.) |
The results in this section are based on implication only, and only use ax-1 5, ax-2 6, and ax-mp 7. In an implication, the wff before the arrow is called the "antecedent" and the wff after the arrow is called the "consequent." We will use the following descriptive terms very loosely: A "closed form" or "tautology" has no $e hypotheses. An "inference" has one or more $e hypotheses. A "deduction" is an inference in which the hypotheses and the conclusion share the same antecedent. | ||
Theorem | mp2b 8 | A double modus ponens inference. (Contributed by Mario Carneiro, 24-Jan-2013.) |
Theorem | a1i 9 | Inference derived from axiom ax-1 5. See a1d 22 for an explanation of our informal use of the terms "inference" and "deduction." See also the comment in syld 44. (Contributed by NM, 5-Aug-1993.) |
Theorem | mp1i 10 | Drop and replace an antecedent. (Contributed by Stefan O'Rear, 29-Jan-2015.) |
Theorem | a2i 11 | Inference derived from axiom ax-2 6. (Contributed by NM, 5-Aug-1993.) |
Theorem | imim2i 12 | Inference adding common antecedents in an implication. (Contributed by NM, 5-Aug-1993.) |
Theorem | mpd 13 | A modus ponens deduction. (Contributed by NM, 5-Aug-1993.) |
Theorem | syl 14 | An inference version of the transitive laws for implication imim2 53 and imim1 74, 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." (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 20-Oct-2011.) (Proof shortened by Wolf Lammen, 26-Jul-2012.) |
Theorem | mpi 15 | A nested modus ponens inference. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Stefan Allan, 20-Mar-2006.) |
Theorem | mp2 16 | A double modus ponens inference. (Contributed by NM, 5-Apr-1994.) (Proof shortened by Wolf Lammen, 23-Jul-2013.) |
Theorem | 3syl 17 | Inference chaining two syllogisms. (Contributed by NM, 5-Aug-1993.) |
Theorem | 4syl 18 | Inference chaining three syllogisms. The use of this theorem is marked "discouraged" because it can cause the "minimize" command to have very long run times. However, feel free to use "minimize 4syl /override" if you wish. (Contributed by BJ, 14-Jul-2018.) (New usage is discouraged.) |
Theorem | id 19 | Principle of identity. Theorem *2.08 of [WhiteheadRussell] p. 101. For another version of the proof directly from axioms, see idALT 20. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Stefan Allan, 20-Mar-2006.) |
Theorem | idALT 20 | 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. 17 (PDF p. 23) 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 19. (Contributed by NM, 5-Aug-1993.) (Proof modification is discouraged.) Use id 19 instead. (New usage is discouraged.) |
Theorem | idd 21 | Principle of identity with antecedent. (Contributed by NM, 26-Nov-1995.) |
Theorem | a1d 22 |
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 (wa 101) 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 9. Finally, a "theorem" would be the form with no hypotheses; in this case the "theorem" form would be the original axiom ax-1 5. We usually show the theorem form without a suffix on its label (e.g. pm2.43 51 vs. pm2.43i 47 vs. pm2.43d 48). (Contributed by NM, 5-Aug-1993.) (Revised by NM, 20-Mar-2006.) |
Theorem | 2a1d 23 | Deduction introducing two antecedents. Two applications of a1d 22. Deduction associated with 2a1 25 and 2a1i 27. (Contributed by BJ, 10-Aug-2020.) |
Theorem | a1i13 24 | Add two antecedents to a wff. (Contributed by Jeff Hankins, 4-Aug-2009.) |
Theorem | 2a1 25 | A double form of ax-1 5. Its associated inference is 2a1i 27. Its associated deduction is 2a1d 23. (Contributed by BJ, 10-Aug-2020.) (Proof shortened by Wolf Lammen, 1-Sep-2020.) |
Theorem | a2d 26 | Deduction distributing an embedded antecedent. (Contributed by NM, 23-Jun-1994.) |
Theorem | 2a1i 27 | Add two antecedents to a wff. (Contributed by Jeff Hankins, 4-Aug-2009.) (Proof shortened by Wolf Lammen, 23-Jul-2013.) |
Theorem | sylcom 28 | Syllogism inference with commutation of antecedents. (Contributed by NM, 29-Aug-2004.) (Proof shortened by O'Cat, 2-Feb-2006.) (Proof shortened by Stefan Allan, 23-Feb-2006.) |
Theorem | syl5com 29 | Syllogism inference with commuted antecedents. (Contributed by NM, 24-May-2005.) |
Theorem | com12 30 | Inference that swaps (commutes) antecedents in an implication. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 4-Aug-2012.) |
Theorem | syl11 31 | A syllogism inference. Commuted form of an instance of syl 14. (Contributed by BJ, 25-Oct-2021.) |
Theorem | syl5 32 | A syllogism rule of inference. The second premise is used to replace the second antecedent of the first premise. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 25-May-2013.) |
Theorem | syl6 33 | A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 30-Jul-2012.) |
Theorem | syl56 34 | Combine syl5 32 and syl6 33. (Contributed by NM, 14-Nov-2013.) |
Theorem | syl6com 35 | Syllogism inference with commuted antecedents. (Contributed by NM, 25-May-2005.) |
Theorem | mpcom 36 | Modus ponens inference with commutation of antecedents. (Contributed by NM, 17-Mar-1996.) |
Theorem | syli 37 | Syllogism inference with common nested antecedent. (Contributed by NM, 4-Nov-2004.) |
Theorem | syl2im 38 | Replace two antecedents. Implication-only version of syl2an 277. (Contributed by Wolf Lammen, 14-May-2013.) |
Theorem | pm2.27 39 | This theorem, called "Assertion," can be thought of as closed form of modus ponens ax-mp 7. Theorem *2.27 of [WhiteheadRussell] p. 104. (Contributed by NM, 5-Aug-1993.) |
Theorem | mpdd 40 | A nested modus ponens deduction. (Contributed by NM, 12-Dec-2004.) |
Theorem | mpid 41 | A nested modus ponens deduction. (Contributed by NM, 14-Dec-2004.) |
Theorem | mpdi 42 | A nested modus ponens deduction. (Contributed by NM, 16-Apr-2005.) (Proof shortened by O'Cat, 15-Jan-2008.) |
Theorem | mpii 43 | A doubly nested modus ponens inference. (Contributed by NM, 31-Dec-1993.) (Proof shortened by Wolf Lammen, 31-Jul-2012.) |
Theorem | syld 44 |
Syllogism deduction.
Notice that syld 44 has the same form as syl 14 with added in front of each hypothesis and conclusion. When all theorems referenced in a proof are converted in this way, we can replace with a hypothesis of the proof, allowing the hypothesis to be eliminated with id 19 and become an antecedent. The Deduction Theorem for propositional calculus, e.g. Theorem 3 in [Margaris] p. 56, tells us that this procedure is always possible. (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 19-Feb-2008.) (Proof shortened by Wolf Lammen, 3-Aug-2012.) |
Theorem | mp2d 45 | A double modus ponens deduction. (Contributed by NM, 23-May-2013.) (Proof shortened by Wolf Lammen, 23-Jul-2013.) |
Theorem | a1dd 46 | Deduction introducing a nested embedded antecedent. (Contributed by NM, 17-Dec-2004.) (Proof shortened by O'Cat, 15-Jan-2008.) |
Theorem | pm2.43i 47 | Inference absorbing redundant antecedent. (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 28-Nov-2008.) |
Theorem | pm2.43d 48 | Deduction absorbing redundant antecedent. (Contributed by NM, 18-Aug-1993.) (Proof shortened by O'Cat, 28-Nov-2008.) |
Theorem | pm2.43a 49 | Inference absorbing redundant antecedent. (Contributed by NM, 7-Nov-1995.) (Proof shortened by O'Cat, 28-Nov-2008.) |
Theorem | pm2.43b 50 | Inference absorbing redundant antecedent. (Contributed by NM, 31-Oct-1995.) |
Theorem | pm2.43 51 | Absorption of redundant antecedent. Also called the "Contraction" or "Hilbert" axiom. Theorem *2.43 of [WhiteheadRussell] p. 106. (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 15-Aug-2004.) |
Theorem | imim2d 52 | Deduction adding nested antecedents. (Contributed by NM, 5-Aug-1993.) |
Theorem | imim2 53 | A closed form of syllogism (see syl 14). Theorem *2.05 of [WhiteheadRussell] p. 100. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 6-Sep-2012.) |
Theorem | embantd 54 | Deduction embedding an antecedent. (Contributed by Wolf Lammen, 4-Oct-2013.) |
Theorem | 3syld 55 | Triple syllogism deduction. (Contributed by Jeff Hankins, 4-Aug-2009.) |
Theorem | sylsyld 56 | Virtual deduction rule. (Contributed by Alan Sare, 20-Apr-2011.) |
Theorem | imim12i 57 | Inference joining two implications. (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 29-Oct-2011.) |
Theorem | imim1i 58 | Inference adding common consequents in an implication, thereby interchanging the original antecedent and consequent. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 4-Aug-2012.) |
Theorem | imim3i 59 | Inference adding three nested antecedents. (Contributed by NM, 19-Dec-2006.) |
Theorem | sylc 60 | A syllogism inference combined with contraction. (Contributed by NM, 4-May-1994.) (Revised by NM, 13-Jul-2013.) |
Theorem | syl3c 61 | A syllogism inference combined with contraction. (Contributed by Alan Sare, 7-Jul-2011.) |
Theorem | syl6mpi 62 | syl6 33 combined with mpi 15. (Contributed by Alan Sare, 8-Jul-2011.) (Proof shortened by Wolf Lammen, 13-Sep-2012.) |
Theorem | mpsyl 63 | Modus ponens combined with a syllogism inference. (Contributed by Alan Sare, 20-Apr-2011.) |
Theorem | syl6c 64 | Inference combining syl6 33 with contraction. (Contributed by Alan Sare, 2-May-2011.) |
Theorem | syldd 65 | Nested syllogism deduction. (Contributed by NM, 12-Dec-2004.) (Proof shortened by Wolf Lammen, 11-May-2013.) |
Theorem | syl5d 66 | A nested syllogism deduction. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Josh Purinton, 29-Dec-2000.) (Proof shortened by O'Cat, 2-Feb-2006.) |
Theorem | syl7 67 | A syllogism rule of inference. The second premise is used to replace the third antecedent of the first premise. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 3-Aug-2012.) |
Theorem | syl6d 68 | A nested syllogism deduction. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Josh Purinton, 29-Dec-2000.) (Proof shortened by O'Cat, 2-Feb-2006.) (Revised by NM, 3-Feb-2006.) |
Theorem | syl8 69 | A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. (Contributed by NM, 1-Aug-1994.) (Proof shortened by Wolf Lammen, 3-Aug-2012.) |
Theorem | syl9 70 | A nested syllogism inference with different antecedents. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Josh Purinton, 29-Dec-2000.) |
Theorem | syl9r 71 | A nested syllogism inference with different antecedents. (Contributed by NM, 5-Aug-1993.) |
Theorem | imim12d 72 | Deduction combining antecedents and consequents. (Contributed by NM, 7-Aug-1994.) (Proof shortened by O'Cat, 30-Oct-2011.) |
Theorem | imim1d 73 | Deduction adding nested consequents. (Contributed by NM, 3-Apr-1994.) (Proof shortened by Wolf Lammen, 12-Sep-2012.) |
Theorem | imim1 74 | A closed form of syllogism (see syl 14). Theorem *2.06 of [WhiteheadRussell] p. 100. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 25-May-2013.) |
Theorem | pm2.83 75 | Theorem *2.83 of [WhiteheadRussell] p. 108. (Contributed by NM, 3-Jan-2005.) |
Theorem | com23 76 | Commutation of antecedents. Swap 2nd and 3rd. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 4-Aug-2012.) |
Theorem | com3r 77 | Commutation of antecedents. Rotate right. (Contributed by NM, 25-Apr-1994.) |
Theorem | com13 78 | Commutation of antecedents. Swap 1st and 3rd. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.) |
Theorem | com3l 79 | Commutation of antecedents. Rotate left. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.) |
Theorem | pm2.04 80 | Swap antecedents. Theorem *2.04 of [WhiteheadRussell] p. 100. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 12-Sep-2012.) |
Theorem | com34 81 | Commutation of antecedents. Swap 3rd and 4th. (Contributed by NM, 25-Apr-1994.) |
Theorem | com4l 82 | Commutation of antecedents. Rotate left. (Contributed by NM, 25-Apr-1994.) (Proof shortened by O'Cat, 15-Aug-2004.) |
Theorem | com4t 83 | Commutation of antecedents. Rotate twice. (Contributed by NM, 25-Apr-1994.) |
Theorem | com4r 84 | Commutation of antecedents. Rotate right. (Contributed by NM, 25-Apr-1994.) |
Theorem | com24 85 | Commutation of antecedents. Swap 2nd and 4th. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.) |
Theorem | com14 86 | Commutation of antecedents. Swap 1st and 4th. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.) |
Theorem | com45 87 | Commutation of antecedents. Swap 4th and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) |
Theorem | com35 88 | Commutation of antecedents. Swap 3rd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) |
Theorem | com25 89 | Commutation of antecedents. Swap 2nd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) |
Theorem | com5l 90 | Commutation of antecedents. Rotate left. (Contributed by Jeff Hankins, 28-Jun-2009.) (Proof shortened by Wolf Lammen, 29-Jul-2012.) |
Theorem | com15 91 | Commutation of antecedents. Swap 1st and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) (Proof shortened by Wolf Lammen, 29-Jul-2012.) |
Theorem | com52l 92 | Commutation of antecedents. Rotate left twice. (Contributed by Jeff Hankins, 28-Jun-2009.) |
Theorem | com52r 93 | Commutation of antecedents. Rotate right twice. (Contributed by Jeff Hankins, 28-Jun-2009.) |
Theorem | com5r 94 | Commutation of antecedents. Rotate right. (Contributed by Wolf Lammen, 29-Jul-2012.) |
Theorem | jarr 95 | Elimination of a nested antecedent. (Contributed by Wolf Lammen, 9-May-2013.) |
Theorem | pm2.86i 96 | Inference based on pm2.86 98. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 3-Apr-2013.) |
Theorem | pm2.86d 97 | Deduction based on pm2.86 98. (Contributed by NM, 29-Jun-1995.) (Proof shortened by Wolf Lammen, 3-Apr-2013.) |
Theorem | pm2.86 98 | Converse of axiom ax-2 6. Theorem *2.86 of [WhiteheadRussell] p. 108. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 3-Apr-2013.) |
Theorem | loolin 99 | The Linearity Axiom of the infinite-valued sentential logic (L-infinity) of Lukasiewicz. (Contributed by O'Cat, 12-Aug-2004.) |
Theorem | loowoz 100 | 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.) |
< Previous Next > |
Copyright terms: Public domain | < Previous Next > |