HomeHome New Foundations Explorer
Theorem List (p. 1 of 64)
< Previous  Next >
Bad symbols? Try the
GIF version.

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

Theorem List for New Foundations Explorer - 1-100   *Has distinct variable group(s)
TypeLabelDescription
Statement
 
PART 1  CLASSICAL FIRST ORDER LOGIC WITH EQUALITY

Logic can be defined as the "study of the principles of correct reasoning" (Merrilee H. Salmon's 1991 "Informal Reasoning and Informal Logic" in Informal Reasoning and Education ) or as "a formal system using symbolic techniques and mathematical methods to establish truth-values" (the Oxford English Dictionary).

This section formally defines the logic system we will use. In particular, it defines symbols for declaring truthful statements, along with rules for deriving truthful statements from other truthful statements. The system defined here is classical first order logic with equality (the most common logic system used by mathematicians).

We begin with a few housekeeping items in pre-logic, and then introduce propositional calculus (both its axioms and important theorems that can be derived from them). Propositional calculus deals with general truths about well-formed formulas (wffs) regardless of how they are constructed. This is followed by proofs that other axiomatizations of classical propositional calculus can be derived from the axioms we have chosen to use.

We then define predicate calculus, which adds additional symbols and rules useful for discussing objects (beyond simply true or false). In particular, it introduces the symbols = ("equals"), ("is a member of"), and ("for all"). The first two are called "predicates." A predicate specifies a true or false relationship between its two arguments.

 
1.1  Pre-logic

This section includes a few "housekeeping" mechanisms before we begin defining the basics of logic.

 
1.1.1  Inferences for assisting proof development

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.

 
Theorema1ii 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.)

φ    &   ψ       φ
 
Theoremidi 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.)
φ       φ
 
1.2  Propositional calculus

Propositional calculus deals with general truths about well-formed formulas (wffs) regardless of how they are constructed. The simplest propositional truth is (φφ), which can be read "if something is true, then it is true" - rather trivial and obvious, but nonetheless it must be proved from the axioms (see theorem id 19).

Our system of propositional calculus consists of three basic axioms and another axiom that defines the modus-ponens inference rule. It is attributed to Jan Lukasiewicz (pronounced woo-kah-SHAY-vitch) and was popularized by Alonzo Church, who called it system P2. (Thanks to Ted Ulrich for this information.) These axioms are ax-1 5, ax-2 6, ax-3 7, and (for modus ponens) ax-mp 8. Some closely followed texts include [Margaris] for the axioms and [WhiteheadRussell] for the theorems.

The propositional calculus used here is the classical system widely used by mathematicians. In particular, this logic system accepts the "law of the excluded middle" as proven in exmid 404, which says that a logical statement is either true or not true. This is an essential distinction of classical logic and is not a theorem of intuitionistic logic.

All 194 axioms, definitions, and theorems for propositional calculus in Principia Mathematica (specifically *1.2 through *5.75) are axioms or formally proven. See the Bibliographic Cross-References at http://us.metamath.org/mpeuni/mmbiblio.html for a complete cross-reference from sources used to its formalization in the Metamath Proof Explorer.

 
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 1643 and wel 1711).
wff ¬ φ
 
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. After we define the axioms of propositional calculus (ax-1 5, ax-2 6, ax-3 7, and ax-mp 8), the biconditional (df-bi 177), the constant true (df-tru 1319), and the constant false (df-fal 1320), we will be able to prove these truth table values: (( ⊤ → ⊤ ) ↔ ⊤ ) (truimtru 1344), (( ⊤ → ⊥ ) ↔ ⊥ ) (truimfal 1345), (( ⊥ → ⊤ ) ↔ ⊤ ) (falimtru 1346), and (( ⊥ → ⊥ ) ↔ ⊤ ) (falimfal 1347). These have straightforward meanings, for example, (( ⊤ → ⊤ ) ↔ ⊤ ) just means "the value of ⊤ → ⊤ is ".

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. Contrast with (df-bi 177), (df-an 360), and (df-or 359).

This is called "material implication" and the arrow is usually read as "implies." However, material implication is not identical to the meaning of "implies" in natural language. For example, the word "implies" may suggest a causal relationship in natural language. Material implication does not require any causal relationship. Also, note that in material implication, if the consequent is true then the wff is always true (even if the antecedent is false). Thus, if "implies" means material implication, it is true that "if the moon is made of green cheese that implies that 5=5" (because 5=5). Similarly, if the antecedent is false, the wff is always true. Thus, it is true that, "if the moon made of green cheese that implies that 5=7" (because the moon is not actually made of green cheese). A contradiction implies anything (pm2.21i 123). In short, material implication has a very specific technical definition, and misunderstandings of it are sometimes called "paradoxes of logical implication."

