HomeHome Intuitionistic Logic Explorer
Theorem List (p. 1 of 20)
< Previous  Next >
Browser slow? Try the
Unicode version.

Mirrors  >  Metamath Home Page  >  ILE Home Page  >  Theorem List Contents       This page: Page List

Theorem List for Intuitionistic Logic Explorer - 1-100   *Has distinct variable group(s)
TypeLabelDescription
Statement
 
PART 1  CLASSICAL FIRST ORDER LOGIC WITH EQUALITY
 
1.1  Pre-logic
 
1.1.1  Inferences for assisting proof development
 
Theoremdummylink 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 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 *' to clean up (discard) all dummylink 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.

   &       =>   
 
Theoremidi 2 Inference form of id 18. 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.)
   =>   
 
1.2  Propositional calculus
 
1.2.1  Recursively define primitive wffs for propositional calculus
 
Syntaxwn 3 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 1384 and wel 1386).
 
Syntaxwi 4 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.
 
1.2.2  The axioms of propositional calculus
 
Axiomax-1 5 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 5 through ax-3 7 and rule ax-mp 8) 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 8) the wffs ax-1 5, ax-2 6, pm2.04 75, con3 550, notnot2 718, and notnot1 541. 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 75) and replacing the last three with our ax-3 7. (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 4 and wn 3) 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, since truth tables grow exponentially with the number of variables, and the much shorter proofs that we show here were found manually.

 
Axiomax-2 6 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 239.
 
Axiomax-3 7 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.
 
Axiomax-mp 8 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.

   &       =>   
 
1.2.3  Logical implication
 
Theoremmp2b 9 A double modus ponens inference. (Contributed by Mario Carneiro, 24-Jan-2013.)
   &       &       =>   
 
Theorema1i 10 Inference derived from axiom ax-1 5. See a1d 21 for an explanation of our informal use of the terms "inference" and "deduction." See also the comment in syld 39.
   =>   
 
Theorema2i 11 Inference derived from axiom ax-2 6.
   =>   
 
Theoremimim2i 12 Inference adding common antecedents in an implication.
   =>   
 
Theoremmpd 13 A modus ponens deduction.
   &       =>   
 
Theoremsyl 14 An inference version of the transitive laws for implication imim2 48 and imim1 69, 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.) (The proof was shortened by Wolf Lammen, 26-Jul-2012.)
   &       =>   
 
Theoremmpi 15 A nested modus ponens inference. (The proof was shortened by Stefan Allan, 20-Mar-2006.)
   &       =>   
 
Theoremmp2 16 A double modus ponens inference. (The proof was shortened by Wolf Lammen, 23-Jul-2013.)
   &       &       =>   
 
Theorem3syl 17 Inference chaining two syllogisms.
   &       &       =>   
 
Theoremid 18 Principle of identity. Theorem *2.08 of [WhiteheadRussell] p. 101. For another version of the proof directly from axioms, see id1 19. (The proof was shortened by Stefan Allan, 20-Mar-2006.)
 
Theoremid1 19 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 18.
 
Theoremidd 20 Principle of identity with antecedent.
 
Theorema1d 21 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 775) 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 10. 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 46 vs. pm2.43i 42 vs. pm2.43d 43).

   =>   
 
Theorema2d 22 Deduction distributing an embedded antecedent.
   =>   
 
Theorema1ii 23 Add two antecedents to a wff. (Contributed by Jeff Hankins, 4-Aug-2009.) (The proof was shortened by Wolf Lammen, 23-Jul-2013.)
   =>   
 
