Home | Metamath
Proof Explorer Theorem List (p. 19 of 426) | < Previous Next > |
Bad symbols? Try the
GIF version. |
||
Mirrors > Metamath Home Page > MPE Home Page > Theorem List Contents > Recent Proofs This page: Page List |
Color key: | Metamath Proof Explorer
(1-27775) |
Hilbert Space Explorer
(27776-29300) |
Users' Mathboxes
(29301-42551) |
Type | Label | Description |
---|---|---|
Statement | ||
Theorem | 19.29 1801 | Theorem 19.29 of [Margaris] p. 90. See also 19.29r 1802. (Contributed by NM, 21-Jun-1993.) (Proof shortened by Andrew Salmon, 13-May-2011.) |
⊢ ((∀𝑥𝜑 ∧ ∃𝑥𝜓) → ∃𝑥(𝜑 ∧ 𝜓)) | ||
Theorem | 19.29r 1802 | Variation of 19.29 1801. (Contributed by NM, 18-Aug-1993.) (Proof shortened by Wolf Lammen, 12-Nov-2020.) |
⊢ ((∃𝑥𝜑 ∧ ∀𝑥𝜓) → ∃𝑥(𝜑 ∧ 𝜓)) | ||
Theorem | 19.29r2 1803 | Variation of 19.29r 1802 with double quantification. (Contributed by NM, 3-Feb-2005.) |
⊢ ((∃𝑥∃𝑦𝜑 ∧ ∀𝑥∀𝑦𝜓) → ∃𝑥∃𝑦(𝜑 ∧ 𝜓)) | ||
Theorem | 19.29x 1804 | Variation of 19.29 1801 with mixed quantification. (Contributed by NM, 11-Feb-2005.) |
⊢ ((∃𝑥∀𝑦𝜑 ∧ ∀𝑥∃𝑦𝜓) → ∃𝑥∃𝑦(𝜑 ∧ 𝜓)) | ||
Theorem | 19.35 1805 | Theorem 19.35 of [Margaris] p. 90. This theorem is useful for moving an implication (in the form of the right-hand side) into the scope of a single existential quantifier. (Contributed by NM, 12-Mar-1993.) (Proof shortened by Wolf Lammen, 27-Jun-2014.) |
⊢ (∃𝑥(𝜑 → 𝜓) ↔ (∀𝑥𝜑 → ∃𝑥𝜓)) | ||
Theorem | 19.35i 1806 | Inference associated with 19.35 1805. (Contributed by NM, 21-Jun-1993.) |
⊢ ∃𝑥(𝜑 → 𝜓) ⇒ ⊢ (∀𝑥𝜑 → ∃𝑥𝜓) | ||
Theorem | 19.35ri 1807 | Inference associated with 19.35 1805. (Contributed by NM, 12-Mar-1993.) |
⊢ (∀𝑥𝜑 → ∃𝑥𝜓) ⇒ ⊢ ∃𝑥(𝜑 → 𝜓) | ||
Theorem | 19.25 1808 | Theorem 19.25 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) |
⊢ (∀𝑦∃𝑥(𝜑 → 𝜓) → (∃𝑦∀𝑥𝜑 → ∃𝑦∃𝑥𝜓)) | ||
Theorem | 19.30 1809 | Theorem 19.30 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) (Proof shortened by Andrew Salmon, 25-May-2011.) |
⊢ (∀𝑥(𝜑 ∨ 𝜓) → (∀𝑥𝜑 ∨ ∃𝑥𝜓)) | ||
Theorem | 19.43 1810 | Theorem 19.43 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) (Proof shortened by Wolf Lammen, 27-Jun-2014.) |
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (∃𝑥𝜑 ∨ ∃𝑥𝜓)) | ||
Theorem | 19.43OLD 1811 | Obsolete proof of 19.43 1810. Do not delete as it is referenced on the mmrecent.html page and in conventions-label 27259. (Contributed by NM, 5-Aug-1993.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (∃𝑥𝜑 ∨ ∃𝑥𝜓)) | ||
Theorem | 19.33 1812 | Theorem 19.33 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) |
⊢ ((∀𝑥𝜑 ∨ ∀𝑥𝜓) → ∀𝑥(𝜑 ∨ 𝜓)) | ||
Theorem | 19.33b 1813 | The antecedent provides a condition implying the converse of 19.33 1812. (Contributed by NM, 27-Mar-2004.) (Proof shortened by Andrew Salmon, 25-May-2011.) (Proof shortened by Wolf Lammen, 5-Jul-2014.) |
⊢ (¬ (∃𝑥𝜑 ∧ ∃𝑥𝜓) → (∀𝑥(𝜑 ∨ 𝜓) ↔ (∀𝑥𝜑 ∨ ∀𝑥𝜓))) | ||
Theorem | 19.40-2 1814 | Theorem *11.42 in [WhiteheadRussell] p. 163. Theorem 19.40 of [Margaris] p. 90 with two quantifiers. (Contributed by Andrew Salmon, 24-May-2011.) |
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) → (∃𝑥∃𝑦𝜑 ∧ ∃𝑥∃𝑦𝜓)) | ||
Theorem | 19.40b 1815 | The antecedent provides a condition implying the converse of 19.40 1797. This is to 19.40 1797 what 19.33b 1813 is to 19.33 1812. (Contributed by BJ, 6-May-2019.) (Proof shortened by Wolf Lammen, 13-Nov-2020.) |
⊢ ((∀𝑥𝜑 ∨ ∀𝑥𝜓) → ((∃𝑥𝜑 ∧ ∃𝑥𝜓) ↔ ∃𝑥(𝜑 ∧ 𝜓))) | ||
Theorem | albiim 1816 | Split a biconditional and distribute quantifier. (Contributed by NM, 18-Aug-1993.) |
⊢ (∀𝑥(𝜑 ↔ 𝜓) ↔ (∀𝑥(𝜑 → 𝜓) ∧ ∀𝑥(𝜓 → 𝜑))) | ||
Theorem | 2albiim 1817 | Split a biconditional and distribute two quantifiers. (Contributed by NM, 3-Feb-2005.) |
⊢ (∀𝑥∀𝑦(𝜑 ↔ 𝜓) ↔ (∀𝑥∀𝑦(𝜑 → 𝜓) ∧ ∀𝑥∀𝑦(𝜓 → 𝜑))) | ||
Theorem | exintrbi 1818 | Add/remove a conjunct in the scope of an existential quantifier. (Contributed by Raph Levien, 3-Jul-2006.) |
⊢ (∀𝑥(𝜑 → 𝜓) → (∃𝑥𝜑 ↔ ∃𝑥(𝜑 ∧ 𝜓))) | ||
Theorem | exintr 1819 | Introduce a conjunct in the scope of an existential quantifier. (Contributed by NM, 11-Aug-1993.) |
⊢ (∀𝑥(𝜑 → 𝜓) → (∃𝑥𝜑 → ∃𝑥(𝜑 ∧ 𝜓))) | ||
Theorem | alsyl 1820 | Universally quantified and uncurried (imported) form of syllogism. Theorem *10.3 in [WhiteheadRussell] p. 150. (Contributed by Andrew Salmon, 8-Jun-2011.) |
⊢ ((∀𝑥(𝜑 → 𝜓) ∧ ∀𝑥(𝜓 → 𝜒)) → ∀𝑥(𝜑 → 𝜒)) | ||
Theorem | nfimt 1821 | Closed form of nfim 1825 and curried (exported) form of nfimt2 1822. (Contributed by BJ, 20-Oct-2021.) |
⊢ (Ⅎ𝑥𝜑 → (Ⅎ𝑥𝜓 → Ⅎ𝑥(𝜑 → 𝜓))) | ||
Theorem | nfimt2 1822 | Closed form of nfim 1825 and uncurried (imported) form of nfimt 1821. (Contributed by BJ, 20-Oct-2021.) |
⊢ ((Ⅎ𝑥𝜑 ∧ Ⅎ𝑥𝜓) → Ⅎ𝑥(𝜑 → 𝜓)) | ||
Theorem | nfimd 1823 | If in a context 𝑥 is not free in 𝜓 and 𝜒, it is not free in (𝜓 → 𝜒). Deduction form of nfimt 1821. (Contributed by Mario Carneiro, 24-Sep-2016.) (Proof shortened by Wolf Lammen, 30-Dec-2017.) df-nf 1710 changed. (Revised by Wolf Lammen, 18-Sep-2021.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) & ⊢ (𝜑 → Ⅎ𝑥𝜒) ⇒ ⊢ (𝜑 → Ⅎ𝑥(𝜓 → 𝜒)) | ||
Theorem | nfimdOLDOLD 1824 | Obsolete proof of nfimd 1823 as of 3-Nov-2021. (Contributed by Mario Carneiro, 24-Sep-2016.) (Proof shortened by Wolf Lammen, 30-Dec-2017.) df-nf 1710 changed. (Revised by Wolf Lammen, 18-Sep-2021.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) & ⊢ (𝜑 → Ⅎ𝑥𝜒) ⇒ ⊢ (𝜑 → Ⅎ𝑥(𝜓 → 𝜒)) | ||
Theorem | nfim 1825 | If 𝑥 is not free in 𝜑 and 𝜓, it is not free in (𝜑 → 𝜓). Inference associated with nfimt 1821. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof shortened by Wolf Lammen, 2-Jan-2018.) df-nf 1710 changed. (Revised by Wolf Lammen, 17-Sep-2021.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ Ⅎ𝑥(𝜑 → 𝜓) | ||
Theorem | nfand 1826 | If in a context 𝑥 is not free in 𝜓 and 𝜒, it is not free in (𝜓 ∧ 𝜒). (Contributed by Mario Carneiro, 7-Oct-2016.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) & ⊢ (𝜑 → Ⅎ𝑥𝜒) ⇒ ⊢ (𝜑 → Ⅎ𝑥(𝜓 ∧ 𝜒)) | ||
Theorem | nf3and 1827 | Deduction form of bound-variable hypothesis builder nf3an 1831. (Contributed by NM, 17-Feb-2013.) (Revised by Mario Carneiro, 16-Oct-2016.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) & ⊢ (𝜑 → Ⅎ𝑥𝜒) & ⊢ (𝜑 → Ⅎ𝑥𝜃) ⇒ ⊢ (𝜑 → Ⅎ𝑥(𝜓 ∧ 𝜒 ∧ 𝜃)) | ||
Theorem | nfan 1828 | If 𝑥 is not free in 𝜑 and 𝜓, it is not free in (𝜑 ∧ 𝜓). (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof shortened by Wolf Lammen, 13-Jan-2018.) (Proof shortened by Wolf Lammen, 9-Oct-2021.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ Ⅎ𝑥(𝜑 ∧ 𝜓) | ||
Theorem | nfanOLD 1829 | Obsolete proof of nfan 1828 as of 9-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof shortened by Wolf Lammen, 13-Jan-2018.) (New usage is discouraged.) (Proof modification is discouraged.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ Ⅎ𝑥(𝜑 ∧ 𝜓) | ||
Theorem | nfnan 1830 | If 𝑥 is not free in 𝜑 and 𝜓, then it is not free in (𝜑 ⊼ 𝜓). (Contributed by Scott Fenton, 2-Jan-2018.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ Ⅎ𝑥(𝜑 ⊼ 𝜓) | ||
Theorem | nf3an 1831 | If 𝑥 is not free in 𝜑, 𝜓, and 𝜒, it is not free in (𝜑 ∧ 𝜓 ∧ 𝜒). (Contributed by Mario Carneiro, 11-Aug-2016.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 & ⊢ Ⅎ𝑥𝜒 ⇒ ⊢ Ⅎ𝑥(𝜑 ∧ 𝜓 ∧ 𝜒) | ||
Theorem | nfbid 1832 | If in a context 𝑥 is not free in 𝜓 and 𝜒, it is not free in (𝜓 ↔ 𝜒). (Contributed by Mario Carneiro, 24-Sep-2016.) (Proof shortened by Wolf Lammen, 29-Dec-2017.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) & ⊢ (𝜑 → Ⅎ𝑥𝜒) ⇒ ⊢ (𝜑 → Ⅎ𝑥(𝜓 ↔ 𝜒)) | ||
Theorem | nfbi 1833 | If 𝑥 is not free in 𝜑 and 𝜓, it is not free in (𝜑 ↔ 𝜓). (Contributed by NM, 26-May-1993.) (Revised by Mario Carneiro, 11-Aug-2016.) (Proof shortened by Wolf Lammen, 2-Jan-2018.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ Ⅎ𝑥(𝜑 ↔ 𝜓) | ||
Theorem | nfor 1834 | If 𝑥 is not free in 𝜑 and 𝜓, it is not free in (𝜑 ∨ 𝜓). (Contributed by NM, 5-Aug-1993.) (Revised by Mario Carneiro, 11-Aug-2016.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ Ⅎ𝑥(𝜑 ∨ 𝜓) | ||
Theorem | nf3or 1835 | If 𝑥 is not free in 𝜑, 𝜓, and 𝜒, it is not free in (𝜑 ∨ 𝜓 ∨ 𝜒). (Contributed by Mario Carneiro, 11-Aug-2016.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 & ⊢ Ⅎ𝑥𝜒 ⇒ ⊢ Ⅎ𝑥(𝜑 ∨ 𝜓 ∨ 𝜒) | ||
Theorem | nfbiiOLD 1836 | Obsolete proof of nfbii 1778 as of 6-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝜑 ↔ 𝜓) ⇒ ⊢ (Ⅎ𝑥𝜑 ↔ Ⅎ𝑥𝜓) | ||
Theorem | nfxfrOLD 1837 | Obsolete proof of nfxfr 1779 as of 6-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝜑 ↔ 𝜓) & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ Ⅎ𝑥𝜑 | ||
Theorem | nfxfrdOLD 1838 | Obsolete proof of nfxfrd 1780 as of 6-Oct-2021. (Contributed by Mario Carneiro, 24-Sep-2016.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝜑 ↔ 𝜓) & ⊢ (𝜒 → Ⅎ𝑥𝜓) ⇒ ⊢ (𝜒 → Ⅎ𝑥𝜑) | ||
Axiom | ax-5 1839* |
Axiom of Distinctness. This axiom quantifies a variable over a formula
in which it does not occur. Axiom C5 in [Megill] p. 444 (p. 11 of the
preprint). Also appears as Axiom B6 (p. 75) of system S2 of [Tarski]
p. 77 and Axiom C5-1 of [Monk2] p. 113.
(See comments in ax5ALT 34192 about the logical redundancy of ax-5 1839 in the presence of our obsolete axioms.) This axiom essentially says that if 𝑥 does not occur in 𝜑, i.e. 𝜑 does not depend on 𝑥 in any way, then we can add the quantifier ∀𝑥 to 𝜑 with no further assumptions. By sp 2053, we can also remove the quantifier (unconditionally). (Contributed by NM, 10-Jan-1993.) |
⊢ (𝜑 → ∀𝑥𝜑) | ||
Theorem | ax5d 1840* | ax-5 1839 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders. (Contributed by NM, 1-Mar-2013.) |
⊢ (𝜑 → (𝜓 → ∀𝑥𝜓)) | ||
Theorem | ax5e 1841* | A rephrasing of ax-5 1839 using the existential quantifier. (Contributed by Wolf Lammen, 4-Dec-2017.) |
⊢ (∃𝑥𝜑 → 𝜑) | ||
Theorem | ax5ea 1842* | If a formula holds for some value of a variable not occurring in it, then it holds for all values of that variable. (Contributed by BJ, 28-Dec-2020.) |
⊢ (∃𝑥𝜑 → ∀𝑥𝜑) | ||
Theorem | nfv 1843* | If 𝑥 is not present in 𝜑, then 𝑥 is not free in 𝜑. (Contributed by Mario Carneiro, 11-Aug-2016.) Definition change. (Revised by Wolf Lammen, 12-Sep-2021.) |
⊢ Ⅎ𝑥𝜑 | ||
Theorem | nfvd 1844* | nfv 1843 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders such as nfimd 1823. (Contributed by Mario Carneiro, 6-Oct-2016.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) | ||
Theorem | alimdv 1845* | Deduction form of Theorem 19.20 of [Margaris] p. 90, see alim 1738. (Contributed by NM, 3-Apr-1994.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥𝜓 → ∀𝑥𝜒)) | ||
Theorem | eximdv 1846* | Deduction form of Theorem 19.22 of [Margaris] p. 90, see exim 1761. (Contributed by NM, 27-Apr-1994.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 → ∃𝑥𝜒)) | ||
Theorem | 2alimdv 1847* | Deduction form of Theorem 19.20 of [Margaris] p. 90 with two quantifiers, see alim 1738. (Contributed by NM, 27-Apr-2004.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 → ∀𝑥∀𝑦𝜒)) | ||
Theorem | 2eximdv 1848* | Deduction form of Theorem 19.22 of [Margaris] p. 90 with two quantifiers, see exim 1761. (Contributed by NM, 3-Aug-1995.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → ∃𝑥∃𝑦𝜒)) | ||
Theorem | albidv 1849* | Formula-building rule for universal quantifier (deduction rule). (Contributed by NM, 26-May-1993.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥𝜓 ↔ ∀𝑥𝜒)) | ||
Theorem | exbidv 1850* | Formula-building rule for existential quantifier (deduction rule). (Contributed by NM, 26-May-1993.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 ↔ ∃𝑥𝜒)) | ||
Theorem | 2albidv 1851* | Formula-building rule for two universal quantifiers (deduction rule). (Contributed by NM, 4-Mar-1997.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 ↔ ∀𝑥∀𝑦𝜒)) | ||
Theorem | 2exbidv 1852* | Formula-building rule for two existential quantifiers (deduction rule). (Contributed by NM, 1-May-1995.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 ↔ ∃𝑥∃𝑦𝜒)) | ||
Theorem | 3exbidv 1853* | Formula-building rule for three existential quantifiers (deduction rule). (Contributed by NM, 1-May-1995.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧𝜓 ↔ ∃𝑥∃𝑦∃𝑧𝜒)) | ||
Theorem | 4exbidv 1854* | Formula-building rule for four existential quantifiers (deduction rule). (Contributed by NM, 3-Aug-1995.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧∃𝑤𝜓 ↔ ∃𝑥∃𝑦∃𝑧∃𝑤𝜒)) | ||
Theorem | alrimiv 1855* | Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2075 and 19.21v 1868. (Contributed by NM, 21-Jun-1993.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (𝜑 → ∀𝑥𝜓) | ||
Theorem | alrimivv 1856* | Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2075 and 19.21v 1868. (Contributed by NM, 31-Jul-1995.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (𝜑 → ∀𝑥∀𝑦𝜓) | ||
Theorem | alrimdv 1857* | Deduction form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2075 and 19.21v 1868. (Contributed by NM, 10-Feb-1997.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (𝜓 → ∀𝑥𝜒)) | ||
Theorem | exlimiv 1858* |
Inference form of Theorem 19.23 of [Margaris]
p. 90, see 19.23 2080.
See exlimi 2086 for a more general version requiring more axioms. This inference, along with its many variants such as rexlimdv 3030, is used to implement a metatheorem called "Rule C" that is given in many logic textbooks. See, for example, Rule C in [Mendelson] p. 81, Rule C in [Margaris] p. 40, or Rule C in Hirst and Hirst's A Primer for Logic and Proof p. 59 (PDF p. 65) at http://www.appstate.edu/~hirstjl/primer/hirst.pdf. In informal proofs, the statement "Let 𝐶 be an element such that..." almost always means an implicit application of Rule C. In essence, Rule C states that if we can prove that some element 𝑥 exists satisfying a wff, i.e. ∃𝑥𝜑(𝑥) where 𝜑(𝑥) has 𝑥 free, then we can use 𝜑(𝐶) as a hypothesis for the proof where 𝐶 is a new (fictitious) constant not appearing previously in the proof, nor in any axioms used, nor in the theorem to be proved. The purpose of Rule C is to get rid of the existential quantifier. We cannot do this in Metamath directly. Instead, we use the original 𝜑 (containing 𝑥) as an antecedent for the main part of the proof. We eventually arrive at (𝜑 → 𝜓) where 𝜓 is the theorem to be proved and does not contain 𝑥. Then we apply exlimiv 1858 to arrive at (∃𝑥𝜑 → 𝜓). Finally, we separately prove ∃𝑥𝜑 and detach it with modus ponens ax-mp 5 to arrive at the final theorem 𝜓. (Contributed by NM, 21-Jun-1993.) Remove dependencies on ax-6 1888 and ax-8 1992. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (∃𝑥𝜑 → 𝜓) | ||
Theorem | exlimiiv 1859* | Inference associated with exlimiv 1858. (Contributed by BJ, 19-Dec-2020.) |
⊢ (𝜑 → 𝜓) & ⊢ ∃𝑥𝜑 ⇒ ⊢ 𝜓 | ||
Theorem | exlimivv 1860* | Inference form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2080. (Contributed by NM, 1-Aug-1995.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (∃𝑥∃𝑦𝜑 → 𝜓) | ||
Theorem | exlimdv 1861* | Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2080. (Contributed by NM, 27-Apr-1994.) Remove dependencies on ax-6 1888, ax-7 1935. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 → 𝜒)) | ||
Theorem | exlimdvv 1862* | Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2080. (Contributed by NM, 31-Jul-1995.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → 𝜒)) | ||
Theorem | exlimddv 1863* | Existential elimination rule of natural deduction. (Contributed by Mario Carneiro, 15-Jun-2016.) |
⊢ (𝜑 → ∃𝑥𝜓) & ⊢ ((𝜑 ∧ 𝜓) → 𝜒) ⇒ ⊢ (𝜑 → 𝜒) | ||
Theorem | nexdv 1864* | Deduction for generalization rule for negated wff. (Contributed by NM, 5-Aug-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 13-Jul-2020.) (Proof shortened by Wolf Lammen, 10-Oct-2021.) |
⊢ (𝜑 → ¬ 𝜓) ⇒ ⊢ (𝜑 → ¬ ∃𝑥𝜓) | ||
Theorem | nexdvOLD 1865* | Obsolete proof of nexdv 1864 as of 10-Oct-2021. (Contributed by NM, 5-Aug-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 13-Jul-2020.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝜑 → ¬ 𝜓) ⇒ ⊢ (𝜑 → ¬ ∃𝑥𝜓) | ||
Theorem | 2ax5 1866* | Quantification of two variables over a formula in which they do not occur. (Contributed by Alan Sare, 12-Apr-2011.) |
⊢ (𝜑 → ∀𝑥∀𝑦𝜑) | ||
Theorem | stdpc5v 1867* | Version of stdpc5 2076 with a dv condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) Revised to shorten 19.21v 1868. (Revised by Wolf Lammen, 12-Jul-2020.) |
⊢ (∀𝑥(𝜑 → 𝜓) → (𝜑 → ∀𝑥𝜓)) | ||
Theorem | 19.21v 1868* |
Version of 19.21 2075 with a dv condition, requiring fewer axioms.
Notational convention: We sometimes suffix with "v" the label of a theorem using a distinct variable ("dv") condition instead of a non-freeness hypothesis such as Ⅎ𝑥𝜑. Conversely, we sometimes suffix with "f" the label of a theorem introducing such a non-freeness hypothesis ("f" stands for "not free in", see df-nf 1710) instead of a dv condition. For instance, 19.21v 1868 versus 19.21 2075 and vtoclf 3258 versus vtocl 3259. Note that "not free in" is less restrictive than "does not occur in." Note that the version with a dv condition is easily proved from the version with the corresponding non-freeness hypothesis, by using nfv 1843. However, the dv version can often be proved from fewer axioms. (Contributed by NM, 21-Jun-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 2-Jan-2020.) (Proof shortened by Wolf Lammen, 12-Jul-2020.) |
⊢ (∀𝑥(𝜑 → 𝜓) ↔ (𝜑 → ∀𝑥𝜓)) | ||
Theorem | 19.32v 1869* | Version of 19.32 2101 with a dv condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) |
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (𝜑 ∨ ∀𝑥𝜓)) | ||
Theorem | 19.31v 1870* | Version of 19.31 2102 with a dv condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) |
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (∀𝑥𝜑 ∨ 𝜓)) | ||
Theorem | nfvOLD 1871* | Obsolete proof of nfv 1843 as of 5-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ Ⅎ𝑥𝜑 | ||
Theorem | nfvdOLD 1872* | Obsolete proof of nfvd 1844 as of 6-Oct-2021. (Contributed by Mario Carneiro, 6-Oct-2016.) (New usage is discouraged.) (Proof modification is discouraged.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) | ||
Theorem | nfdvOLD 1873* | Obsolete proof of nf5dv 2025 as of 6-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝜑 → (𝜓 → ∀𝑥𝜓)) ⇒ ⊢ (𝜑 → Ⅎ𝑥𝜓) | ||
The equality predicate was introduced above in wceq 1483 for use by df-tru 1486. See the comments in that section. In this section, we continue with the first "real" use of it. | ||
Theorem | weq 1874 |
Extend wff definition to include atomic formulas using the equality
predicate.
(Instead of introducing weq 1874 as an axiomatic statement, as was done in an older version of this database, we introduce it by "proving" a special case of set theory's more general wceq 1483. This lets us avoid overloading the = connective, thus preventing ambiguity that would complicate certain Metamath parsers. However, logically weq 1874 is considered to be a primitive syntax, even though here it is artificially "derived" from wceq 1483. Note: To see the proof steps of this syntax proof, type "show proof weq /all" in the Metamath program.) (Contributed by NM, 24-Jan-2006.) |
wff 𝑥 = 𝑦 | ||
Theorem | equs3 1875 | Lemma used in proofs of substitution properties. (Contributed by NM, 10-May-1993.) |
⊢ (∃𝑥(𝑥 = 𝑦 ∧ 𝜑) ↔ ¬ ∀𝑥(𝑥 = 𝑦 → ¬ 𝜑)) | ||
Theorem | speimfw 1876 | Specialization, with additional weakening (compared to 19.2 1892) to allow bundling of 𝑥 and 𝑦. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 23-Apr-2017.) (Proof shortened by Wolf Lammen, 5-Dec-2017.) |
⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓)) ⇒ ⊢ (¬ ∀𝑥 ¬ 𝑥 = 𝑦 → (∀𝑥𝜑 → ∃𝑥𝜓)) | ||
Theorem | speimfwALT 1877 | Alternate proof of speimfw 1876 (longer compressed proof, but fewer essential steps). (Contributed by NM, 23-Apr-2017.) (Proof shortened by Wolf Lammen, 5-Aug-2017.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓)) ⇒ ⊢ (¬ ∀𝑥 ¬ 𝑥 = 𝑦 → (∀𝑥𝜑 → ∃𝑥𝜓)) | ||
Theorem | spimfw 1878 | Specialization, with additional weakening (compared to sp 2053) to allow bundling of 𝑥 and 𝑦. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 23-Apr-2017.) (Proof shortened by Wolf Lammen, 7-Aug-2017.) |
⊢ (¬ 𝜓 → ∀𝑥 ¬ 𝜓) & ⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓)) ⇒ ⊢ (¬ ∀𝑥 ¬ 𝑥 = 𝑦 → (∀𝑥𝜑 → 𝜓)) | ||
Theorem | ax12i 1879 | Inference that has ax-12 2047 (without ∀𝑦) as its conclusion. Uses only Tarski's FOL axiom schemes. The hypotheses may be eliminable without using ax-12 2047 in special cases. Proof similar to Lemma 16 of [Tarski] p. 70. (Contributed by NM, 20-May-2008.) |
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓)) & ⊢ (𝜓 → ∀𝑥𝜓) ⇒ ⊢ (𝑥 = 𝑦 → (𝜑 → ∀𝑥(𝑥 = 𝑦 → 𝜑))) | ||
Syntax | wsb 1880 | Extend wff definition to include proper substitution (read "the wff that results when 𝑦 is properly substituted for 𝑥 in wff 𝜑"). (Contributed by NM, 24-Jan-2006.) |
wff [𝑦 / 𝑥]𝜑 | ||
Definition | df-sb 1881 |
Define proper substitution. Remark 9.1 in [Megill] p. 447 (p. 15 of the
preprint). For our notation, we use [𝑦 / 𝑥]𝜑 to mean "the wff
that results from the proper substitution of 𝑦 for 𝑥 in the
wff
𝜑." That is, 𝑦
properly replaces 𝑥. For example,
[𝑥 /
𝑦]𝑧 ∈ 𝑦 is the same as 𝑧 ∈ 𝑥, as shown in elsb4 2435. We
can also use [𝑦 / 𝑥]𝜑 in place of the "free for"
side condition
used in traditional predicate calculus; see, for example, stdpc4 2353.
Our notation was introduced in Haskell B. Curry's Foundations of Mathematical Logic (1977), p. 316 and is frequently used in textbooks of lambda calculus and combinatory logic. This notation improves the common but ambiguous notation, "𝜑(𝑦) is the wff that results when 𝑦 is properly substituted for 𝑥 in 𝜑(𝑥)." For example, if the original 𝜑(𝑥) is 𝑥 = 𝑦, then 𝜑(𝑦) is 𝑦 = 𝑦, from which we obtain that 𝜑(𝑥) is 𝑥 = 𝑥. So what exactly does 𝜑(𝑥) mean? Curry's notation solves this problem. In most books, proper substitution has a somewhat complicated recursive definition with multiple cases based on the occurrences of free and bound variables in the wff. Instead, we use a single formula that is exactly equivalent and gives us a direct definition. We later prove that our definition has the properties we expect of proper substitution (see theorems sbequ 2376, sbcom2 2445 and sbid2v 2457). Note that our definition is valid even when 𝑥 and 𝑦 are replaced with the same variable, as sbid 2114 shows. We achieve this by having 𝑥 free in the first conjunct and bound in the second. We can also achieve this by using a dummy variable, as the alternate definition dfsb7 2455 shows (which some logicians may prefer because it doesn't mix free and bound variables). Another version that mixes free and bound variables is dfsb3 2374. When 𝑥 and 𝑦 are distinct, we can express proper substitution with the simpler expressions of sb5 2430 and sb6 2429. There are no restrictions on any of the variables, including what variables may occur in wff 𝜑. (Contributed by NM, 10-May-1993.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ ((𝑥 = 𝑦 → 𝜑) ∧ ∃𝑥(𝑥 = 𝑦 ∧ 𝜑))) | ||
Theorem | sbequ2 1882 | An equality theorem for substitution. (Contributed by NM, 16-May-1993.) (Proof shortened by Wolf Lammen, 25-Feb-2018.) |
⊢ (𝑥 = 𝑦 → ([𝑦 / 𝑥]𝜑 → 𝜑)) | ||
Theorem | sb1 1883 | One direction of a simplified definition of substitution. The converse requires either a dv condition (sb5 2430) or a non-freeness hypothesis (sb5f 2386). (Contributed by NM, 13-May-1993.) |
⊢ ([𝑦 / 𝑥]𝜑 → ∃𝑥(𝑥 = 𝑦 ∧ 𝜑)) | ||
Theorem | spsbe 1884 | A specialization theorem. (Contributed by NM, 29-Jun-1993.) (Proof shortened by Wolf Lammen, 3-May-2018.) |
⊢ ([𝑦 / 𝑥]𝜑 → ∃𝑥𝜑) | ||
Theorem | sbequ8 1885 | Elimination of equality from antecedent after substitution. (Contributed by NM, 5-Aug-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 28-Jul-2018.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥](𝑥 = 𝑦 → 𝜑)) | ||
Theorem | sbimi 1886 | Infer substitution into antecedent and consequent of an implication. (Contributed by NM, 25-Jun-1998.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ ([𝑦 / 𝑥]𝜑 → [𝑦 / 𝑥]𝜓) | ||
Theorem | sbbii 1887 | Infer substitution into both sides of a logical equivalence. (Contributed by NM, 14-May-1993.) |
⊢ (𝜑 ↔ 𝜓) ⇒ ⊢ ([𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜓) | ||
Axiom | ax-6 1888 |
Axiom of Existence. One of the equality and substitution axioms of
predicate calculus with equality. This axiom tells us is that at least
one thing exists. In this form (not requiring that 𝑥 and 𝑦 be
distinct) it was used in an axiom system of Tarski (see Axiom B7' in
footnote 1 of [KalishMontague] p.
81.) It is equivalent to axiom scheme
C10' in [Megill] p. 448 (p. 16 of the
preprint); the equivalence is
established by axc10 2252 and ax6fromc10 34181. A more convenient form of this
axiom is ax6e 2250, which has additional remarks.
Raph Levien proved the independence of this axiom from the other logical axioms on 12-Apr-2005. See item 16 at http://us.metamath.org/award2003.html. ax-6 1888 can be proved from the weaker version ax6v 1889 requiring that the variables be distinct; see theorem ax6 2251. ax-6 1888 can also be proved from the Axiom of Separation (in the form that we use that axiom, where free variables are not universally quantified). See theorem ax6vsep 4785. Except by ax6v 1889, this axiom should not be referenced directly. Instead, use theorem ax6 2251. (Contributed by NM, 10-Jan-1993.) (New usage is discouraged.) |
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦 | ||
Theorem | ax6v 1889* |
Axiom B7 of [Tarski] p. 75, which requires that
𝑥
and 𝑦 be
distinct. This trivial proof is intended merely to weaken axiom ax-6 1888
by adding a distinct variable restriction ($d). From here on, ax-6 1888
should not be referenced directly by any other proof, so that theorem
ax6 2251 will show that we can recover ax-6 1888
from this weaker version if
it were an axiom (as it is in the case of Tarski).
Note: Introducing 𝑥, 𝑦 as a distinct variable group "out of the blue" with no apparent justification has puzzled some people, but it is perfectly sound. All we are doing is adding an additional prerequisite, similar to adding an unnecessary logical hypothesis, that results in a weakening of the theorem. This means that any future theorem that references ax6v 1889 must have a $d specified for the two variables that get substituted for 𝑥 and 𝑦. The $d does not propagate "backwards" i.e. it does not impose a requirement on ax-6 1888. When possible, use of this theorem rather than ax6 2251 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 7-Aug-2015.) |
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦 | ||
Theorem | ax6ev 1890* | At least one individual exists. Weaker version of ax6e 2250. When possible, use of this theorem rather than ax6e 2250 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 3-Aug-2017.) |
⊢ ∃𝑥 𝑥 = 𝑦 | ||
Theorem | exiftru 1891 | Rule of existential generalization, similar to universal generalization ax-gen 1722, but valid only if an individual exists. Its proof requires ax-6 1888 but the equality predicate does not occur in its statement. Some fundamental theorems of predicate logic can be proven from ax-gen 1722, ax-4 1737 and this theorem alone, not requiring ax-7 1935 or excessive distinct variable conditions. (Contributed by Wolf Lammen, 12-Nov-2017.) (Proof shortened by Wolf Lammen, 9-Dec-2017.) |
⊢ 𝜑 ⇒ ⊢ ∃𝑥𝜑 | ||
Theorem | 19.2 1892 | Theorem 19.2 of [Margaris] p. 89. This corresponds to the axiom (D) of modal logic. Note: This proof is very different from Margaris' because we only have Tarski's FOL axiom schemes available at this point. See the later 19.2g 2058 for a more conventional proof of a more general result, which uses additional axioms. The reverse implication is the defining property of effective non-freeness (see df-nf 1710). (Contributed by NM, 2-Aug-2017.) Remove dependency on ax-7 1935. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (∀𝑥𝜑 → ∃𝑥𝜑) | ||
Theorem | 19.2d 1893 | Deduction associated with 19.2 1892. (Contributed by BJ, 12-May-2019.) |
⊢ (𝜑 → ∀𝑥𝜓) ⇒ ⊢ (𝜑 → ∃𝑥𝜓) | ||
Theorem | 19.8w 1894 | Weak version of 19.8a 2052 and instance of 19.2d 1893. (Contributed by NM, 1-Aug-2017.) (Proof shortened by Wolf Lammen, 4-Dec-2017.) (Revised by BJ, 31-Mar-2021.) |
⊢ (𝜑 → ∀𝑥𝜑) ⇒ ⊢ (𝜑 → ∃𝑥𝜑) | ||
Theorem | 19.8v 1895* | Version of 19.8a 2052 with a dv condition, requiring fewer axioms. Converse of ax5e 1841. (Contributed by BJ, 12-Mar-2020.) |
⊢ (𝜑 → ∃𝑥𝜑) | ||
Theorem | 19.9v 1896* | Version of 19.9 2072 with a dv condition, requiring fewer axioms. Any formula can be existentially quantified using a variable which it does not contain. See also 19.3v 1897. (Contributed by NM, 28-May-1995.) Remove dependency on ax-7 1935. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (∃𝑥𝜑 ↔ 𝜑) | ||
Theorem | 19.3v 1897* | Version of 19.3 2069 with a dv condition, requiring fewer axioms. Any formula can be universally quantified using a variable which it does not contain. See also 19.9v 1896. (Contributed by Anthony Hart, 13-Sep-2011.) Remove dependency on ax-7 1935. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (∀𝑥𝜑 ↔ 𝜑) | ||
Theorem | spvw 1898* | Version of sp 2053 when 𝑥 does not occur in 𝜑. Converse of ax-5 1839. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 10-Apr-2017.) (Proof shortened by Wolf Lammen, 4-Dec-2017.) |
⊢ (∀𝑥𝜑 → 𝜑) | ||
Theorem | 19.39 1899 | Theorem 19.39 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) |
⊢ ((∃𝑥𝜑 → ∃𝑥𝜓) → ∃𝑥(𝜑 → 𝜓)) | ||
Theorem | 19.24 1900 | Theorem 19.24 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) |
⊢ ((∀𝑥𝜑 → ∀𝑥𝜓) → ∃𝑥(𝜑 → 𝜓)) |
< Previous Next > |
Copyright terms: Public domain | < Previous Next > |