wff (φψ)
 
1.2.2  The axioms of propositional calculus

Postulate the three axioms of classical propositional calculus.

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 76, con3 126, notnot2 104, and notnot1 114. 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 76) 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-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." (Contributed by NM, 5-Aug-1993.)
(φ → (ψφ))
 
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 353. (Contributed by NM, 5-Aug-1993.)
((φ → (ψχ)) → ((φψ) → (φχ)))
 
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. (Contributed by NM, 5-Aug-1993.)
((¬ φ → ¬ ψ) → (ψφ))
 
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. "Modus ponens" is short for "modus ponendo ponens," a Latin phrase that means "the mood that by affirming affirms" [Sanford] p. 39. This rule is similar to the rule of modus tollens mto 167.

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.)

φ    &   (φψ)       ψ
 
1.2.3  Logical implication

The results in this section are based on implication only, and avoid ax-3. 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.

 
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 22 for an explanation of our informal use of the terms "inference" and "deduction." See also the comment in syld 40. (Contributed by NM, 5-Aug-1993.)
φ       (ψφ)
 
Theoremmp1i 11 Drop and replace an antecedent. (Contributed by Stefan O'Rear, 29-Jan-2015.)
φ    &   (φψ)       (χψ)
 
Theorema2i 12 Inference derived from axiom ax-2 6. (Contributed by NM, 5-Aug-1993.)
(φ → (ψχ))       ((φψ) → (φχ))
 
Theoremimim2i 13 Inference adding common antecedents in an implication. (Contributed by NM, 5-Aug-1993.)
(φψ)       ((χφ) → (χψ))
 
Theoremmpd 14 A modus ponens deduction. A translation of natural deduction rule E ( elimination). (Contributed by NM, 5-Aug-1993.)
(φψ)    &   (φ → (ψχ))       (φχ)
 
Theoremsyl 15 An inference version of the transitive laws for implication imim2 49 and imim1 70, 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 eqid 2353, followed by syl2anc 642, adantr 451, syl3anc 1182, and ax-mp 8. The Metamath program command 'show usage' shows the number of references.) (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 20-Oct-2011.) (Proof shortened by Wolf Lammen, 26-Jul-2012.)

(φψ)    &   (ψχ)       (φχ)
 
Theoremmpi 16 A nested modus ponens inference. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Stefan Allan, 20-Mar-2006.)
ψ    &   (φ → (ψχ))       (φχ)
 
Theoremmp2 17 A double modus ponens inference. (Contributed by NM, 5-Apr-1994.) (Proof shortened by Wolf Lammen, 23-Jul-2013.)
φ    &   ψ    &   (φ → (ψχ))       χ
 
Theorem3syl 18 Inference chaining two syllogisms. (Contributed by NM, 5-Aug-1993.)
(φψ)    &   (ψχ)    &   (χθ)       (φθ)
 
Theoremid 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.)
(φφ)
 
TheoremidALT 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/~hirstjl/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.)
(φφ)
 
Theoremidd 21 Principle of identity with antecedent. (Contributed by NM, 26-Nov-1995.)
(φ → (ψψ))
 
Theorema1d 22 Deduction introducing an embedded antecedent.

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 360) 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 47 vs. pm2.43i 43 vs. pm2.43d 44). When an inference is converted to a theorem by eliminating an "is a set" hypothesis, we sometimes suffix the theorem form with "g" (for "more general") as in uniex 4317 vs. uniexg 4316. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Stefan Allan, 20-Mar-2006.)

(φψ)       (φ → (χψ))
 
Theorema2d 23 Deduction distributing an embedded antecedent. (Contributed by NM, 23-Jun-1994.)
(φ → (ψ → (χθ)))       (φ → ((ψχ) → (ψθ)))
 
Theorem2a1i 24 Add two antecedents to a wff. (Contributed by Jeff Hankins, 4-Aug-2009.) (Proof shortened by Wolf Lammen, 23-Jul-2013.)
χ       (φ → (ψχ))
 
Theoremsylcom 25 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.)
(φ → (ψχ))    &   (ψ → (χθ))       (φ → (ψθ))
 