Theoremsylcom 24 Syllogism inference with commutation of antecedents. (The proof was shortened by O'Cat, 2-Feb-2006.) (The proof was shortened by Stefan Allan, 23-Feb-2006.)
   &       =>   
 
Theoremsyl5com 25 Syllogism inference with commuted antecedents.
   &       =>   
 
Theoremcom12 26 Inference that swaps (commutes) antecedents in an implication. (The proof was shortened by Wolf Lammen, 4-Aug-2012.)
   =>   
 
Theoremsyl5 27 A syllogism rule of inference. The second premise is used to replace the second antecedent of the first premise. (The proof was shortened by Wolf Lammen, 25-May-2013.)
   &       =>   
 
Theoremsyl6 28 A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. (The proof was shortened by Wolf Lammen, 30-Jul-2012.)
   &       =>   
 
Theoremsyl56 29 Combine syl5 27 and syl6 28.
   &       &       =>   
 
Theoremsyl6com 30 Syllogism inference with commuted antecedents.
   &       =>   
 
Theoremmpcom 31 Modus ponens inference with commutation of antecedents.
   &       =>   
 
Theoremsyli 32 Syllogism inference with common nested antecedent.
   &       =>   
 
Theoremsyl2im 33 Replace two antecedents. Implication-only version of syl2an 272. (Contributed by Wolf Lammen, 14-May-2013.)
   &       &       =>   
 
Theorempm2.27 34 This theorem, called "Assertion," can be thought of as closed form of modus ponens ax-mp 8. Theorem *2.27 of [WhiteheadRussell] p. 104.
 
Theoremmpdd 35 A nested modus ponens deduction.
   &       =>   
 
Theoremmpid 36 A nested modus ponens deduction.
   &       =>   
 
Theoremmpdi 37 A nested modus ponens deduction. (The proof was shortened by O'Cat, 15-Jan-2008.)
   &       =>   
 
Theoremmpii 38 A doubly nested modus ponens inference. (The proof was shortened by Wolf Lammen, 31-Jul-2012.)
   &       =>   
 
Theoremsyld 39 Syllogism deduction. (The proof was shortened by O'Cat, 19-Feb-2008.) (The proof was shortened by Wolf Lammen, 3-Aug-2012.)

Notice that syld 39 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 18 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.

   &       =>   
 
Theoremmp2d 40 A double modus ponens deduction. (The proof was shortened by Wolf Lammen, 23-Jul-2013.)
   &       &       =>   
 
Theorema1dd 41 Deduction introducing a nested embedded antecedent. (The proof was shortened by O'Cat, 15-Jan-2008.)
   =>   
 
Theorempm2.43i 42 Inference absorbing redundant antecedent. (The proof was shortened by O'Cat, 28-Nov-2008.)
   =>   
 
Theorempm2.43d 43 Deduction absorbing redundant antecedent. (The proof was shortened by O'Cat, 28-Nov-2008.)
   =>   
 
Theorempm2.43a 44 Inference absorbing redundant antecedent. (The proof was shortened by O'Cat, 28-Nov-2008.)
   =>   
 
Theorempm2.43b 45 Inference absorbing redundant antecedent.
   =>   
 
Theorempm2.43 46 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.)
 
Theoremimim2d 47 Deduction adding nested antecedents.
   =>   
 
Theoremimim2 48 A closed form of syllogism (see syl 14). Theorem *2.05 of [WhiteheadRussell] p. 100. (The proof was shortened by Wolf Lammen, 6-Sep-2012.)
 
Theoremembantd 49 Deduction embedding an antecedent. (Contributed by Wolf Lammen, 4-Oct-2013.)
   &       =>   
 
Theorem3syld 50 Triple syllogism deduction. (Contributed by Jeff Hankins, 4-Aug-2009.)
   &       &       =>   
 
Theoremsylsyld 51 Virtual deduction rule. (Contributed by Alan Sare, 20-Apr-2011.)
   &       &       =>   
 
Theoremimim12i 52 Inference joining two implications. (The proof was shortened by O'Cat, 29-Oct-2011.)
   &       =>   
 
Theoremimim1i 53 Inference adding common consequents in an implication, thereby interchanging the original antecedent and consequent. (The proof was shortened by Wolf Lammen, 4-Aug-2012.)
   =>   
 
Theoremimim3i 54 Inference adding three nested antecedents.
   =>   
 
Theoremsylc 55 A syllogism inference combined with contraction.
   &       &       =>   
 
Theoremsyl3c 56 A syllogism inference combined with contraction. (Contributed by Alan Sare, 7-Jul-2011.)
   &       &       &       =>   
 
Theoremsyl6mpi 57 syl6 28 combined with mpi 15. (Contributed by Alan Sare, 8-Jul-2011.) (The proof was shortened by Wolf Lammen, 13-Sep-2012.)
   &       &       =>   
 
Theoremmpsyl 58 Modus ponens combined with a syllogism inference. (Contributed by Alan Sare, 20-Apr-2011.)
   &       &       =>   
 
Theoremsyl6c 59 Inference combining syl6 28 with contraction. (Contributed by Alan Sare, 2-May-2011.)
   &       &       =>   
 
Theoremsyldd 60 Nested syllogism deduction. (The proof was shortened by Wolf Lammen, 11-May-2013.)
   &       =>   
 
Theoremsyl5d 61 A nested syllogism deduction. (The proof was shortened by Josh Purinton, 29-Dec-2000 and shortened further by O'Cat, 2-Feb-2006.)
   &       =>   
 
Theoremsyl7 62 A syllogism rule of inference. The second premise is used to replace the third antecedent of the first premise. (The proof was shortened by Wolf Lammen, 3-Aug-2012.)
   &       =>   
 
Theoremsyl6d 63 A nested syllogism deduction. (The proof was shortened by Josh Purinton, 29-Dec-2000 and shortened further by O'Cat, 2-Feb-2006.)
   &       =>   
 
Theoremsyl8 64 A syllogism rule of inference. The second premise is used to replace the consequent of the first premise. (The proof was shortened by Wolf Lammen, 3-Aug-2012.)
   &       =>   
 
Theoremsyl9 65 A nested syllogism inference with different antecedents. (The proof was shortened by Josh Purinton, 29-Dec-2000.)
   &       =>   
 
Theoremsyl9r 66 A nested syllogism inference with different antecedents.
   &       =>   
 
Theoremimim12d 67 Deduction combining antecedents and consequents. (The proof was shortened by O'Cat, 30-Oct-2011.)
   &       =>   
 
Theoremimim1d 68 Deduction adding nested consequents. (The proof was shortened by Wolf Lammen, 12-Sep-2012.)
   =>   
 
Theoremimim1 69 A closed form of syllogism (see syl 14). Theorem *2.06 of [WhiteheadRussell] p. 100. (The proof was shortened by Wolf Lammen, 25-May-2013.)
 
Theorempm2.83 70 Theorem *2.83 of [WhiteheadRussell] p. 108.
 
Theoremcom23 71 Commutation of antecedents. Swap 2nd and 3rd. (The proof was shortened by Wolf Lammen, 4-Aug-2012.)
   =>   
 
Theoremcom3r 72 Commutation of antecedents. Rotate right.
   =>   
 
Theoremcom13 73 Commutation of antecedents. Swap 1st and 3rd. (The proof was shortened by Wolf Lammen, 28-Jul-2012.)
   =>   
 
Theoremcom3l 74 Commutation of antecedents. Rotate left. (The proof was shortened by Wolf Lammen, 28-Jul-2012.)
   =>   
 
Theorempm2.04 75 Swap antecedents. Theorem *2.04 of [WhiteheadRussell] p. 100. (The proof was shortened by Wolf Lammen, 12-Sep-2012.)
 
Theoremcom34 76 Commutation of antecedents. Swap 3rd and 4th.
   =>   
 
Theoremcom4l 77 Commutation of antecedents. Rotate left. (The proof was shortened by O'Cat, 15-Aug-2004.)
   =>   
 
Theoremcom4t 78 Commutation of antecedents. Rotate twice.
   =>   
 
Theoremcom4r 79 Commutation of antecedents. Rotate right.
   =>   
 
Theoremcom24 80 Commutation of antecedents. Swap 2nd and 4th. (The proof was shortened by Wolf Lammen, 28-Jul-2012.)
   =>   
 
Theoremcom14 81 Commutation of antecedents. Swap 1st and 4th. (The proof was shortened by Wolf Lammen, 28-Jul-2012.)
   =>   
 
Theoremcom45 82 Commutation of antecedents. Swap 4th and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.)
   =>   
 
Theoremcom35 83 Commutation of antecedents. Swap 3rd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.)
   =>   
 
Theoremcom25 84 Commutation of antecedents. Swap 2nd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.)
   =>   
 
Theoremcom5l 85 Commutation of antecedents. Rotate left. (Contributed by Jeff Hankins, 28-Jun-2009.) (The proof was shortened by Wolf Lammen, 29-Jul-2012.)
   =>   
 
Theoremcom15 86 Commutation of antecedents. Swap 1st and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) (The proof was shortened by Wolf Lammen, 29-Jul-2012.)
   =>   
 
Theoremcom52l 87 Commutation of antecedents. Rotate left twice. (Contributed by Jeff Hankins, 28-Jun-2009.)
   =>   
 
Theoremcom52r 88 Commutation of antecedents. Rotate right twice. (Contributed by Jeff Hankins, 28-Jun-2009.)
   =>   
 
Theoremcom5r 89 Commutation of antecedents. Rotate right. (Contributed by Wolf Lammen, 29-Jul-2012.)
   =>   
 
Theoremjarr 90 Elimination of a nested antecedent as a kind of reversal of inference ja 738. (Contributed by Wolf Lammen, 9-May-2013.)
 
Theorempm2.86i 91 Inference based on pm2.86 93. (The proof was shortened by Wolf Lammen, 3-Apr-2013.)
   =>   
 
Theorempm2.86d 92 Deduction based on pm2.86 93. (The proof was shortened by Wolf Lammen, 3-Apr-2013.)
   =>   
 
Theorempm2.86 93 Converse of axiom ax-2 6. Theorem *2.86 of [WhiteheadRussell] p. 108. (The proof was shortened by Wolf Lammen, 3-Apr-2013.)
 
TheoremloolinALT 94 The Linearity Axiom of the infinite-valued sentential logic (L-infinity) of Lukasiewicz. This version of loolin 755 does not use ax-3 7, meaning that this theorem is intuitionistically valid. (Contributed by O'Cat, 12-Aug-2004.)
 
Theoremloowoz 95 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.)
 
1.2.4  Logical conjunction and logical equivalence
 
Syntaxwa 96 Extend wff definition to include conjunction ('and').
 
Syntaxwb 97 Extend our wff definition to include the biconditional connective.
 
Axiomax-ia1 98 Left 'and' elimination. Axiom 1 of 10 for intuitionistic logic.
 
Axiomax-ia2 99 Right 'and' elimination. Axiom 2 of 10 for intuitionistic logic.
 
Axiomax-ia3 100 'And' introduction. Axiom 3 of 10 for intuitionistic logic.
    < Previous  Next >

Page List
Jump to page: Contents  1 1-100 2 101-200 3 201-300 4 301-400 5 401-500 6 501-600 7 601-700 8 701-800 9 801-900 10 901-1000 11 1001-1100 12 1101-1200 13 1201-1300 14 1301-1400 15 1401-1500 16 1501-1600 17 1601-1700 18 1701-1800 19 1801-1900 20 1901-1914
  Copyright terms: Public domain < Previous  Next >