mmtheorems2 - Metamath Proof Explorer

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-6400 65 6401-6500 66 6501-6600 67 6601-6700 68 6701-6800 69 6801-6900 70 6901-7000 71 7001-7100 72 7101-7200 73 7201-7300 74 7301-7400 75 7401-7500 76 7501-7600 77 7601-7700 78 7701-7800 79 7801-7900 80 7901-8000 81 8001-8100 82 8101-8200 83 8201-8300 84 8301-8400 85 8401-8500 86 8501-8600 87 8601-8700 88 8701-8800 89 8801-8900 90 8901-9000 91 9001-9100 92 9101-9200 93 9201-9300 94 9301-9400 95 9401-9500 96 9501-9600 97 9601-9700 98 9701-9800 99 9801-9900 100 9901-10000 101 10001-10100 102 10101-10200 103 10201-10300 104 10301-10400 105 10401-10500 106 10501-10600 107 10601-10688

Statement List for Metamath Proof Explorer - 101-200 - Page 2 of 107

Type	Label	Description
Statement
Theorem	pm2.51 101	Theorem *2.51 of [WhiteheadRussell] p. 107.
⊢ (¬ (φ → ψ) → (φ → ¬ ψ))
Theorem	pm2.52 102	Theorem *2.52 of [WhiteheadRussell] p. 107.
⊢ (¬ (φ → ψ) → (¬ φ → ¬ ψ))
Theorem	pm2.521 103	Theorem *2.521 of [WhiteheadRussell] p. 107.
⊢ (¬ (φ → ψ) → (ψ → φ))
Theorem	pm2.24i 104	Inference version of pm2.24 79.
⊢ φ    ⇒   ⊢ (¬ φ → ψ)
Theorem	pm2.24d 105	Deduction version of pm2.21 76.
⊢ (φ → ψ)    ⇒   ⊢ (φ → (¬ ψ → χ))
Theorem	mto 106	The rule of modus tollens.
⊢ ¬ ψ    &   ⊢ (φ → ψ)    ⇒   ⊢ ¬ φ
Theorem	mtoi 107	Modus tollens inference.
⊢ ¬ χ    &   ⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → ¬ ψ)
Theorem	mtod 108	Modus tollens deduction.
⊢ (φ → ¬ χ)    &   ⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → ¬ ψ)
Theorem	mt2 109	A rule similar to modus tollens.
⊢ ψ    &   ⊢ (φ → ¬ ψ)    ⇒   ⊢ ¬ φ
Theorem	mt2i 110	Modus tollens inference.
⊢ χ    &   ⊢ (φ → (ψ → ¬ χ))    ⇒   ⊢ (φ → ¬ ψ)
Theorem	mt2d 111	Modus tollens deduction.
⊢ (φ → χ)    &   ⊢ (φ → (ψ → ¬ χ))    ⇒   ⊢ (φ → ¬ ψ)
Theorem	mt3 112	A rule similar to modus tollens.
⊢ ¬ ψ    &   ⊢ (¬ φ → ψ)    ⇒   ⊢ φ
Theorem	mt3i 113	Modus tollens inference.
⊢ ¬ χ    &   ⊢ (φ → (¬ ψ → χ))    ⇒   ⊢ (φ → ψ)
Theorem	mt3d 114	Modus tollens deduction.
⊢ (φ → ¬ χ)    &   ⊢ (φ → (¬ ψ → χ))    ⇒   ⊢ (φ → ψ)
Theorem	mt4d 115	Modus tollens deduction.
⊢ (φ → ψ)    &   ⊢ (φ → (¬ χ → ¬ ψ))    ⇒   ⊢ (φ → χ)
Theorem	nsyl 116	A negated syllogism inference.
⊢ (φ → ¬ ψ)    &   ⊢ (χ → ψ)    ⇒   ⊢ (φ → ¬ χ)
Theorem	nsyld 117	A negated syllogism deduction.
⊢ (φ → (ψ → ¬ χ))    &   ⊢ (φ → (τ → χ))    ⇒   ⊢ (φ → (ψ → ¬ τ))
Theorem	nsyl2 118	A negated syllogism inference.
⊢ (φ → ¬ ψ)    &   ⊢ (¬ χ → ψ)    ⇒   ⊢ (φ → χ)
Theorem	nsyl3 119	A negated syllogism inference.
⊢ (φ → ¬ ψ)    &   ⊢ (χ → ψ)    ⇒   ⊢ (χ → ¬ φ)
Theorem	nsyl4 120	A negated syllogism inference.
⊢ (φ → ψ)    &   ⊢ (¬ φ → χ)    ⇒   ⊢ (¬ χ → ψ)
Theorem	nsyli 121	A negated syllogism inference.
⊢ (φ → (ψ → χ))    &   ⊢ (θ → ¬ χ)    ⇒   ⊢ (φ → (θ → ¬ ψ))
Theorem	pm3.2im 122	Theorem *3.2 of [WhiteheadRussell] p. 111, expressed with primitive connectives. (The proof was shortened by Josh Purinton, 29-Dec-00.)
⊢ (φ → (ψ → ¬ (φ → ¬ ψ)))
Theorem	mth8 123	Theorem 8 of [Margaris] p. 60. (The proof was shortened by Josh Purinton, 29-Dec-00.)
⊢ (φ → (¬ ψ → ¬ (φ → ψ)))
Theorem	pm2.61 124	Theorem *2.61 of [WhiteheadRussell] p. 107. Useful for eliminating an antecedent. (The proof was shortened by O'Cat, 19-Feb-2008.)
⊢ ((φ → ψ) → ((¬ φ → ψ) → ψ))
Theorem	pm2.61-ocatOLD 125	Theorem *2.61 of [WhiteheadRussell] p. 107. Useful for eliminating an antecedent. (The proof was shortened by O'Cat, 19-Feb-2008.)
⊢ ((φ → ψ) → ((¬ φ → ψ) → ψ))
Theorem	pm2.61i 126	Inference eliminating an antecedent.
⊢ (φ → ψ)    &   ⊢ (¬ φ → ψ)    ⇒   ⊢ ψ
Theorem	pm2.61d 127	Deduction eliminating an antecedent.
⊢ (φ → (ψ → χ))    &   ⊢ (φ → (¬ ψ → χ))    ⇒   ⊢ (φ → χ)
Theorem	pm2.61d1 128	Inference eliminating an antecedent.
⊢ (φ → (ψ → χ))    &   ⊢ (¬ ψ → χ)    ⇒   ⊢ (φ → χ)
Theorem	pm2.61d2 129	Inference eliminating an antecedent.
⊢ (φ → (¬ ψ → χ))    &   ⊢ (ψ → χ)    ⇒   ⊢ (φ → χ)
Theorem	pm2.61ii 130	Inference eliminating two antecedents. (The proof was shortened by Josh Purinton, 29-Dec-00.)
⊢ (¬ φ → (¬ ψ → χ))    &   ⊢ (φ → χ)    &   ⊢ (ψ → χ)    ⇒   ⊢ χ
Theorem	pm2.61nii 131	Inference eliminating two antecedents.
⊢ (φ → (ψ → χ))    &   ⊢ (¬ φ → χ)    &   ⊢ (¬ ψ → χ)    ⇒   ⊢ χ
Theorem	pm2.61iii 132	Inference eliminating three antecedents.
⊢ (¬ φ → (¬ ψ → (¬ χ → θ)))    &   ⊢ (φ → θ)    &   ⊢ (ψ → θ)    &   ⊢ (χ → θ)    ⇒   ⊢ θ
Theorem	pm2.6 133	Theorem *2.6 of [WhiteheadRussell] p. 107.
⊢ ((¬ φ → ψ) → ((φ → ψ) → ψ))
Theorem	pm2.65 134	Theorem *2.65 of [WhiteheadRussell] p. 107. Proof by contradiction.
⊢ ((φ → ψ) → ((φ → ¬ ψ) → ¬ φ))
Theorem	pm2.65i 135	Inference rule for proof by contradiction.
⊢ (φ → ψ)    &   ⊢ (φ → ¬ ψ)    ⇒   ⊢ ¬ φ
Theorem	pm2.65d 136	Deduction rule for proof by contradiction.
⊢ (φ → (ψ → χ))    &   ⊢ (φ → (ψ → ¬ χ))    ⇒   ⊢ (φ → ¬ ψ)
Theorem	ja 137	Inference joining the antecedents of two premises. (The proof was shortened by O'Cat, 19-Feb-2008.)
⊢ (¬ φ → χ)    &   ⊢ (ψ → χ)    ⇒   ⊢ ((φ → ψ) → χ)
Theorem	jc 138	Inference joining the consequents of two premises.
⊢ (φ → ψ)    &   ⊢ (φ → χ)    ⇒   ⊢ (φ → ¬ (ψ → ¬ χ))
Theorem	pm3.26im 139	Simplification. Similar to Theorem *3.26 (Simp) of [WhiteheadRussell] p. 112.
⊢ (¬ (φ → ¬ ψ) → φ)
Theorem	pm3.27im 140	Simplification. Similar to Theorem *3.27 (Simp) of [WhiteheadRussell] p. 112.
⊢ (¬ (φ → ¬ ψ) → ψ)
Theorem	impt 141	Importation theorem expressed with primitive connectives.
⊢ ((φ → (ψ → χ)) → (¬ (φ → ¬ ψ) → χ))
Theorem	expt 142	Exportation theorem expressed with primitive connectives.
⊢ ((¬ (φ → ¬ ψ) → χ) → (φ → (ψ → χ)))
Theorem	impi 143	An importation inference.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (¬ (φ → ¬ ψ) → χ)
Theorem	expi 144	An exportation inference.
⊢ (¬ (φ → ¬ ψ) → χ)    ⇒   ⊢ (φ → (ψ → χ))
Theorem	bijust 145	Theorem used to justify definition of biconditional df-bi 147. (The proof was shortened by Josh Purinton, 29-Dec-00.)
⊢ ¬ ((φ → φ) → ¬ (φ → φ))
Logical equivalence
Syntax	wb 146	Extend our wff definition to include the biconditional connective.
wff (φ ↔ ψ)
Definition	df-bi 147	This is our first definition, which introduces and defines the biconditional connective ↔. We define a wff of the form (φ ↔ ψ) as an abbreviation for ¬ ((φ → ψ) → ¬ (ψ → φ)). Unlike most traditional developments, we have chosen not to have a separate symbol such as "Df." to mean "is defined as." Instead, we will later use the biconditional connective for this purpose (df-or 224 is its first use), as it allows us to use logic to manipulate definitions directly. This greatly simplifies many proofs since it eliminates the need for a separate mechanism for introducing and eliminating definitions. Of course, we cannot use this mechanism to define the biconditional itself, since it hasn't been introduced yet. In its most general form, a definition is simply an assertion that introduces a new symbol (or a new combination of existing symbols, as in df-3an 776) that is eliminable and does not strengthen the existing language. The latter requirement means that the set of provable statements not containing the new symbol (or new combination) should remain exactly the same after the definition is introduced. Our definition of the biconditional may look unusual compared to most definitions, but it strictly satisfies these requirements. The justification for our definition is that if we mechanically replace the first wff above (the definiendum i.e. the thing being defined) with the second (the definiens i.e. the defining expression) in the definition, the definition becomes a substitution instance of previously proved theorem bijust 145. It is impossible to use df-bi 147 to prove any statement expressed in the original language that can't be proved from the original axioms. For if it were, we could replace it with instances of bijust 145 throughout the proof, thus obtaining a proof from the original axioms (contradiction). Note that from Metamath's point of view, a definition is just another axiom - i.e. an assertion we claim to be true - but from our high level point of view, we are are not strengthening the language. To indicate this fact, we prefix definition labels with "df-" instead of "ax-". (This prefixing is an informal convention that means nothing to the Metamath proof verifier; it is just for human readability.) See bii 158 and bi 514 for theorems suggesting the typical textbook definition of ↔, showing that our definition has the properties we expect.
⊢ ¬ (((φ ↔ ψ) → ¬ ((φ → ψ) → ¬ (ψ → φ))) → ¬ (¬ ((φ → ψ) → ¬ (ψ → φ)) → (φ ↔ ψ)))
Theorem	bi1 148	Property of the biconditional connective.
⊢ ((φ ↔ ψ) → (φ → ψ))
Theorem	bi2 149	Property of the biconditional connective.
⊢ ((φ ↔ ψ) → (ψ → φ))
Theorem	bi3 150	Property of the biconditional connective.
⊢ ((φ → ψ) → ((ψ → φ) → (φ ↔ ψ)))
Theorem	biimp 151	Infer an implication from a logical equivalence.
⊢ (φ ↔ ψ)    ⇒   ⊢ (φ → ψ)
Theorem	biimpr 152	Infer a converse implication from a logical equivalence.
⊢ (φ ↔ ψ)    ⇒   ⊢ (ψ → φ)
Theorem	biimpd 153	Deduce an implication from a logical equivalence.
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (ψ → χ))
Theorem	biimprd 154	Deduce a converse implication from a logical equivalence.
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (χ → ψ))
Theorem	biimpcd 155	Deduce a commuted implication from a logical equivalence.
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (ψ → (φ → χ))
Theorem	biimprcd 156	Deduce a converse commuted implication from a logical equivalence.
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (χ → (φ → ψ))
Theorem	impbi 157	Infer an equivalence from an implication and its converse.
⊢ (φ → ψ)    &   ⊢ (ψ → φ)    ⇒   ⊢ (φ ↔ ψ)
Theorem	bii 158	Relate the biconditional connective to primitive connectives. See biigb 159 for an unusual version proved directly from axioms.
⊢ ((φ ↔ ψ) ↔ ¬ ((φ → ψ) → ¬ (ψ → φ)))
Theorem	biigb 159	This proof of bii 158, discovered by Gregory Bush on 8-Mar-2004, has several curious properties. First, it has only 17 steps directly from the axioms and df-bi 147, compared to over 800 steps were the proof of bii 158 expanded into axioms. Second, step 2 demands only the property of "true"; any axiom (or theorem) could be used. It might be thought, therefore, that it is in some sense redundant, but in fact no proof is shorter than this (measured by number of steps). Third, it illustrates how intermediate steps can "blow up" in size even in short proofs. Fourth, the compressed proof is only 182 bytes (or 17 bytes in D-proof notation), but the generated web page is over 200kB with intermediate steps that are essentially incomprehensible to humans (other than Gregory Bush). If there were an obfuscated code contest for proofs, this would be a contender.
⊢ ((φ ↔ ψ) ↔ ¬ ((φ → ψ) → ¬ (ψ → φ)))
Theorem	bi2.04 160	Logical equivalence of commuted antecedents. Part of Theorem *4.87 of [WhiteheadRussell] p. 122.
⊢ ((φ → (ψ → χ)) ↔ (ψ → (φ → χ)))
Theorem	pm4.13 161	Double negation. Theorem *4.13 of [WhiteheadRussell] p. 117.
⊢ (φ ↔ ¬ ¬ φ)
Theorem	pm4.8 162	Theorem *4.8 of [WhiteheadRussell] p. 122.
⊢ ((φ → ¬ φ) ↔ ¬ φ)
Theorem	pm4.81 163	Theorem *4.81 of [WhiteheadRussell] p. 122.
⊢ ((¬ φ → φ) ↔ φ)
Theorem	pm4.1 164	Contraposition. Theorem *4.1 of [WhiteheadRussell] p. 116.
⊢ ((φ → ψ) ↔ (¬ ψ → ¬ φ))
Theorem	bi2.03 165	Contraposition. Bidirectional version of con2 90.
⊢ ((φ → ¬ ψ) ↔ (ψ → ¬ φ))
Theorem	bi2.15 166	Contraposition. Bidirectional version of con1 92.
⊢ ((¬ φ → ψ) ↔ (¬ ψ → φ))
Theorem	pm5.4 167	Antecedent absorption implication. Theorem *5.4 of [WhiteheadRussell] p. 125.
⊢ ((φ → (φ → ψ)) ↔ (φ → ψ))
Theorem	imdi 168	Distributive law for implication. Compare Theorem *5.41 of [WhiteheadRussell] p. 125.
⊢ ((φ → (ψ → χ)) ↔ ((φ → ψ) → (φ → χ)))
Theorem	pm5.41 169	Theorem *5.41 of [WhiteheadRussell] p. 125.
⊢ (((φ → ψ) → (φ → χ)) ↔ (φ → (ψ → χ)))
Theorem	pm4.2 170	Principle of identity for logical equivalence. Theorem *4.2 of [WhiteheadRussell] p. 117.
⊢ (φ ↔ φ)
Theorem	pm4.2i 171	Principle of identity with antecedent.
⊢ (φ → (ψ ↔ ψ))
Theorem	bicomi 172	Inference from commutative law for logical equivalence.
⊢ (φ ↔ ψ)    ⇒   ⊢ (ψ ↔ φ)
Theorem	bitr 173	An inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (ψ ↔ χ)    ⇒   ⊢ (φ ↔ χ)
Theorem	bitr2 174	An inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (ψ ↔ χ)    ⇒   ⊢ (χ ↔ φ)
Theorem	bitr3 175	An inference from transitive law for logical equivalence.
⊢ (ψ ↔ φ)    &   ⊢ (ψ ↔ χ)    ⇒   ⊢ (φ ↔ χ)
Theorem	bitr4 176	An inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (χ ↔ ψ)    ⇒   ⊢ (φ ↔ χ)
Theorem	3bitr 177	A chained inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (ψ ↔ χ)    &   ⊢ (χ ↔ θ)    ⇒   ⊢ (φ ↔ θ)
Theorem	3bitrr 178	A chained inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (ψ ↔ χ)    &   ⊢ (χ ↔ θ)    ⇒   ⊢ (θ ↔ φ)
Theorem	3bitr2 179	A chained inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (χ ↔ ψ)    &   ⊢ (χ ↔ θ)    ⇒   ⊢ (φ ↔ θ)
Theorem	3bitr2r 180	A chained inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (χ ↔ ψ)    &   ⊢ (χ ↔ θ)    ⇒   ⊢ (θ ↔ φ)
Theorem	3bitr3 181	A chained inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (φ ↔ χ)    &   ⊢ (ψ ↔ θ)    ⇒   ⊢ (χ ↔ θ)
Theorem	3bitr3r 182	A chained inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (φ ↔ χ)    &   ⊢ (ψ ↔ θ)    ⇒   ⊢ (θ ↔ χ)
Theorem	3bitr4 183	A chained inference from transitive law for logical equivalence. This inference is frequently used to apply a definition to both sides of a logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (χ ↔ φ)    &   ⊢ (θ ↔ ψ)    ⇒   ⊢ (χ ↔ θ)
Theorem	3bitr4r 184	A chained inference from transitive law for logical equivalence.
⊢ (φ ↔ ψ)    &   ⊢ (χ ↔ φ)    &   ⊢ (θ ↔ ψ)    ⇒   ⊢ (θ ↔ χ)
Theorem	imbi2i 185	Introduce an antecedent to both sides of a logical equivalence.
⊢ (φ ↔ ψ)    ⇒   ⊢ ((χ → φ) ↔ (χ → ψ))
Theorem	imbi1i 186	Introduce a consequent to both sides of a logical equivalence.
⊢ (φ ↔ ψ)    ⇒   ⊢ ((φ → χ) ↔ (ψ → χ))
Theorem	negbii 187	Negate both sides of a logical equivalence.
⊢ (φ ↔ ψ)    ⇒   ⊢ (¬ φ ↔ ¬ ψ)
Theorem	imbi12i 188	Join two logical equivalences to form equivalence of implications.
⊢ (φ ↔ ψ)    &   ⊢ (χ ↔ θ)    ⇒   ⊢ ((φ → χ) ↔ (ψ → θ))
Theorem	mpbi 189	An inference from a biconditional, related to modus ponens.
⊢ φ    &   ⊢ (φ ↔ ψ)    ⇒   ⊢ ψ
Theorem	mpbir 190	An inference from a biconditional, related to modus ponens.
⊢ ψ    &   ⊢ (φ ↔ ψ)    ⇒   ⊢ φ
Theorem	mtbi 191	An inference from a biconditional, related to modus tollens.
⊢ ¬ φ    &   ⊢ (φ ↔ ψ)    ⇒   ⊢ ¬ ψ
Theorem	mtbir 192	An inference from a biconditional, related to modus tollens.
⊢ ¬ ψ    &   ⊢ (φ ↔ ψ)    ⇒   ⊢ ¬ φ
Theorem	mpbii 193	An inference from a nested biconditional, related to modus ponens.
⊢ ψ    &   ⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → χ)
Theorem	mpbiri 194	An inference from a nested biconditional, related to modus ponens.
⊢ χ    &   ⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → ψ)
Theorem	mpbid 195	A deduction from a biconditional, related to modus ponens.
⊢ (φ → ψ)    &   ⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → χ)
Theorem	mpbird 196	A deduction from a biconditional, related to modus ponens.
⊢ (φ → χ)    &   ⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → ψ)
Theorem	a1bi 197	Inference rule introducing a theorem as an antecedent.
⊢ φ    ⇒   ⊢ (ψ ↔ (φ → ψ))
Theorem	sylib 198	A mixed syllogism inference from an implication and a biconditional.
⊢ (φ → ψ)    &   ⊢ (ψ ↔ χ)    ⇒   ⊢ (φ → χ)
Theorem	sylbi 199	A mixed syllogism inference from a biconditional and an implication. Useful for substituting an antecedent with a definition.
⊢ (φ ↔ ψ)    &   ⊢ (ψ → χ)    ⇒   ⊢ (φ → χ)
Theorem	sylibr 200	A mixed syllogism inference from an implication and a biconditional. Useful for substituting a consequent with a definition.
⊢ (φ → ψ)    &   ⊢ (χ ↔ ψ)    ⇒   ⊢ (φ → χ)