P. 20 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 1901-2000   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	19.26-3an 1901	Theorem 19.26 1899 with triple conjunction. (Contributed by NM, 13-Sep-2011.)
⊢ (∀𝑥(𝜑 ∧ 𝜓 ∧ 𝜒) ↔ (∀𝑥𝜑 ∧ ∀𝑥𝜓 ∧ ∀𝑥𝜒))
Theorem	19.29 1902	Theorem 19.29 of [Margaris] p. 90. See also 19.29r 1903. (Contributed by NM, 21-Jun-1993.) (Proof shortened by Andrew Salmon, 13-May-2011.)
⊢ ((∀𝑥𝜑 ∧ ∃𝑥𝜓) → ∃𝑥(𝜑 ∧ 𝜓))
Theorem	19.29r 1903	Variation of 19.29 1902. (Contributed by NM, 18-Aug-1993.) (Proof shortened by Wolf Lammen, 12-Nov-2020.)
⊢ ((∃𝑥𝜑 ∧ ∀𝑥𝜓) → ∃𝑥(𝜑 ∧ 𝜓))
Theorem	19.29r2 1904	Variation of 19.29r 1903 with double quantification. (Contributed by NM, 3-Feb-2005.)
⊢ ((∃𝑥∃𝑦𝜑 ∧ ∀𝑥∀𝑦𝜓) → ∃𝑥∃𝑦(𝜑 ∧ 𝜓))
Theorem	19.29x 1905	Variation of 19.29 1902 with mixed quantification. (Contributed by NM, 11-Feb-2005.)
⊢ ((∃𝑥∀𝑦𝜑 ∧ ∀𝑥∃𝑦𝜓) → ∃𝑥∃𝑦(𝜑 ∧ 𝜓))
Theorem	19.35 1906	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 1907	Inference associated with 19.35 1906. (Contributed by NM, 21-Jun-1993.)
⊢ ∃𝑥(𝜑 → 𝜓)    ⇒   ⊢ (∀𝑥𝜑 → ∃𝑥𝜓)
Theorem	19.35ri 1908	Inference associated with 19.35 1906. (Contributed by NM, 12-Mar-1993.)
⊢ (∀𝑥𝜑 → ∃𝑥𝜓)    ⇒   ⊢ ∃𝑥(𝜑 → 𝜓)
Theorem	19.25 1909	Theorem 19.25 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.)
⊢ (∀𝑦∃𝑥(𝜑 → 𝜓) → (∃𝑦∀𝑥𝜑 → ∃𝑦∃𝑥𝜓))
Theorem	19.30 1910	Theorem 19.30 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) (Proof shortened by Andrew Salmon, 25-May-2011.)
⊢ (∀𝑥(𝜑 ∨ 𝜓) → (∀𝑥𝜑 ∨ ∃𝑥𝜓))
Theorem	19.43 1911	Theorem 19.43 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) (Proof shortened by Wolf Lammen, 27-Jun-2014.)
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (∃𝑥𝜑 ∨ ∃𝑥𝜓))
Theorem	19.43OLD 1912	Obsolete proof of 19.43 1911. Do not delete as it is referenced on the mmrecent.html 1911 page and in conventions-labels 30763. (Contributed by NM, 5-Aug-1993.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (∃𝑥𝜑 ∨ ∃𝑥𝜓))
Theorem	19.33 1913	Theorem 19.33 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.)
⊢ ((∀𝑥𝜑 ∨ ∀𝑥𝜓) → ∀𝑥(𝜑 ∨ 𝜓))
Theorem	19.33b 1914	The antecedent provides a condition implying the converse of 19.33 1913. (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 1915	Theorem 19.40 of [Margaris] p. 90. (Contributed by NM, 26-May-1993.)
⊢ (∃𝑥(𝜑 ∧ 𝜓) → (∃𝑥𝜑 ∧ ∃𝑥𝜓))
Theorem	19.40-2 1916	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 1917	The antecedent provides a condition implying the converse of 19.40 1915. This is to 19.40 1915 what 19.33b 1914 is to 19.33 1913. (Contributed by BJ, 6-May-2019.) (Proof shortened by Wolf Lammen, 13-Nov-2020.)
⊢ ((∀𝑥𝜑 ∨ ∀𝑥𝜓) → ((∃𝑥𝜑 ∧ ∃𝑥𝜓) ↔ ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	albiim 1918	Split a biconditional and distribute quantifier. (Contributed by NM, 18-Aug-1993.)
⊢ (∀𝑥(𝜑 ↔ 𝜓) ↔ (∀𝑥(𝜑 → 𝜓) ∧ ∀𝑥(𝜓 → 𝜑)))
Theorem	2albiim 1919	Split a biconditional and distribute two quantifiers. (Contributed by NM, 3-Feb-2005.)
⊢ (∀𝑥∀𝑦(𝜑 ↔ 𝜓) ↔ (∀𝑥∀𝑦(𝜑 → 𝜓) ∧ ∀𝑥∀𝑦(𝜓 → 𝜑)))
Theorem	exintrbi 1920	Add/remove a conjunct in the scope of an existential quantifier. (Contributed by Raph Levien, 3-Jul-2006.)
⊢ (∀𝑥(𝜑 → 𝜓) → (∃𝑥𝜑 ↔ ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	exintr 1921	Introduce a conjunct in the scope of an existential quantifier. (Contributed by NM, 11-Aug-1993.) (Proof shortened by BJ, 16-Sep-2022.)
⊢ (∀𝑥(𝜑 → 𝜓) → (∃𝑥𝜑 → ∃𝑥(𝜑 ∧ 𝜓)))
Theorem	alsyl 1922	Universally quantified and uncurried (imported) form of syllogism. Theorem *10.3 in [WhiteheadRussell] p. 150. (Contributed by Andrew Salmon, 8-Jun-2011.)
⊢ ((∀𝑥(𝜑 → 𝜓) ∧ ∀𝑥(𝜓 → 𝜒)) → ∀𝑥(𝜑 → 𝜒))
Theorem	nfimd 1923	If in a context 𝑥 is not free in 𝜓 and 𝜒, then it is not free in (𝜓 → 𝜒). Deduction form of nfim 1925. (Contributed by Mario Carneiro, 24-Sep-2016.) (Proof shortened by Wolf Lammen, 30-Dec-2017.) df-nf 1813 changed. (Revised by Wolf Lammen, 18-Sep-2021.) Eliminate curried form of nfimt 1924. (Revised by Wolf Lammen, 10-Jul-2022.)
⊢ (𝜑 → Ⅎ𝑥𝜓)    &   ⊢ (𝜑 → Ⅎ𝑥𝜒)    ⇒   ⊢ (𝜑 → Ⅎ𝑥(𝜓 → 𝜒))
Theorem	nfimt 1924	Closed form of nfim 1925 and nfimd 1923. (Contributed by BJ, 20-Oct-2021.) Eliminate curried form, former name nfimt2. (Revised by Wolf Lammen, 6-Jul-2022.)
⊢ ((Ⅎ𝑥𝜑 ∧ Ⅎ𝑥𝜓) → Ⅎ𝑥(𝜑 → 𝜓))
Theorem	nfim 1925	If 𝑥 is not free in 𝜑 and 𝜓, then it is not free in (𝜑 → 𝜓). Inference associated with nfimt 1924. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof shortened by Wolf Lammen, 2-Jan-2018.) df-nf 1813 changed. (Revised by Wolf Lammen, 17-Sep-2021.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    ⇒   ⊢ Ⅎ𝑥(𝜑 → 𝜓)
Theorem	nfand 1926	If in a context 𝑥 is not free in 𝜓 and 𝜒, then it is not free in (𝜓 ∧ 𝜒). (Contributed by Mario Carneiro, 7-Oct-2016.)
⊢ (𝜑 → Ⅎ𝑥𝜓)    &   ⊢ (𝜑 → Ⅎ𝑥𝜒)    ⇒   ⊢ (𝜑 → Ⅎ𝑥(𝜓 ∧ 𝜒))
Theorem	nf3and 1927	Deduction form of bound-variable hypothesis builder nf3an 1930. (Contributed by NM, 17-Feb-2013.) (Revised by Mario Carneiro, 16-Oct-2016.)
⊢ (𝜑 → Ⅎ𝑥𝜓)    &   ⊢ (𝜑 → Ⅎ𝑥𝜒)    &   ⊢ (𝜑 → Ⅎ𝑥𝜃)    ⇒   ⊢ (𝜑 → Ⅎ𝑥(𝜓 ∧ 𝜒 ∧ 𝜃))
Theorem	nfan 1928	If 𝑥 is not free in 𝜑 and 𝜓, then 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	nfnan 1929	If 𝑥 is not free in 𝜑 and 𝜓, then it is not free in (𝜑 ⊼ 𝜓). (Contributed by Scott Fenton, 2-Jan-2018.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    ⇒   ⊢ Ⅎ𝑥(𝜑 ⊼ 𝜓)
Theorem	nf3an 1930	If 𝑥 is not free in 𝜑, 𝜓, and 𝜒, then it is not free in (𝜑 ∧ 𝜓 ∧ 𝜒). (Contributed by Mario Carneiro, 11-Aug-2016.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    &   ⊢ Ⅎ𝑥𝜒    ⇒   ⊢ Ⅎ𝑥(𝜑 ∧ 𝜓 ∧ 𝜒)
Theorem	nfbid 1931	If in a context 𝑥 is not free in 𝜓 and 𝜒, then it is not free in (𝜓 ↔ 𝜒). (Contributed by Mario Carneiro, 24-Sep-2016.) (Proof shortened by Wolf Lammen, 29-Dec-2017.)
⊢ (𝜑 → Ⅎ𝑥𝜓)    &   ⊢ (𝜑 → Ⅎ𝑥𝜒)    ⇒   ⊢ (𝜑 → Ⅎ𝑥(𝜓 ↔ 𝜒))
Theorem	nfbi 1932	If 𝑥 is not free in 𝜑 and 𝜓, then 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 1933	If 𝑥 is not free in 𝜑 and 𝜓, then it is not free in (𝜑 ∨ 𝜓). (Contributed by NM, 5-Aug-1993.) (Revised by Mario Carneiro, 11-Aug-2016.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    ⇒   ⊢ Ⅎ𝑥(𝜑 ∨ 𝜓)
Theorem	nf3or 1934	If 𝑥 is not free in 𝜑, 𝜓, and 𝜒, then it is not free in (𝜑 ∨ 𝜓 ∨ 𝜒). (Contributed by Mario Carneiro, 11-Aug-2016.)
⊢ Ⅎ𝑥𝜑    &   ⊢ Ⅎ𝑥𝜓    &   ⊢ Ⅎ𝑥𝜒    ⇒   ⊢ Ⅎ𝑥(𝜑 ∨ 𝜓 ∨ 𝜒)
1.4.3.1  The empty domain of discourse This database develops mathematics from first-order logic, which has only nonempty models. Before stating axioms excluding the empty model (typically, ax-6 1996 in logic and ax-nul 5268 in set theory), we state in this short subsection a few results relative to the empty domain, which we characterize by the assumption ¬ ∃𝑥⊤. As expected, on the empty domain, every universally quantified formula is true (emptyal 1937) and every existential formula is false (emptyex 1936), and every variable is effectively nonfree in any formula (emptynf 1938).
Theorem	empty 1935	Two characterizations of the empty domain. (Contributed by Gérard Lang, 5-Feb-2024.)
⊢ (¬ ∃𝑥⊤ ↔ ∀𝑥⊥)
Theorem	emptyex 1936	On the empty domain, any existentially quantified formula is false. (Contributed by Wolf Lammen, 21-Jan-2024.)
⊢ (¬ ∃𝑥⊤ → ¬ ∃𝑥𝜑)
Theorem	emptyal 1937	On the empty domain, any universally quantified formula is true. (Contributed by Wolf Lammen, 12-Mar-2023.)
⊢ (¬ ∃𝑥⊤ → ∀𝑥𝜑)
Theorem	emptynf 1938	On the empty domain, any variable is effectively nonfree in any formula. (Contributed by Wolf Lammen, 12-Mar-2023.)
⊢ (¬ ∃𝑥⊤ → Ⅎ𝑥𝜑)
1.4.4  Axiom scheme ax-5 (Distinctness) - first use of $d
Axiom	ax-5 1939*	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 39709 about the logical redundancy of ax-5 1939 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 2218, we can also remove the quantifier (unconditionally). For an explanation of disjoint variable conditions, see https://us.metamath.org/mpeuni/mmset.html#distinct 2218. (Contributed by NM, 10-Jan-1993.)
⊢ (𝜑 → ∀𝑥𝜑)
Theorem	ax5d 1940*	Version of ax-5 1939 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders. (Contributed by NM, 1-Mar-2013.)
⊢ (𝜑 → (𝜓 → ∀𝑥𝜓))
Theorem	ax5e 1941*	A rephrasing of ax-5 1939 using the existential quantifier. (Contributed by Wolf Lammen, 4-Dec-2017.)
⊢ (∃𝑥𝜑 → 𝜑)
Theorem	ax5ea 1942*	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 1943*	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 1944*	nfv 1943 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders such as nfimd 1923. (Contributed by Mario Carneiro, 6-Oct-2016.)
⊢ (𝜑 → Ⅎ𝑥𝜓)
Theorem	alimdv 1945*	Deduction form of Theorem 19.20 of [Margaris] p. 90, see alim 1839. See alimdh 1846 and alimd 2247 for versions without a distinct variable condition. (Contributed by NM, 3-Apr-1994.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥𝜓 → ∀𝑥𝜒))
Theorem	eximdv 1946*	Deduction form of Theorem 19.22 of [Margaris] p. 90, see exim 1863. See eximdh 1893 and eximd 2251 for versions without a distinct variable condition. (Contributed by NM, 27-Apr-1994.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥𝜓 → ∃𝑥𝜒))
Theorem	2alimdv 1947*	Deduction form of Theorem 19.20 of [Margaris] p. 90 with two quantifiers, see alim 1839. (Contributed by NM, 27-Apr-2004.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 → ∀𝑥∀𝑦𝜒))
Theorem	2eximdv 1948*	Deduction form of Theorem 19.22 of [Margaris] p. 90 with two quantifiers, see exim 1863. (Contributed by NM, 3-Aug-1995.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → ∃𝑥∃𝑦𝜒))
Theorem	albidv 1949*	Formula-building rule for universal quantifier (deduction form). See also albidh 1895 and albid 2257. (Contributed by NM, 26-May-1993.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥𝜓 ↔ ∀𝑥𝜒))
Theorem	exbidv 1950*	Formula-building rule for existential quantifier (deduction form). See also exbidh 1896 and exbid 2258. (Contributed by NM, 26-May-1993.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥𝜓 ↔ ∃𝑥𝜒))
Theorem	nfbidv 1951*	An equality theorem for nonfreeness. See nfbidf 2259 for a version without disjoint variable condition but requiring more axioms. (Contributed by Mario Carneiro, 4-Oct-2016.) Remove dependency on ax-6 1996, ax-7 2037, ax-12 2212 by adapting proof of nfbidf 2259. (Revised by BJ, 25-Sep-2022.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (Ⅎ𝑥𝜓 ↔ Ⅎ𝑥𝜒))
Theorem	2albidv 1952*	Formula-building rule for two universal quantifiers (deduction form). (Contributed by NM, 4-Mar-1997.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 ↔ ∀𝑥∀𝑦𝜒))
Theorem	2exbidv 1953*	Formula-building rule for two existential quantifiers (deduction form). (Contributed by NM, 1-May-1995.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 ↔ ∃𝑥∃𝑦𝜒))
Theorem	3exbidv 1954*	Formula-building rule for three existential quantifiers (deduction form). (Contributed by NM, 1-May-1995.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧𝜓 ↔ ∃𝑥∃𝑦∃𝑧𝜒))
Theorem	4exbidv 1955*	Formula-building rule for four existential quantifiers (deduction form). (Contributed by NM, 3-Aug-1995.)
⊢ (𝜑 → (𝜓 ↔ 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧∃𝑤𝜓 ↔ ∃𝑥∃𝑦∃𝑧∃𝑤𝜒))
Theorem	alrimiv 1956*	Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2242 and 19.21v 1968. (Contributed by NM, 21-Jun-1993.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (𝜑 → ∀𝑥𝜓)
Theorem	alrimivv 1957*	Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2242 and 19.21v 1968. (Contributed by NM, 31-Jul-1995.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (𝜑 → ∀𝑥∀𝑦𝜓)
Theorem	alrimdv 1958*	Deduction form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2242 and 19.21v 1968. (Contributed by NM, 10-Feb-1997.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (𝜓 → ∀𝑥𝜒))
Theorem	exlimiv 1959*	Inference form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2246. See exlimi 2252 for a more general version requiring more axioms. This inference, along with its many variants such as rexlimdv 3163, 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 3163. 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 1959 to arrive at (∃𝑥𝜑 → 𝜓). Finally, we separately prove ∃𝑥𝜑 and detach it with modus ponens ax-mp 5 to arrive at the final theorem 𝜓, see exlimiiv 1960. (Contributed by NM, 21-Jun-1993.) Remove dependencies on ax-6 1996 and ax-8 2144. (Revised by Wolf Lammen, 4-Dec-2017.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (∃𝑥𝜑 → 𝜓)
Theorem	exlimiiv 1960*	Inference (Rule C) associated with exlimiv 1959. (Contributed by BJ, 19-Dec-2020.)
⊢ (𝜑 → 𝜓)    &   ⊢ ∃𝑥𝜑    ⇒   ⊢ 𝜓
Theorem	exlimivv 1961*	Inference form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2246. (Contributed by NM, 1-Aug-1995.)
⊢ (𝜑 → 𝜓)    ⇒   ⊢ (∃𝑥∃𝑦𝜑 → 𝜓)
Theorem	exlimdv 1962*	Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2246. (Contributed by NM, 27-Apr-1994.) Remove dependencies on ax-6 1996, ax-7 2037. (Revised by Wolf Lammen, 4-Dec-2017.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥𝜓 → 𝜒))
Theorem	exlimdvv 1963*	Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2246. (Contributed by NM, 31-Jul-1995.)
⊢ (𝜑 → (𝜓 → 𝜒))    ⇒   ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → 𝜒))
Theorem	exlimddv 1964*	Existential elimination rule of natural deduction (Rule C, explained in exlimiv 1959). (Contributed by Mario Carneiro, 15-Jun-2016.)
⊢ (𝜑 → ∃𝑥𝜓)    &   ⊢ ((𝜑 ∧ 𝜓) → 𝜒)    ⇒   ⊢ (𝜑 → 𝜒)
Theorem	nexdv 1965*	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	2ax5 1966*	Quantification of two variables over a formula in which they do not occur. (Contributed by Alan Sare, 12-Apr-2011.)
⊢ (𝜑 → ∀𝑥∀𝑦𝜑)
Theorem	stdpc5v 1967*	Version of stdpc5 2243 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) Revised to shorten 19.21v 1968. (Revised by Wolf Lammen, 12-Jul-2020.)
⊢ (∀𝑥(𝜑 → 𝜓) → (𝜑 → ∀𝑥𝜓))
Theorem	19.21v 1968*	Version of 19.21 2242 with a disjoint variable 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 nonfreeness hypothesis such as Ⅎ𝑥𝜑. Conversely, we sometimes suffix with "f" the label of a theorem introducing such a nonfreeness hypothesis ("f" stands for "not free in", see df-nf 1813) instead of a disjoint variable condition. For instance, 19.21v 1968 versus 19.21 2242 and vtoclf 3529 versus vtocl 3524. Note that "not free in" is less restrictive than "does not occur in". Note that the version with a disjoint variable condition is easily proved from the version with the corresponding nonfreeness hypothesis, by using nfv 1943. 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 1969*	Version of 19.32 2268 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.)
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (𝜑 ∨ ∀𝑥𝜓))
Theorem	19.31v 1970*	Version of 19.31 2269 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.)
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (∀𝑥𝜑 ∨ 𝜓))
Theorem	19.23v 1971*	Version of 19.23 2246 with a disjoint variable condition instead of a nonfreeness hypothesis. (Contributed by NM, 28-Jun-1998.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 11-Jan-2020.) Remove dependency on ax-6 1996. (Revised by Rohan Ridenour, 15-Apr-2022.)
⊢ (∀𝑥(𝜑 → 𝜓) ↔ (∃𝑥𝜑 → 𝜓))
Theorem	19.23vv 1972*	Theorem 19.23v 1971 extended to two variables. (Contributed by NM, 10-Aug-2004.)
⊢ (∀𝑥∀𝑦(𝜑 → 𝜓) ↔ (∃𝑥∃𝑦𝜑 → 𝜓))
Theorem	pm11.53v 1973*	Version of pm11.53 2377 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.)
⊢ (∀𝑥∀𝑦(𝜑 → 𝜓) ↔ (∃𝑥𝜑 → ∀𝑦𝜓))
Theorem	19.36imv 1974*	One direction of 19.36v 2022 that can be proven without ax-6 1996. (Contributed by Rohan Ridenour, 16-Apr-2022.) (Proof shortened by Wolf Lammen, 22-Sep-2024.)
⊢ (∃𝑥(𝜑 → 𝜓) → (∀𝑥𝜑 → 𝜓))
Theorem	19.36iv 1975*	Inference associated with 19.36v 2022. Version of 19.36i 2266 with a disjoint variable condition. (Contributed by NM, 5-Aug-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 17-Jan-2020.) Remove dependency on ax-6 1996. (Revised by Rohan Ridenour, 15-Apr-2022.)
⊢ ∃𝑥(𝜑 → 𝜓)    ⇒   ⊢ (∀𝑥𝜑 → 𝜓)
Theorem	19.37imv 1976*	One direction of 19.37v 2026 that can be proven without ax-6 1996. (Contributed by Rohan Ridenour, 16-Apr-2022.)
⊢ (∃𝑥(𝜑 → 𝜓) → (𝜑 → ∃𝑥𝜓))
Theorem	19.37iv 1977*	Inference associated with 19.37v 2026. (Contributed by NM, 5-Aug-1993.) Remove dependency on ax-6 1996. (Revised by Rohan Ridenour, 15-Apr-2022.)
⊢ ∃𝑥(𝜑 → 𝜓)    ⇒   ⊢ (𝜑 → ∃𝑥𝜓)
Theorem	19.41v 1978*	Version of 19.41 2270 with a disjoint variable condition, requiring fewer axioms. (Contributed by NM, 21-Jun-1993.) Remove dependency on ax-6 1996. (Revised by Rohan Ridenour, 15-Apr-2022.)
⊢ (∃𝑥(𝜑 ∧ 𝜓) ↔ (∃𝑥𝜑 ∧ 𝜓))
Theorem	19.41vv 1979*	Version of 19.41 2270 with two quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by NM, 30-Apr-1995.)
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦𝜑 ∧ 𝜓))
Theorem	19.41vvv 1980*	Version of 19.41 2270 with three quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by NM, 30-Apr-1995.)
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦∃𝑧𝜑 ∧ 𝜓))
Theorem	19.41vvvv 1981*	Version of 19.41 2270 with four quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by FL, 14-Jul-2007.)
⊢ (∃𝑤∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓) ↔ (∃𝑤∃𝑥∃𝑦∃𝑧𝜑 ∧ 𝜓))
Theorem	19.42v 1982*	Version of 19.42 2271 with a disjoint variable condition requiring fewer axioms. (Contributed by NM, 21-Jun-1993.)
⊢ (∃𝑥(𝜑 ∧ 𝜓) ↔ (𝜑 ∧ ∃𝑥𝜓))
Theorem	exdistr 1983*	Distribution of existential quantifiers. See also exdistrv 1984. (Contributed by NM, 9-Mar-1995.)
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ ∃𝑥(𝜑 ∧ ∃𝑦𝜓))
Theorem	exdistrv 1984*	Distribute a pair of existential quantifiers (over disjoint variables) over a conjunction. Combination of 19.41v 1978 and 19.42v 1982. For a version with fewer disjoint variable conditions but requiring more axioms, see eeanv 2380. (Contributed by BJ, 30-Sep-2022.)
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (∃𝑥𝜑 ∧ ∃𝑦𝜓))
Theorem	4exdistrv 1985*	Distribute two pairs of existential quantifiers (over disjoint variables) over a conjunction. For a version with fewer disjoint variable conditions but requiring more axioms, see ee4anv 2382. (Contributed by BJ, 5-Jan-2023.)
⊢ (∃𝑥∃𝑧∃𝑦∃𝑤(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦𝜑 ∧ ∃𝑧∃𝑤𝜓))
Theorem	19.42vv 1986*	Version of 19.42 2271 with two quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by NM, 16-Mar-1995.)
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (𝜑 ∧ ∃𝑥∃𝑦𝜓))
Theorem	exdistr2 1987*	Distribution of existential quantifiers. (Contributed by NM, 17-Mar-1995.)
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓) ↔ ∃𝑥(𝜑 ∧ ∃𝑦∃𝑧𝜓))
Theorem	19.42vvv 1988*	Version of 19.42 2271 with three quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by NM, 21-Sep-2011.) (Proof shortened by Wolf Lammen, 27-Aug-2023.)
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓) ↔ (𝜑 ∧ ∃𝑥∃𝑦∃𝑧𝜓))
Theorem	3exdistr 1989*	Distribution of existential quantifiers in a triple conjunction. (Contributed by NM, 9-Mar-1995.) (Proof shortened by Andrew Salmon, 25-May-2011.)
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓 ∧ 𝜒) ↔ ∃𝑥(𝜑 ∧ ∃𝑦(𝜓 ∧ ∃𝑧𝜒)))
Theorem	4exdistr 1990*	Distribution of existential quantifiers in a quadruple conjunction. (Contributed by NM, 9-Mar-1995.) (Proof shortened by Wolf Lammen, 20-Jan-2018.)
⊢ (∃𝑥∃𝑦∃𝑧∃𝑤((𝜑 ∧ 𝜓) ∧ (𝜒 ∧ 𝜃)) ↔ ∃𝑥(𝜑 ∧ ∃𝑦(𝜓 ∧ ∃𝑧(𝜒 ∧ ∃𝑤𝜃))))
1.4.5  Equality predicate (continued) The equality predicate was introduced above in wceq 1569 for use by df-tru 1572. See the comments in that section. In this section, we continue with its first "real" use.
Theorem	weq 1991	Extend wff definition to include atomic formulas using the equality predicate. (Instead of introducing weq 1991 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 1569. This lets us avoid overloading the = connective, thus preventing ambiguity that would complicate certain Metamath parsers. However, logically weq 1991 is considered to be a primitive syntax, even though here it is artificially "derived" from wceq 1569. Note: To see the proof steps of this syntax proof, type "MM> SHOW PROOF weq / ALL" in the Metamath program.) (Contributed by NM, 24-Jan-2006.)
wff 𝑥 = 𝑦
Theorem	speimfw 1992	Specialization, with additional weakening (compared to 19.2 2005) 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 1993	Alternate proof of speimfw 1992 (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 1994	Specialization, with additional weakening (compared to sp 2218) 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 1995	Inference that has ax-12 2212 (without ∀𝑦) as its conclusion. Uses only Tarski's FOL axiom schemes. The hypotheses may be eliminable without using ax-12 2212 in special cases. Proof similar to Lemma 16 of [Tarski] p. 70. (Contributed by NM, 20-May-2008.)
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓))    &   ⊢ (𝜓 → ∀𝑥𝜓)    ⇒   ⊢ (𝑥 = 𝑦 → (𝜑 → ∀𝑥(𝑥 = 𝑦 → 𝜑)))
1.4.6  Axiom scheme ax-6 (Existence)
Axiom	ax-6 1996	Axiom of Existence. One of the equality and substitution axioms of predicate calculus with equality. This axiom tells us 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 2416 and ax6fromc10 39698. A more convenient form of this axiom is ax6e 2414, 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 https://us.metamath.org/award2003.html 2414. ax-6 1996 can be proved from the weaker version ax6v 1997 requiring that the variables be distinct; see Theorem ax6 2415. ax-6 1996 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 5265. Except by ax6v 1997, this axiom should not be referenced directly. Instead, use Theorem ax6 2415. (Contributed by NM, 10-Jan-1993.) (New usage is discouraged.)
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦
Theorem	ax6v 1997*	Axiom B7 of [Tarski] p. 75, which requires that 𝑥 and 𝑦 be distinct. This trivial proof is intended merely to weaken Axiom ax-6 1996 by adding a distinct variable restriction ($d). From here on, ax-6 1996 should not be referenced directly by any other proof, so that Theorem ax6 2415 will show that we can recover ax-6 1996 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 1997 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 1996. When possible, use of this theorem rather than ax6 2415 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 7-Aug-2015.)
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦
Theorem	ax6ev 1998*	At least one individual exists. Weaker version of ax6e 2414. When possible, use of this theorem rather than ax6e 2414 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 3-Aug-2017.)
⊢ ∃𝑥 𝑥 = 𝑦
Theorem	spimw 1999*	Specialization. Lemma 8 of [KalishMontague] p. 87. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 19-Apr-2017.) (Proof shortened by Wolf Lammen, 7-Aug-2017.)
⊢ (¬ 𝜓 → ∀𝑥 ¬ 𝜓)    &   ⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓))    ⇒   ⊢ (∀𝑥𝜑 → 𝜓)
Theorem	spimew 2000*	Existential introduction, using implicit substitution. Compare Lemma 14 of [Tarski] p. 70. (Contributed by NM, 7-Aug-1994.) (Proof shortened by Wolf Lammen, 22-Oct-2023.)
⊢ (𝜑 → ∀𝑥𝜑)    &   ⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓))    ⇒   ⊢ (𝜑 → ∃𝑥𝜓)