Theoremsyl5com 26 Syllogism inference with commuted antecedents. (Contributed by NM, 24-May-2005.)
(φψ)    &   (χ → (ψθ))       (φ → (χθ))
 
Theoremcom12 27 Inference that swaps (commutes) antecedents in an implication. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 4-Aug-2012.)
(φ → (ψχ))       (ψ → (φχ))
 
Theoremsyl5 28 A syllogism rule of inference. The first premise is used to replace the second antecedent of the second premise. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 25-May-2013.)
(φψ)    &   (χ → (ψθ))       (χ → (φθ))
 
Theoremsyl6 29 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.)
(φ → (ψχ))    &   (χθ)       (φ → (ψθ))
 
Theoremsyl56 30 Combine syl5 28 and syl6 29. (Contributed by NM, 14-Nov-2013.)
(φψ)    &   (χ → (ψθ))    &   (θτ)       (χ → (φτ))
 
Theoremsyl6com 31 Syllogism inference with commuted antecedents. (Contributed by NM, 25-May-2005.)
(φ → (ψχ))    &   (χθ)       (ψ → (φθ))
 
Theoremmpcom 32 Modus ponens inference with commutation of antecedents. (Contributed by NM, 17-Mar-1996.)
(ψφ)    &   (φ → (ψχ))       (ψχ)
 
Theoremsyli 33 Syllogism inference with common nested antecedent. (Contributed by NM, 4-Nov-2004.)
(ψ → (φχ))    &   (χ → (φθ))       (ψ → (φθ))
 
Theoremsyl2im 34 Replace two antecedents. Implication-only version of syl2an 463. (Contributed by Wolf Lammen, 14-May-2013.)
(φψ)    &   (χθ)    &   (ψ → (θτ))       (φ → (χτ))
 
Theorempm2.27 35 This theorem, called "Assertion," can be thought of as closed form of modus ponens ax-mp 8. Theorem *2.27 of [WhiteheadRussell] p. 104. (Contributed by NM, 5-Aug-1993.)
(φ → ((φψ) → ψ))
 
Theoremmpdd 36 A nested modus ponens deduction. (Contributed by NM, 12-Dec-2004.)
(φ → (ψχ))    &   (φ → (ψ → (χθ)))       (φ → (ψθ))
 
Theoremmpid 37 A nested modus ponens deduction. (Contributed by NM, 14-Dec-2004.)
(φχ)    &   (φ → (ψ → (χθ)))       (φ → (ψθ))
 
