P. 19 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 1801-1900   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	19.33 1801	Theorem 19.33 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.)
⊢ ((∀𝑥𝜑 ∨ ∀𝑥𝜓) → ∀𝑥(𝜑 ∨ 𝜓))
Theorem	19.33b 1802	The antecedent provides a condition implying the converse of 19.33 1801. (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 1803	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 1804	The antecedent provides a condition implying the converse of 19.40 1785. This is to 19.40 1785 what 19.33b 1802 is to 19.33 1801. (Contributed by BJ, 6-May-2019.) (Proof shortened by Wolf Lammen, 13-Nov-2020.)
⊢ ((∀𝑥𝜑 ∨ ∀𝑥𝜓) → ((∃𝑥𝜑 ∧ ∃𝑥𝜓) ↔ ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	19.40bOLD 1805	Obsolete proof of 19.40b 1804 as of 13-Nov-2020. (Contributed by BJ, 6-May-2019.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ ((∀𝑥𝜑 ∨ ∀𝑥𝜓) → ((∃𝑥𝜑 ∧ ∃𝑥𝜓) ↔ ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	albiim 1806	Split a biconditional and distribute quantifier. (Contributed by NM, 18-Aug-1993.)
⊢ (∀𝑥(𝜑 ↔ 𝜓) ↔ (∀𝑥(𝜑 → 𝜓) ∧ ∀𝑥(𝜓 → 𝜑)))
Theorem	2albiim 1807	Split a biconditional and distribute two quantifiers. (Contributed by NM, 3-Feb-2005.)
⊢ (∀𝑥∀𝑦(𝜑 ↔ 𝜓) ↔ (∀𝑥∀𝑦(𝜑 → 𝜓) ∧ ∀𝑥∀𝑦(𝜓 → 𝜑)))
Theorem	exintrbi 1808	Add/remove a conjunct in the scope of an existential quantifier. (Contributed by Raph Levien, 3-Jul-2006.)
⊢ (∀𝑥(𝜑 → 𝜓) → (∃𝑥𝜑 ↔ ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	exintrbiOLD 1809	Obsolete proof of exintrbi 1808 as of 16-Nov-2020. (Contributed by Raph Levien, 3-Jul-2006.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (∀𝑥(𝜑 → 𝜓) → (∃𝑥𝜑 ↔ ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	exintr 1810	Introduce a conjunct in the scope of an existential quantifier. (Contributed by NM, 11-Aug-1993.)
⊢ (∀𝑥(𝜑 → 𝜓) → (∃𝑥𝜑 → ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	alsyl 1811	Theorem *10.3 in [WhiteheadRussell] p. 150. (Contributed by Andrew Salmon, 8-Jun-2011.)
⊢ ((∀𝑥(𝜑 → 𝜓) ∧ ∀𝑥(𝜓 → 𝜒)) → ∀𝑥(𝜑 → 𝜒))
Theorem	nfimd 1812	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, 30-Dec-2017.) df-nf 1701 changed. (Revised by Wolf Lammen, 18-Sep-2021.)
⊢ (𝜑 → Ⅎ𝑥𝜓)    &   ⊢ (𝜑 → Ⅎ𝑥𝜒)    ⇒   ⊢ (𝜑 → Ⅎ𝑥(𝜓 → 𝜒))
Theorem	nfim 1813	If 𝑥 is not free in 𝜑 and 𝜓, it is not free in (𝜑 → 𝜓). (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof shortened by Wolf Lammen, 2-Jan-2018.) df-nf 1701 changed. (Revised by Wolf Lammen, 17-Sep-2021.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    ⇒   ⊢ Ⅎ𝑥(𝜑 → 𝜓)
Theorem	nfand 1814	If in a context 𝑥 is not free in 𝜓 and 𝜒, it is not free in (𝜓 ∧ 𝜒). (Contributed by Mario Carneiro, 7-Oct-2016.)
⊢ (𝜑 → Ⅎ𝑥𝜓)    &   ⊢ (𝜑 → Ⅎ𝑥𝜒)    ⇒   ⊢ (𝜑 → Ⅎ𝑥(𝜓 ∧ 𝜒))
Theorem	nf3and 1815	Deduction form of bound-variable hypothesis builder nf3an 1819. (Contributed by NM, 17-Feb-2013.) (Revised by Mario Carneiro, 16-Oct-2016.)
⊢ (𝜑 → Ⅎ𝑥𝜓)    &   ⊢ (𝜑 → Ⅎ𝑥𝜒)    &   ⊢ (𝜑 → Ⅎ𝑥𝜃)    ⇒   ⊢ (𝜑 → Ⅎ𝑥(𝜓 ∧ 𝜒 ∧ 𝜃))
Theorem	nfan 1816	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 1817	Obsolete proof of nfan 1816 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 1818	If 𝑥 is not free in 𝜑 and 𝜓, then it is not free in (𝜑 ⊼ 𝜓). (Contributed by Scott Fenton, 2-Jan-2018.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    ⇒   ⊢ Ⅎ𝑥(𝜑 ⊼ 𝜓)
Theorem	nf3an 1819	If 𝑥 is not free in 𝜑, 𝜓, and 𝜒, it is not free in (𝜑 ∧ 𝜓 ∧ 𝜒). (Contributed by Mario Carneiro, 11-Aug-2016.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    &   ⊢ Ⅎ𝑥𝜒    ⇒   ⊢ Ⅎ𝑥(𝜑 ∧ 𝜓 ∧ 𝜒)
Theorem	nfbid 1820	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 1821	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 1822	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 1823	If 𝑥 is not free in 𝜑, 𝜓, and 𝜒, it is not free in (𝜑 ∨ 𝜓 ∨ 𝜒). (Contributed by Mario Carneiro, 11-Aug-2016.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    &   ⊢ Ⅎ𝑥𝜒    ⇒   ⊢ Ⅎ𝑥(𝜑 ∨ 𝜓 ∨ 𝜒)
Theorem	nfbiiOLD 1824	Obsolete proof of nfbii 1770 as of 6-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (𝜑 ↔ 𝜓)    ⇒   ⊢ (Ⅎ𝑥𝜑 ↔ Ⅎ𝑥𝜓)
Theorem	nfxfrOLD 1825	Obsolete proof of nfxfr 1771 as of 6-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (𝜑 ↔ 𝜓)    &   ⊢ Ⅎ𝑥𝜓    ⇒   ⊢ Ⅎ𝑥𝜑
Theorem	nfxfrdOLD 1826	Obsolete proof of nfxfrd 1772 as of 6-Oct-2021. (Contributed by Mario Carneiro, 24-Sep-2016.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (𝜑 ↔ 𝜓)    &   ⊢ (𝜒 → Ⅎ𝑥𝜓)    ⇒   ⊢ (𝜒 → Ⅎ𝑥𝜑)
1.4.4  Axiom scheme ax-5 (Distinctness) - first use of $d
Axiom	ax-5 1827*	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 33210 about the logical redundancy of ax-5 1827 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 2041, we can also remove the quantifier (unconditionally). (Contributed by NM, 10-Jan-1993.)
⊢ (𝜑 → ∀𝑥𝜑)
Theorem	ax5d 1828*	ax-5 1827 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders. (Contributed by NM, 1-Mar-2013.)
⊢ (𝜑 → (𝜓 → ∀𝑥𝜓))
Theorem	ax5e 1829*	A rephrasing of ax-5 1827 using the existential quantifier. (Contributed by Wolf Lammen, 4-Dec-2017.)
⊢ (∃𝑥𝜑 → 𝜑)
Theorem	nfv 1830*	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 1831*	nfv 1830 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders such as nfimd 1812. (Contributed by Mario Carneiro, 6-Oct-2016.)
⊢ (𝜑 → Ⅎ𝑥𝜓)
Theorem	alimdv 1832*	Deduction form of Theorem 19.20 of [Margaris] p. 90, see alim 1729. (Contributed by NM, 3-Apr-1994.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥𝜓 → ∀𝑥𝜒))
Theorem	eximdv 1833*	Deduction form of Theorem 19.22 of [Margaris] p. 90, see exim 1751. (Contributed by NM, 27-Apr-1994.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥𝜓 → ∃𝑥𝜒))
Theorem	2alimdv 1834*	Deduction form of Theorem 19.20 of [Margaris] p. 90 with two quantifiers, see alim 1729. (Contributed by NM, 27-Apr-2004.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 → ∀𝑥∀𝑦𝜒))
Theorem	2eximdv 1835*	Deduction form of Theorem 19.22 of [Margaris] p. 90 with two quantifiers, see exim 1751. (Contributed by NM, 3-Aug-1995.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → ∃𝑥∃𝑦𝜒))
Theorem	albidv 1836*	Formula-building rule for universal quantifier (deduction rule). (Contributed by NM, 26-May-1993.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥𝜓 ↔ ∀𝑥𝜒))
Theorem	exbidv 1837*	Formula-building rule for existential quantifier (deduction rule). (Contributed by NM, 26-May-1993.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥𝜓 ↔ ∃𝑥𝜒))
Theorem	2albidv 1838*	Formula-building rule for two universal quantifiers (deduction rule). (Contributed by NM, 4-Mar-1997.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 ↔ ∀𝑥∀𝑦𝜒))
Theorem	2exbidv 1839*	Formula-building rule for two existential quantifiers (deduction rule). (Contributed by NM, 1-May-1995.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 ↔ ∃𝑥∃𝑦𝜒))
Theorem	3exbidv 1840*	Formula-building rule for three existential quantifiers (deduction rule). (Contributed by NM, 1-May-1995.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧𝜓 ↔ ∃𝑥∃𝑦∃𝑧𝜒))
Theorem	4exbidv 1841*	Formula-building rule for four existential quantifiers (deduction rule). (Contributed by NM, 3-Aug-1995.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧∃𝑤𝜓 ↔ ∃𝑥∃𝑦∃𝑧∃𝑤𝜒))
Theorem	alrimiv 1842*	Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2062 and 19.21v 1855. (Contributed by NM, 21-Jun-1993.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (𝜑 → ∀𝑥𝜓)
Theorem	alrimivv 1843*	Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2062 and 19.21v 1855. (Contributed by NM, 31-Jul-1995.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (𝜑 → ∀𝑥∀𝑦𝜓)
Theorem	alrimdv 1844*	Deduction form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2062 and 19.21v 1855. (Contributed by NM, 10-Feb-1997.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (𝜓 → ∀𝑥𝜒))
Theorem	exlimiv 1845*	Inference form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2067. See exlimi 2073 for a more general version requiring more axioms. This inference, along with its many variants such as rexlimdv 3012, 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 1845 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 1875 and ax-8 1979. (Revised by Wolf Lammen, 4-Dec-2017.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (∃𝑥𝜑 → 𝜓)
Theorem	exlimiiv 1846*	Inference associated with exlimiv 1845. (Contributed by BJ, 19-Dec-2020.)
⊢ (𝜑 → 𝜓)    &   ⊢ ∃𝑥𝜑    ⇒   ⊢ 𝜓
Theorem	exlimivv 1847*	Inference form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2067. (Contributed by NM, 1-Aug-1995.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (∃𝑥∃𝑦𝜑 → 𝜓)
Theorem	exlimdv 1848*	Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2067. (Contributed by NM, 27-Apr-1994.) Remove dependencies on ax-6 1875, ax-7 1922. (Revised by Wolf Lammen, 4-Dec-2017.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥𝜓 → 𝜒))
Theorem	exlimdvv 1849*	Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2067. (Contributed by NM, 31-Jul-1995.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → 𝜒))
Theorem	exlimddv 1850*	Existential elimination rule of natural deduction. (Contributed by Mario Carneiro, 15-Jun-2016.)
⊢ (𝜑 → ∃𝑥𝜓)    &   ⊢ ((𝜑 ∧ 𝜓) → 𝜒)    ⇒   ⊢ (𝜑 → 𝜒)
Theorem	nexdv 1851*	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 1852*	Obsolete proof of nexdv 1851 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 1853*	Quantification of two variables over a formula in which they do not occur. (Contributed by Alan Sare, 12-Apr-2011.)
⊢ (𝜑 → ∀𝑥∀𝑦𝜑)
Theorem	stdpc5v 1854*	Version of stdpc5 2063 with a dv condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) Revised to shorten 19.21v 1855. (Revised by Wolf Lammen, 12-Jul-2020.)
⊢ (∀𝑥(𝜑 → 𝜓) → (𝜑 → ∀𝑥𝜓))
Theorem	19.21v 1855*	Version of 19.21 2062 with a dv condition. 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 1701) instead of a dv condition. For instance, 19.21v 1855 versus 19.21 2062 and vtoclf 3231 versus vtocl 3232. 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 1830. 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 1856*	Version of 19.32 2088 with a dv condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.)
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (𝜑 ∨ ∀𝑥𝜓))
Theorem	19.31v 1857*	Version of 19.31 2089 with a dv condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.)
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (∀𝑥𝜑 ∨ 𝜓))
Theorem	nfvOLD 1858*	Obsolete proof of nfv 1830 as of 5-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ Ⅎ𝑥𝜑
Theorem	nfvdOLD 1859*	Obsolete proof of nfvd 1831 as of 6-Oct-2021. (Contributed by Mario Carneiro, 6-Oct-2016.) (New usage is discouraged.) (Proof modification is discouraged.)
⊢ (𝜑 → Ⅎ𝑥𝜓)
Theorem	nfdvOLD 1860*	Obsolete proof of nf5dv 2012 as of 6-Oct-2021. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (𝜑 → (𝜓 → ∀𝑥𝜓))    ⇒   ⊢ (𝜑 → Ⅎ𝑥𝜓)
1.4.5  Equality predicate (continued) The equality predicate was introduced above in wceq 1475 for use by df-tru 1478. See the comments in that section. In this section, we continue with the first "real" use of it.
Theorem	weq 1861	Extend wff definition to include atomic formulas using the equality predicate. (Instead of introducing weq 1861 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 1475. This lets us avoid overloading the = connective, thus preventing ambiguity that would complicate certain Metamath parsers. However, logically weq 1861 is considered to be a primitive syntax, even though here it is artificially "derived" from wceq 1475. 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 1862	Lemma used in proofs of substitution properties. (Contributed by NM, 10-May-1993.)
⊢ (∃𝑥(𝑥 = 𝑦 ∧ 𝜑) ↔ ¬ ∀𝑥(𝑥 = 𝑦 → ¬ 𝜑))
Theorem	speimfw 1863	Specialization, with additional weakening (compared to 19.2 1879) 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 1864	Alternate proof of speimfw 1863 (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 1865	Specialization, with additional weakening (compared to sp 2041) 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 1866	Inference that has ax-12 2034 (without ∀𝑦) as its conclusion. Uses only Tarski's FOL axiom schemes. The hypotheses may be eliminable without using ax-12 2034 in special cases. Proof similar to Lemma 16 of [Tarski] p. 70. (Contributed by NM, 20-May-2008.)
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓))    &   ⊢ (𝜓 → ∀𝑥𝜓)    ⇒   ⊢ (𝑥 = 𝑦 → (𝜑 → ∀𝑥(𝑥 = 𝑦 → 𝜑)))
1.4.6  Define proper substitution
Syntax	wsb 1867	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 1868	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 2423. We can also use [𝑦 / 𝑥]𝜑 in place of the "free for" side condition used in traditional predicate calculus; see, for example, stdpc4 2341. 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 2364, sbcom2 2433 and sbid2v 2445). Note that our definition is valid even when 𝑥 and 𝑦 are replaced with the same variable, as sbid 2100 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 2443 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 2362. When 𝑥 and 𝑦 are distinct, we can express proper substitution with the simpler expressions of sb5 2418 and sb6 2417. There are no restrictions on any of the variables, including what variables may occur in wff 𝜑. (Contributed by NM, 10-May-1993.)
⊢ ([𝑦 / 𝑥]𝜑 ↔ ((𝑥 = 𝑦 → 𝜑) ∧ ∃𝑥(𝑥 = 𝑦 ∧ 𝜑)))
Theorem	sbequ2 1869	An equality theorem for substitution. (Contributed by NM, 16-May-1993.) (Proof shortened by Wolf Lammen, 25-Feb-2018.)
⊢ (𝑥 = 𝑦 → ([𝑦 / 𝑥]𝜑 → 𝜑))
Theorem	sb1 1870	One direction of a simplified definition of substitution. The converse requires either a dv condition (sb5 2418) or a non-freeness hypothesis (sb5f 2374). (Contributed by NM, 13-May-1993.)
⊢ ([𝑦 / 𝑥]𝜑 → ∃𝑥(𝑥 = 𝑦 ∧ 𝜑))
Theorem	spsbe 1871	A specialization theorem. (Contributed by NM, 29-Jun-1993.) (Proof shortened by Wolf Lammen, 3-May-2018.)
⊢ ([𝑦 / 𝑥]𝜑 → ∃𝑥𝜑)
Theorem	sbequ8 1872	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 1873	Infer substitution into antecedent and consequent of an implication. (Contributed by NM, 25-Jun-1998.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ ([𝑦 / 𝑥]𝜑 → [𝑦 / 𝑥]𝜓)
Theorem	sbbii 1874	Infer substitution into both sides of a logical equivalence. (Contributed by NM, 14-May-1993.)
⊢ (𝜑 ↔ 𝜓)    ⇒   ⊢ ([𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜓)
1.4.7  Axiom scheme ax-6 (Existence)
Axiom	ax-6 1875	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 2240 and ax6fromc10 33199. A more convenient form of this axiom is ax6e 2238, 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 1875 can be proved from the weaker version ax6v 1876 requiring that the variables be distinct; see theorem ax6 2239. ax-6 1875 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 4713. Except by ax6v 1876, this axiom should not be referenced directly. Instead, use theorem ax6 2239. (Contributed by NM, 10-Jan-1993.) (New usage is discouraged.)
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦
Theorem	ax6v 1876*	Axiom B7 of [Tarski] p. 75, which requires that 𝑥 and 𝑦 be distinct. This trivial proof is intended merely to weaken axiom ax-6 1875 by adding a distinct variable restriction ($d). From here on, ax-6 1875 should not be referenced directly by any other proof, so that theorem ax6 2239 will show that we can recover ax-6 1875 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 1876 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 1875. When possible, use of this theorem rather than ax6 2239 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 7-Aug-2015.)
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦
Theorem	ax6ev 1877*	At least one individual exists. Weaker version of ax6e 2238. When possible, use of this theorem rather than ax6e 2238 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 3-Aug-2017.)
⊢ ∃𝑥 𝑥 = 𝑦
Theorem	exiftru 1878	Rule of existential generalization, similar to universal generalization ax-gen 1713, but valid only if an individual exists. Its proof requires ax-6 1875 but the equality predicate does not occur in its statement. Some fundamental theorems of predicate logic can be proven from ax-gen 1713, ax-4 1728 and this theorem alone, not requiring ax-7 1922 or excessive distinct variable conditions. (Contributed by Wolf Lammen, 12-Nov-2017.) (Proof shortened by Wolf Lammen, 9-Dec-2017.)
⊢ 𝜑    ⇒   ⊢ ∃𝑥𝜑
Theorem	19.2 1879	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 2046 for a more conventional proof of a more general result, which uses additional axioms. (Contributed by NM, 2-Aug-2017.) Remove dependency on ax-7 1922. (Revised by Wolf Lammen, 4-Dec-2017.)
⊢ (∀𝑥𝜑 → ∃𝑥𝜑)
Theorem	19.2d 1880	Deduction associated with 19.2 1879. (Contributed by BJ, 12-May-2019.)
⊢ (𝜑 → ∀𝑥𝜓)    ⇒   ⊢ (𝜑 → ∃𝑥𝜓)
Theorem	19.8w 1881	Weak version of 19.8a 2039 and instance of 19.2d 1880. (Contributed by NM, 1-Aug-2017.) (Proof shortened by Wolf Lammen, 4-Dec-2017.) (Revised by BJ, 31-Mar-2021.)
⊢ (𝜑 → ∀𝑥𝜑)    ⇒   ⊢ (𝜑 → ∃𝑥𝜑)
Theorem	19.8v 1882*	Version of 19.8a 2039 with a dv condition, requiring fewer axioms. (Contributed by BJ, 12-Mar-2020.)
⊢ (𝜑 → ∃𝑥𝜑)
Theorem	19.9v 1883*	Version of 19.9 2060 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 1884. (Contributed by NM, 28-May-1995.) Remove dependency on ax-7 1922. (Revised by Wolf Lammen, 4-Dec-2017.)
⊢ (∃𝑥𝜑 ↔ 𝜑)
Theorem	19.3v 1884*	Version of 19.3 2057 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 1883. (Contributed by Anthony Hart, 13-Sep-2011.) Remove dependency on ax-7 1922. (Revised by Wolf Lammen, 4-Dec-2017.)
⊢ (∀𝑥𝜑 ↔ 𝜑)
Theorem	spvw 1885*	Version of sp 2041 when 𝑥 does not occur in 𝜑. Converse of ax-5 1827. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 10-Apr-2017.) (Proof shortened by Wolf Lammen, 4-Dec-2017.)
⊢ (∀𝑥𝜑 → 𝜑)
Theorem	19.39 1886	Theorem 19.39 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.)
⊢ ((∃𝑥𝜑 → ∃𝑥𝜓) → ∃𝑥(𝜑 → 𝜓))
Theorem	19.24 1887	Theorem 19.24 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.)
⊢ ((∀𝑥𝜑 → ∀𝑥𝜓) → ∃𝑥(𝜑 → 𝜓))
Theorem	19.34 1888	Theorem 19.34 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.)
⊢ ((∀𝑥𝜑 ∨ ∃𝑥𝜓) → ∃𝑥(𝜑 ∨ 𝜓))
Theorem	19.23v 1889*	Version of 19.23 2067 with a dv condition instead of a non-freeness hypothesis. (Contributed by NM, 28-Jun-1998.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 11-Jan-2020.)
⊢ (∀𝑥(𝜑 → 𝜓) ↔ (∃𝑥𝜑 → 𝜓))
Theorem	19.23vv 1890*	Theorem 19.23v 1889 extended to two variables. (Contributed by NM, 10-Aug-2004.)
⊢ (∀𝑥∀𝑦(𝜑 → 𝜓) ↔ (∃𝑥∃𝑦𝜑 → 𝜓))
Theorem	19.36v 1891*	Version of 19.36 2085 with a dv condition instead of a non-freeness hypothesis. (Contributed by NM, 18-Aug-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 17-Jan-2020.)
⊢ (∃𝑥(𝜑 → 𝜓) ↔ (∀𝑥𝜑 → 𝜓))
Theorem	19.36iv 1892*	Inference associated with 19.36v 1891. Version of 19.36i 2086 with a dv condition. (Contributed by NM, 5-Aug-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 17-Jan-2020.)
⊢ ∃𝑥(𝜑 → 𝜓)    ⇒   ⊢ (∀𝑥𝜑 → 𝜓)
Theorem	pm11.53v 1893*	Version of pm11.53 2167 with a dv condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.)
⊢ (∀𝑥∀𝑦(𝜑 → 𝜓) ↔ (∃𝑥𝜑 → ∀𝑦𝜓))
Theorem	19.12vvv 1894*	Version of 19.12vv 2168 with a dv condition, requiring fewer axioms. See also 19.12 2150. (Contributed by BJ, 18-Mar-2020.)
⊢ (∃𝑥∀𝑦(𝜑 → 𝜓) ↔ ∀𝑦∃𝑥(𝜑 → 𝜓))
Theorem	19.27v 1895*	Version of 19.27 2082 with a dv condition, requiring fewer axioms. (Contributed by NM, 3-Jun-2004.)
⊢ (∀𝑥(𝜑 ∧ 𝜓) ↔ (∀𝑥𝜑 ∧ 𝜓))
Theorem	19.28v 1896*	Version of 19.28 2083 with a dv condition, requiring fewer axioms. (Contributed by NM, 25-Mar-2004.)
⊢ (∀𝑥(𝜑 ∧ 𝜓) ↔ (𝜑 ∧ ∀𝑥𝜓))
Theorem	19.37v 1897*	Version of 19.37 2087 with a dv condition, requiring fewer axioms. (Contributed by NM, 21-Jun-1993.)
⊢ (∃𝑥(𝜑 → 𝜓) ↔ (𝜑 → ∃𝑥𝜓))
Theorem	19.37iv 1898*	Inference associated with 19.37v 1897. (Contributed by NM, 5-Aug-1993.)
⊢ ∃𝑥(𝜑 → 𝜓)    ⇒   ⊢ (𝜑 → ∃𝑥𝜓)
Theorem	19.44v 1899*	Version of 19.44 2093 with a dv condition, requiring fewer axioms. (Contributed by NM, 12-Mar-1993.)
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (∃𝑥𝜑 ∨ 𝜓))
Theorem	19.45v 1900*	Version of 19.45 2094 with a dv condition, requiring fewer axioms. (Contributed by NM, 12-Mar-1993.)
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (𝜑 ∨ ∃𝑥𝜓))