Theoremmpdi 38 A nested modus ponens deduction. (Contributed by NM, 16-Apr-2005.) (Proof shortened by O'Cat, 15-Jan-2008.)
(ψχ)    &   (φ → (ψ → (χθ)))       (φ → (ψθ))
 
Theoremmpii 39 A doubly nested modus ponens inference. (Contributed by NM, 31-Dec-1993.) (Proof shortened by Wolf Lammen, 31-Jul-2012.)
χ    &   (φ → (ψ → (χθ)))       (φ → (ψθ))
 
Theoremsyld 40 Syllogism deduction. (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 19-Feb-2008.) (Proof shortened by Wolf Lammen, 3-Aug-2012.)

Notice that syld 40 has the same form as syl 15 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.

(φ → (ψχ))    &   (φ → (χθ))       (φ → (ψθ))
 
Theoremmp2d 41 A double modus ponens deduction. (Contributed by NM, 23-May-2013.) (Proof shortened by Wolf Lammen, 23-Jul-2013.)
(φψ)    &   (φχ)    &   (φ → (ψ → (χθ)))       (φθ)
 
Theorema1dd 42 Deduction introducing a nested embedded antecedent. (Contributed by NM, 17-Dec-2004.) (Proof shortened by O'Cat, 15-Jan-2008.)
(φ → (ψχ))       (φ → (ψ → (θχ)))
 
Theorempm2.43i 43 Inference absorbing redundant antecedent. (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 28-Nov-2008.)
(φ → (φψ))       (φψ)
 
Theorempm2.43d 44 Deduction absorbing redundant antecedent. (Contributed by NM, 18-Aug-1993.) (Proof shortened by O'Cat, 28-Nov-2008.)
(φ → (ψ → (ψχ)))       (φ → (ψχ))
 
Theorempm2.43a 45 Inference absorbing redundant antecedent. (Contributed by NM, 7-Nov-1995.) (Proof shortened by O'Cat, 28-Nov-2008.)
(ψ → (φ → (ψχ)))       (ψ → (φχ))
 
Theorempm2.43b 46 Inference absorbing redundant antecedent. (Contributed by NM, 31-Oct-1995.)
(ψ → (φ → (ψχ)))       (φ → (ψχ))
 
Theorempm2.43 47 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.)
((φ → (φψ)) → (φψ))
 
Theoremimim2d 48 Deduction adding nested antecedents. (Contributed by NM, 5-Aug-1993.)
(φ → (ψχ))       (φ → ((θψ) → (θχ)))
 
Theoremimim2 49 A closed form of syllogism (see syl 15). Theorem *2.05 of [WhiteheadRussell] p. 100. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 6-Sep-2012.)
((φψ) → ((χφ) → (χψ)))
 
Theoremembantd 50 Deduction embedding an antecedent. (Contributed by Wolf Lammen, 4-Oct-2013.)
(φψ)    &   (φ → (χθ))       (φ → ((ψχ) → θ))
 
Theorem3syld 51 Triple syllogism deduction. (Contributed by Jeff Hankins, 4-Aug-2009.)
(φ → (ψχ))    &   (φ → (χθ))    &   (φ → (θτ))       (φ → (ψτ))
 
Theoremsylsyld 52 Virtual deduction rule e12 without virtual deduction symbols. (Contributed by Alan Sare, 20-Apr-2011.)
(φψ)    &   (φ → (χθ))    &   (ψ → (θτ))       (φ → (χτ))
 
Theoremimim12i 53 Inference joining two implications. (Contributed by NM, 5-Aug-1993.) (Proof shortened by O'Cat, 29-Oct-2011.)
(φψ)    &   (χθ)       ((ψχ) → (φθ))
 
Theoremimim1i 54 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.)
(φψ)       ((ψχ) → (φχ))
 
Theoremimim3i 55 Inference adding three nested antecedents. (Contributed by NM, 19-Dec-2006.)
(φ → (ψχ))       ((θφ) → ((θψ) → (θχ)))
 
Theoremsylc 56 A syllogism inference combined with contraction. (Contributed by NM, 4-May-1994.) (Revised by NM, 13-Jul-2013.)
(φψ)    &   (φχ)    &   (ψ → (χθ))       (φθ)
 
Theoremsyl3c 57 A syllogism inference combined with contraction. e111 without virtual deductions. (Contributed by Alan Sare, 7-Jul-2011.)
(φψ)    &   (φχ)    &   (φθ)    &   (ψ → (χ → (θτ)))       (φτ)
 
Theoremsyl6mpi 58 e20 without virtual deductions. (Contributed by Alan Sare, 8-Jul-2011.) (Proof shortened by Wolf Lammen, 13-Sep-2012.)
(φ → (ψχ))    &   θ    &   (χ → (θτ))       (φ → (ψτ))
 
Theoremmpsyl 59 Modus ponens combined with a syllogism inference. (Contributed by Alan Sare, 20-Apr-2011.)
φ    &   (ψχ)    &   (φ → (χθ))       (ψθ)
 
Theoremsyl6c 60 Inference combining syl6 29 with contraction. (Contributed by Alan Sare, 2-May-2011.)
(φ → (ψχ))    &   (φ → (ψθ))    &   (χ → (θτ))       (φ → (ψτ))
 
Theoremsyldd 61 Nested syllogism deduction. (Contributed by NM, 12-Dec-2004.) (Proof shortened by Wolf Lammen, 11-May-2013.)
(φ → (ψ → (χθ)))    &   (φ → (ψ → (θτ)))       (φ → (ψ → (χτ)))
 
Theoremsyl5d 62 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.)
(φ → (ψχ))    &   (φ → (θ → (χτ)))       (φ → (θ → (ψτ)))
 
Theoremsyl7 63 A syllogism rule of inference. The first premise is used to replace the third antecedent of the second premise. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 3-Aug-2012.)
(φψ)    &   (χ → (θ → (ψτ)))       (χ → (θ → (φτ)))
 
Theoremsyl6d 64 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.)
(φ → (ψ → (χθ)))    &   (φ → (θτ))       (φ → (ψ → (χτ)))
 
Theoremsyl8 65 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.)
(φ → (ψ → (χθ)))    &   (θτ)       (φ → (ψ → (χτ)))
 
Theoremsyl9 66 A nested syllogism inference with different antecedents. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Josh Purinton, 29-Dec-2000.)
(φ → (ψχ))    &   (θ → (χτ))       (φ → (θ → (ψτ)))
 
Theoremsyl9r 67 A nested syllogism inference with different antecedents. (Contributed by NM, 5-Aug-1993.)
(φ → (ψχ))    &   (θ → (χτ))       (θ → (φ → (ψτ)))
 
Theoremimim12d 68 Deduction combining antecedents and consequents. (Contributed by NM, 7-Aug-1994.) (Proof shortened by O'Cat, 30-Oct-2011.)
(φ → (ψχ))    &   (φ → (θτ))       (φ → ((χθ) → (ψτ)))
 
Theoremimim1d 69 Deduction adding nested consequents. (Contributed by NM, 3-Apr-1994.) (Proof shortened by Wolf Lammen, 12-Sep-2012.)
(φ → (ψχ))       (φ → ((χθ) → (ψθ)))
 
Theoremimim1 70 A closed form of syllogism (see syl 15). Theorem *2.06 of [WhiteheadRussell] p. 100. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 25-May-2013.)
((φψ) → ((ψχ) → (φχ)))
 
Theorempm2.83 71 Theorem *2.83 of [WhiteheadRussell] p. 108. (Contributed by NM, 3-Jan-2005.)
((φ → (ψχ)) → ((φ → (χθ)) → (φ → (ψθ))))
 
Theoremcom23 72 Commutation of antecedents. Swap 2nd and 3rd. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 4-Aug-2012.)
(φ → (ψ → (χθ)))       (φ → (χ → (ψθ)))
 
Theoremcom3r 73 Commutation of antecedents. Rotate right. (Contributed by NM, 25-Apr-1994.)
(φ → (ψ → (χθ)))       (χ → (φ → (ψθ)))
 
Theoremcom13 74 Commutation of antecedents. Swap 1st and 3rd. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.)
(φ → (ψ → (χθ)))       (χ → (ψ → (φθ)))
 
Theoremcom3l 75 Commutation of antecedents. Rotate left. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.)
(φ → (ψ → (χθ)))       (ψ → (χ → (φθ)))
 
Theorempm2.04 76 Swap antecedents. Theorem *2.04 of [WhiteheadRussell] p. 100. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 12-Sep-2012.)
((φ → (ψχ)) → (ψ → (φχ)))
 
Theoremcom34 77 Commutation of antecedents. Swap 3rd and 4th. (Contributed by NM, 25-Apr-1994.)
(φ → (ψ → (χ → (θτ))))       (φ → (ψ → (θ → (χτ))))
 
Theoremcom4l 78 Commutation of antecedents. Rotate left. (Contributed by NM, 25-Apr-1994.) (Proof shortened by O'Cat, 15-Aug-2004.)
(φ → (ψ → (χ → (θτ))))       (ψ → (χ → (θ → (φτ))))
 
Theoremcom4t 79 Commutation of antecedents. Rotate twice. (Contributed by NM, 25-Apr-1994.)
(φ → (ψ → (χ → (θτ))))       (χ → (θ → (φ → (ψτ))))
 
Theoremcom4r 80 Commutation of antecedents. Rotate right. (Contributed by NM, 25-Apr-1994.)
(φ → (ψ → (χ → (θτ))))       (θ → (φ → (ψ → (χτ))))
 
Theoremcom24 81 Commutation of antecedents. Swap 2nd and 4th. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.)
(φ → (ψ → (χ → (θτ))))       (φ → (θ → (χ → (ψτ))))
 
Theoremcom14 82 Commutation of antecedents. Swap 1st and 4th. (Contributed by NM, 25-Apr-1994.) (Proof shortened by Wolf Lammen, 28-Jul-2012.)
(φ → (ψ → (χ → (θτ))))       (θ → (ψ → (χ → (φτ))))
 
Theoremcom45 83 Commutation of antecedents. Swap 4th and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.)
(φ → (ψ → (χ → (θ → (τη)))))       (φ → (ψ → (χ → (τ → (θη)))))
 
Theoremcom35 84 Commutation of antecedents. Swap 3rd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.)
(φ → (ψ → (χ → (θ → (τη)))))       (φ → (ψ → (τ → (θ → (χη)))))
 
Theoremcom25 85 Commutation of antecedents. Swap 2nd and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.)
(φ → (ψ → (χ → (θ → (τη)))))       (φ → (τ → (χ → (θ → (ψη)))))
 
Theoremcom5l 86 Commutation of antecedents. Rotate left. (Contributed by Jeff Hankins, 28-Jun-2009.) (Proof shortened by Wolf Lammen, 29-Jul-2012.)
(φ → (ψ → (χ → (θ → (τη)))))       (ψ → (χ → (θ → (τ → (φη)))))
 
Theoremcom15 87 Commutation of antecedents. Swap 1st and 5th. (Contributed by Jeff Hankins, 28-Jun-2009.) (Proof shortened by Wolf Lammen, 29-Jul-2012.)
(φ → (ψ → (χ → (θ → (τη)))))       (τ → (ψ → (χ → (θ → (φη)))))
 
Theoremcom52l 88 Commutation of antecedents. Rotate left twice. (Contributed by Jeff Hankins, 28-Jun-2009.)
(φ → (ψ → (χ → (θ → (τη)))))       (χ → (θ → (τ → (φ → (ψη)))))
 
Theoremcom52r 89 Commutation of antecedents. Rotate right twice. (Contributed by Jeff Hankins, 28-Jun-2009.)
(φ → (ψ → (χ → (θ → (τη)))))       (θ → (τ → (φ → (ψ → (χη)))))
 
Theoremcom5r 90 Commutation of antecedents. Rotate right. (Contributed by Wolf Lammen, 29-Jul-2012.)
(φ → (ψ → (χ → (θ → (τη)))))       (τ → (φ → (ψ → (χ → (θη)))))
 
Theoremjarr 91 Elimination of a nested antecedent as a kind of reversal of inference ja 153. (Contributed by Wolf Lammen, 9-May-2013.)
(((φψ) → χ) → (ψχ))
 
Theorempm2.86i 92 Inference based on pm2.86 94. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 3-Apr-2013.)
((φψ) → (φχ))       (φ → (ψχ))
 
Theorempm2.86d 93 Deduction based on pm2.86 94. (Contributed by NM, 29-Jun-1995.) (Proof shortened by Wolf Lammen, 3-Apr-2013.)
(φ → ((ψχ) → (ψθ)))       (φ → (ψ → (χθ)))
 
Theorempm2.86 94 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.)
(((φψ) → (φχ)) → (φ → (ψχ)))
 
TheoremloolinALT 95 The Linearity Axiom of the infinite-valued sentential logic (L-infinity) of Lukasiewicz. This version of loolin 173 does not use ax-3 7, meaning that this theorem is intuitionistically valid. (Contributed by O'Cat, 12-Aug-2004.) (New usage is discouraged.) (Proof modification is discouraged.)
(((φψ) → (ψφ)) → (ψφ))
 
Theoremloowoz 96 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 negation

This section makes our first use of the third axiom of propositional calculus, ax-3 7.

 
Theoremcon4d 97 Deduction derived from axiom ax-3 7. (Contributed by NM, 26-Mar-1995.)
(φ → (¬ ψ → ¬ χ))       (φ → (χψ))
 
Theorempm2.21d 98 A contradiction implies anything. Deduction from pm2.21 100. (Contributed by NM, 10-Feb-1996.)
(φ → ¬ ψ)       (φ → (ψχ))
 
Theorempm2.21dd 99 A contradiction implies anything. Deduction from pm2.21 100. (Contributed by Mario Carneiro, 9-Feb-2017.)
(φψ)    &   (φ → ¬ ψ)       (φχ)
 
Theorempm2.21 100 From a wff and its negation, anything is true. Theorem *2.21 of [WhiteheadRussell] p. 104. Also called the Duns Scotus law. (Contributed by NM, 5-Aug-1993.) (Proof shortened by Wolf Lammen, 14-Sep-2012.)
φ → (φψ))
    < 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-2000 21 2001-2100 22 2101-2200 23 2201-2300 24 2301-2400 25 2401-2500 26 2501-2600 27 2601-2700 28 2701-2800 29 2801-2900 30 2901-3000 31 3001-3100 32 3101-3200 33 3201-3300 34 3301-3400 35 3401-3500 36 3501-3600 37 3601-3700 38 3701-3800 39 3801-3900 40 3901-4000 41 4001-4100 42 4101-4200 43 4201-4300 44 4301-4400 45 4401-4500 46 4501-4600 47 4601-4700 48 4701-4800 49 4801-4900 50 4901-5000 51 5001-5100 52 5101-5200 53 5201-5300 54 5301-5400 55 5401-5500 56 5501-5600 57 5601-5700 58 5701-5800 59 5801-5900 60 5901-6000 61 6001-6100 62 6101-6200 63 6201-6300 64 6301-6336
  Copyright terms: Public domain < Previous  Next >