![]() |
Metamath
Proof Explorer Theorem List (p. 20 of 486) | < 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: | ![]() (1-30851) |
![]() (30852-32374) |
![]() (32375-48553) |
Type | Label | Description |
---|---|---|
Statement | ||
Theorem | nf3or 1901 | If 𝑥 is not free in 𝜑, 𝜓, and 𝜒, then it is not free in (𝜑 ∨ 𝜓 ∨ 𝜒). (Contributed by Mario Carneiro, 11-Aug-2016.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑥𝜓 & ⊢ Ⅎ𝑥𝜒 ⇒ ⊢ Ⅎ𝑥(𝜑 ∨ 𝜓 ∨ 𝜒) | ||
This database develops mathematics from first-order logic, which has only nonempty models. Before stating axioms excluding the empty model (typically, ax-6 1964 in logic and ax-nul 5311 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 1904) and every existential formula is false (emptyex 1903), and every variable is effectively nonfree in any formula (emptynf 1905). | ||
Theorem | empty 1902 | Two characterizations of the empty domain. (Contributed by Gérard Lang, 5-Feb-2024.) |
⊢ (¬ ∃𝑥⊤ ↔ ∀𝑥⊥) | ||
Theorem | emptyex 1903 | On the empty domain, any existentially quantified formula is false. (Contributed by Wolf Lammen, 21-Jan-2024.) |
⊢ (¬ ∃𝑥⊤ → ¬ ∃𝑥𝜑) | ||
Theorem | emptyal 1904 | On the empty domain, any universally quantified formula is true. (Contributed by Wolf Lammen, 12-Mar-2023.) |
⊢ (¬ ∃𝑥⊤ → ∀𝑥𝜑) | ||
Theorem | emptynf 1905 | On the empty domain, any variable is effectively nonfree in any formula. (Contributed by Wolf Lammen, 12-Mar-2023.) |
⊢ (¬ ∃𝑥⊤ → Ⅎ𝑥𝜑) | ||
Axiom | ax-5 1906* |
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 38605 about the logical redundancy of ax-5 1906 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 2172, we can also remove the quantifier (unconditionally). For an explanation of disjoint variable conditions, see https://us.metamath.org/mpeuni/mmset.html#distinct 2172. (Contributed by NM, 10-Jan-1993.) |
⊢ (𝜑 → ∀𝑥𝜑) | ||
Theorem | ax5d 1907* | Version of ax-5 1906 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders. (Contributed by NM, 1-Mar-2013.) |
⊢ (𝜑 → (𝜓 → ∀𝑥𝜓)) | ||
Theorem | ax5e 1908* | A rephrasing of ax-5 1906 using the existential quantifier. (Contributed by Wolf Lammen, 4-Dec-2017.) |
⊢ (∃𝑥𝜑 → 𝜑) | ||
Theorem | ax5ea 1909* | 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 1910* | 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 1911* | nfv 1910 with antecedent. Useful in proofs of deduction versions of bound-variable hypothesis builders such as nfimd 1890. (Contributed by Mario Carneiro, 6-Oct-2016.) |
⊢ (𝜑 → Ⅎ𝑥𝜓) | ||
Theorem | alimdv 1912* | Deduction form of Theorem 19.20 of [Margaris] p. 90, see alim 1805. See alimdh 1812 and alimd 2201 for versions without a distinct variable condition. (Contributed by NM, 3-Apr-1994.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥𝜓 → ∀𝑥𝜒)) | ||
Theorem | eximdv 1913* | Deduction form of Theorem 19.22 of [Margaris] p. 90, see exim 1829. See eximdh 1860 and eximd 2205 for versions without a distinct variable condition. (Contributed by NM, 27-Apr-1994.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 → ∃𝑥𝜒)) | ||
Theorem | 2alimdv 1914* | Deduction form of Theorem 19.20 of [Margaris] p. 90 with two quantifiers, see alim 1805. (Contributed by NM, 27-Apr-2004.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 → ∀𝑥∀𝑦𝜒)) | ||
Theorem | 2eximdv 1915* | Deduction form of Theorem 19.22 of [Margaris] p. 90 with two quantifiers, see exim 1829. (Contributed by NM, 3-Aug-1995.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → ∃𝑥∃𝑦𝜒)) | ||
Theorem | albidv 1916* | Formula-building rule for universal quantifier (deduction form). See also albidh 1862 and albid 2211. (Contributed by NM, 26-May-1993.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥𝜓 ↔ ∀𝑥𝜒)) | ||
Theorem | exbidv 1917* | Formula-building rule for existential quantifier (deduction form). See also exbidh 1863 and exbid 2212. (Contributed by NM, 26-May-1993.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 ↔ ∃𝑥𝜒)) | ||
Theorem | nfbidv 1918* | An equality theorem for nonfreeness. See nfbidf 2213 for a version without disjoint variable condition but requiring more axioms. (Contributed by Mario Carneiro, 4-Oct-2016.) Remove dependency on ax-6 1964, ax-7 2004, ax-12 2167 by adapting proof of nfbidf 2213. (Revised by BJ, 25-Sep-2022.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (Ⅎ𝑥𝜓 ↔ Ⅎ𝑥𝜒)) | ||
Theorem | 2albidv 1919* | Formula-building rule for two universal quantifiers (deduction form). (Contributed by NM, 4-Mar-1997.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥∀𝑦𝜓 ↔ ∀𝑥∀𝑦𝜒)) | ||
Theorem | 2exbidv 1920* | Formula-building rule for two existential quantifiers (deduction form). (Contributed by NM, 1-May-1995.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 ↔ ∃𝑥∃𝑦𝜒)) | ||
Theorem | 3exbidv 1921* | Formula-building rule for three existential quantifiers (deduction form). (Contributed by NM, 1-May-1995.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧𝜓 ↔ ∃𝑥∃𝑦∃𝑧𝜒)) | ||
Theorem | 4exbidv 1922* | Formula-building rule for four existential quantifiers (deduction form). (Contributed by NM, 3-Aug-1995.) |
⊢ (𝜑 → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦∃𝑧∃𝑤𝜓 ↔ ∃𝑥∃𝑦∃𝑧∃𝑤𝜒)) | ||
Theorem | alrimiv 1923* | Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2196 and 19.21v 1935. (Contributed by NM, 21-Jun-1993.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (𝜑 → ∀𝑥𝜓) | ||
Theorem | alrimivv 1924* | Inference form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2196 and 19.21v 1935. (Contributed by NM, 31-Jul-1995.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (𝜑 → ∀𝑥∀𝑦𝜓) | ||
Theorem | alrimdv 1925* | Deduction form of Theorem 19.21 of [Margaris] p. 90. See 19.21 2196 and 19.21v 1935. (Contributed by NM, 10-Feb-1997.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (𝜓 → ∀𝑥𝜒)) | ||
Theorem | exlimiv 1926* |
Inference form of Theorem 19.23 of [Margaris]
p. 90, see 19.23 2200.
See exlimi 2206 for a more general version requiring more axioms. This inference, along with its many variants such as rexlimdv 3143, 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 3143. 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 1926 to arrive at (∃𝑥𝜑 → 𝜓). Finally, we separately prove ∃𝑥𝜑 and detach it with modus ponens ax-mp 5 to arrive at the final theorem 𝜓, see exlimiiv 1927. (Contributed by NM, 21-Jun-1993.) Remove dependencies on ax-6 1964 and ax-8 2101. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (∃𝑥𝜑 → 𝜓) | ||
Theorem | exlimiiv 1927* | Inference (Rule C) associated with exlimiv 1926. (Contributed by BJ, 19-Dec-2020.) |
⊢ (𝜑 → 𝜓) & ⊢ ∃𝑥𝜑 ⇒ ⊢ 𝜓 | ||
Theorem | exlimivv 1928* | Inference form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2200. (Contributed by NM, 1-Aug-1995.) |
⊢ (𝜑 → 𝜓) ⇒ ⊢ (∃𝑥∃𝑦𝜑 → 𝜓) | ||
Theorem | exlimdv 1929* | Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2200. (Contributed by NM, 27-Apr-1994.) Remove dependencies on ax-6 1964, ax-7 2004. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 → 𝜒)) | ||
Theorem | exlimdvv 1930* | Deduction form of Theorem 19.23 of [Margaris] p. 90, see 19.23 2200. (Contributed by NM, 31-Jul-1995.) |
⊢ (𝜑 → (𝜓 → 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥∃𝑦𝜓 → 𝜒)) | ||
Theorem | exlimddv 1931* | Existential elimination rule of natural deduction (Rule C, explained in exlimiv 1926). (Contributed by Mario Carneiro, 15-Jun-2016.) |
⊢ (𝜑 → ∃𝑥𝜓) & ⊢ ((𝜑 ∧ 𝜓) → 𝜒) ⇒ ⊢ (𝜑 → 𝜒) | ||
Theorem | nexdv 1932* | 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 1933* | Quantification of two variables over a formula in which they do not occur. (Contributed by Alan Sare, 12-Apr-2011.) |
⊢ (𝜑 → ∀𝑥∀𝑦𝜑) | ||
Theorem | stdpc5v 1934* | Version of stdpc5 2197 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) Revised to shorten 19.21v 1935. (Revised by Wolf Lammen, 12-Jul-2020.) |
⊢ (∀𝑥(𝜑 → 𝜓) → (𝜑 → ∀𝑥𝜓)) | ||
Theorem | 19.21v 1935* |
Version of 19.21 2196 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 1779) instead of a disjoint variable condition. For instance, 19.21v 1935 versus 19.21 2196 and vtoclf 3545 versus vtocl 3538. 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 1910. 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 1936* | Version of 19.32 2222 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) |
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (𝜑 ∨ ∀𝑥𝜓)) | ||
Theorem | 19.31v 1937* | Version of 19.31 2223 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) |
⊢ (∀𝑥(𝜑 ∨ 𝜓) ↔ (∀𝑥𝜑 ∨ 𝜓)) | ||
Theorem | 19.23v 1938* | Version of 19.23 2200 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 1964. (Revised by Rohan Ridenour, 15-Apr-2022.) |
⊢ (∀𝑥(𝜑 → 𝜓) ↔ (∃𝑥𝜑 → 𝜓)) | ||
Theorem | 19.23vv 1939* | Theorem 19.23v 1938 extended to two variables. (Contributed by NM, 10-Aug-2004.) |
⊢ (∀𝑥∀𝑦(𝜑 → 𝜓) ↔ (∃𝑥∃𝑦𝜑 → 𝜓)) | ||
Theorem | pm11.53v 1940* | Version of pm11.53 2337 with a disjoint variable condition, requiring fewer axioms. (Contributed by BJ, 7-Mar-2020.) |
⊢ (∀𝑥∀𝑦(𝜑 → 𝜓) ↔ (∃𝑥𝜑 → ∀𝑦𝜓)) | ||
Theorem | 19.36imv 1941* | One direction of 19.36v 1984 that can be proven without ax-6 1964. (Contributed by Rohan Ridenour, 16-Apr-2022.) (Proof shortened by Wolf Lammen, 22-Sep-2024.) |
⊢ (∃𝑥(𝜑 → 𝜓) → (∀𝑥𝜑 → 𝜓)) | ||
Theorem | 19.36imvOLD 1942* | Obsolete version of 19.36imv 1941 as of 22-Sep-2024. (Contributed by Rohan Ridenour, 16-Apr-2022.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (∃𝑥(𝜑 → 𝜓) → (∀𝑥𝜑 → 𝜓)) | ||
Theorem | 19.36iv 1943* | Inference associated with 19.36v 1984. Version of 19.36i 2220 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 1964. (Revised by Rohan Ridenour, 15-Apr-2022.) |
⊢ ∃𝑥(𝜑 → 𝜓) ⇒ ⊢ (∀𝑥𝜑 → 𝜓) | ||
Theorem | 19.37imv 1944* | One direction of 19.37v 1988 that can be proven without ax-6 1964. (Contributed by Rohan Ridenour, 16-Apr-2022.) |
⊢ (∃𝑥(𝜑 → 𝜓) → (𝜑 → ∃𝑥𝜓)) | ||
Theorem | 19.37iv 1945* | Inference associated with 19.37v 1988. (Contributed by NM, 5-Aug-1993.) Remove dependency on ax-6 1964. (Revised by Rohan Ridenour, 15-Apr-2022.) |
⊢ ∃𝑥(𝜑 → 𝜓) ⇒ ⊢ (𝜑 → ∃𝑥𝜓) | ||
Theorem | 19.41v 1946* | Version of 19.41 2224 with a disjoint variable condition, requiring fewer axioms. (Contributed by NM, 21-Jun-1993.) Remove dependency on ax-6 1964. (Revised by Rohan Ridenour, 15-Apr-2022.) |
⊢ (∃𝑥(𝜑 ∧ 𝜓) ↔ (∃𝑥𝜑 ∧ 𝜓)) | ||
Theorem | 19.41vv 1947* | Version of 19.41 2224 with two quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by NM, 30-Apr-1995.) |
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦𝜑 ∧ 𝜓)) | ||
Theorem | 19.41vvv 1948* | Version of 19.41 2224 with three quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by NM, 30-Apr-1995.) |
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦∃𝑧𝜑 ∧ 𝜓)) | ||
Theorem | 19.41vvvv 1949* | Version of 19.41 2224 with four quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by FL, 14-Jul-2007.) |
⊢ (∃𝑤∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓) ↔ (∃𝑤∃𝑥∃𝑦∃𝑧𝜑 ∧ 𝜓)) | ||
Theorem | 19.42v 1950* | Version of 19.42 2225 with a disjoint variable condition requiring fewer axioms. (Contributed by NM, 21-Jun-1993.) |
⊢ (∃𝑥(𝜑 ∧ 𝜓) ↔ (𝜑 ∧ ∃𝑥𝜓)) | ||
Theorem | exdistr 1951* | Distribution of existential quantifiers. See also exdistrv 1952. (Contributed by NM, 9-Mar-1995.) |
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ ∃𝑥(𝜑 ∧ ∃𝑦𝜓)) | ||
Theorem | exdistrv 1952* | Distribute a pair of existential quantifiers (over disjoint variables) over a conjunction. Combination of 19.41v 1946 and 19.42v 1950. For a version with fewer disjoint variable conditions but requiring more axioms, see eeanv 2340. (Contributed by BJ, 30-Sep-2022.) |
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (∃𝑥𝜑 ∧ ∃𝑦𝜓)) | ||
Theorem | 4exdistrv 1953* | 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 2342. (Contributed by BJ, 5-Jan-2023.) |
⊢ (∃𝑥∃𝑧∃𝑦∃𝑤(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦𝜑 ∧ ∃𝑧∃𝑤𝜓)) | ||
Theorem | 19.42vv 1954* | Version of 19.42 2225 with two quantifiers and a disjoint variable condition requiring fewer axioms. (Contributed by NM, 16-Mar-1995.) |
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (𝜑 ∧ ∃𝑥∃𝑦𝜓)) | ||
Theorem | exdistr2 1955* | Distribution of existential quantifiers. (Contributed by NM, 17-Mar-1995.) |
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓) ↔ ∃𝑥(𝜑 ∧ ∃𝑦∃𝑧𝜓)) | ||
Theorem | 19.42vvv 1956* | Version of 19.42 2225 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 1957* | Distribution of existential quantifiers in a triple conjunction. (Contributed by NM, 9-Mar-1995.) (Proof shortened by Andrew Salmon, 25-May-2011.) |
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓 ∧ 𝜒) ↔ ∃𝑥(𝜑 ∧ ∃𝑦(𝜓 ∧ ∃𝑧𝜒))) | ||
Theorem | 4exdistr 1958* | Distribution of existential quantifiers in a quadruple conjunction. (Contributed by NM, 9-Mar-1995.) (Proof shortened by Wolf Lammen, 20-Jan-2018.) |
⊢ (∃𝑥∃𝑦∃𝑧∃𝑤((𝜑 ∧ 𝜓) ∧ (𝜒 ∧ 𝜃)) ↔ ∃𝑥(𝜑 ∧ ∃𝑦(𝜓 ∧ ∃𝑧(𝜒 ∧ ∃𝑤𝜃)))) | ||
The equality predicate was introduced above in wceq 1534 for use by df-tru 1537. See the comments in that section. In this section, we continue with its first "real" use. | ||
Theorem | weq 1959 |
Extend wff definition to include atomic formulas using the equality
predicate.
(Instead of introducing weq 1959 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 1534. This lets us avoid overloading the = connective, thus preventing ambiguity that would complicate certain Metamath parsers. However, logically weq 1959 is considered to be a primitive syntax, even though here it is artificially "derived" from wceq 1534. 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 1960 | Specialization, with additional weakening (compared to 19.2 1973) 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 1961 | Alternate proof of speimfw 1960 (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 1962 | Specialization, with additional weakening (compared to sp 2172) 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 1963 | Inference that has ax-12 2167 (without ∀𝑦) as its conclusion. Uses only Tarski's FOL axiom schemes. The hypotheses may be eliminable without using ax-12 2167 in special cases. Proof similar to Lemma 16 of [Tarski] p. 70. (Contributed by NM, 20-May-2008.) |
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓)) & ⊢ (𝜓 → ∀𝑥𝜓) ⇒ ⊢ (𝑥 = 𝑦 → (𝜑 → ∀𝑥(𝑥 = 𝑦 → 𝜑))) | ||
Axiom | ax-6 1964 |
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 2379 and ax6fromc10 38594. A more convenient form of this
axiom is ax6e 2377, 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 2377. ax-6 1964 can be proved from the weaker version ax6v 1965 requiring that the variables be distinct; see Theorem ax6 2378. ax-6 1964 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 5308. Except by ax6v 1965, this axiom should not be referenced directly. Instead, use Theorem ax6 2378. (Contributed by NM, 10-Jan-1993.) (New usage is discouraged.) |
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦 | ||
Theorem | ax6v 1965* |
Axiom B7 of [Tarski] p. 75, which requires that
𝑥
and 𝑦 be
distinct. This trivial proof is intended merely to weaken Axiom ax-6 1964
by adding a distinct variable restriction ($d). From here on, ax-6 1964
should not be referenced directly by any other proof, so that Theorem
ax6 2378 will show that we can recover ax-6 1964
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 1965 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 1964. When possible, use of this theorem rather than ax6 2378 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 7-Aug-2015.) |
⊢ ¬ ∀𝑥 ¬ 𝑥 = 𝑦 | ||
Theorem | ax6ev 1966* | At least one individual exists. Weaker version of ax6e 2377. When possible, use of this theorem rather than ax6e 2377 is preferred since its derivation is much shorter and requires fewer axioms. (Contributed by NM, 3-Aug-2017.) |
⊢ ∃𝑥 𝑥 = 𝑦 | ||
Theorem | spimw 1967* | 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 1968* | 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.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓)) ⇒ ⊢ (𝜑 → ∃𝑥𝜓) | ||
Theorem | speiv 1969* | Inference from existential specialization. (Contributed by NM, 19-Aug-1993.) (Revised by Wolf Lammen, 22-Oct-2023.) |
⊢ (𝑥 = 𝑦 → (𝜓 → 𝜑)) & ⊢ 𝜓 ⇒ ⊢ ∃𝑥𝜑 | ||
Theorem | speivw 1970* | Version of spei 2388 with a disjoint variable condition, which does not require ax-13 2366 (neither ax-7 2004 nor ax-12 2167). (Contributed by BJ, 31-May-2019.) |
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓)) & ⊢ 𝜓 ⇒ ⊢ ∃𝑥𝜑 | ||
Theorem | exgen 1971 | Rule of existential generalization, similar to universal generalization ax-gen 1790, but valid only if an individual exists. Its proof requires ax-6 1964 in our axiomatization but the equality predicate does not occur in its statement. Some fundamental theorems of predicate calculus can be proven from ax-gen 1790, ax-4 1804 and this theorem alone, not requiring ax-7 2004 or excessive distinct variable conditions. (Contributed by Wolf Lammen, 12-Nov-2017.) (Proof shortened by Wolf Lammen, 20-Oct-2023.) |
⊢ 𝜑 ⇒ ⊢ ∃𝑥𝜑 | ||
Theorem | extru 1972 | There exists a variable such that ⊤ holds; that is, there exists a variable. This corresponds under the standard translation to one of the formulations of the modal axiom (D), the other being 19.2 1973. (Contributed by Anthony Hart, 13-Sep-2011.) (Proof shortened by BJ, 12-May-2019.) |
⊢ ∃𝑥⊤ | ||
Theorem | 19.2 1973 | Theorem 19.2 of [Margaris] p. 89. This corresponds to the axiom (D) of modal logic (the other standard formulation being extru 1972). 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 2177 for a more conventional proof of a more general result, which uses additional axioms. The reverse implication is the defining property of effective nonfreeness (see df-nf 1779). (Contributed by NM, 2-Aug-2017.) Remove dependency on ax-7 2004. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (∀𝑥𝜑 → ∃𝑥𝜑) | ||
Theorem | 19.2d 1974 | Deduction associated with 19.2 1973. (Contributed by BJ, 12-May-2019.) |
⊢ (𝜑 → ∀𝑥𝜓) ⇒ ⊢ (𝜑 → ∃𝑥𝜓) | ||
Theorem | 19.8w 1975 | Weak version of 19.8a 2170 and instance of 19.2d 1974. (Contributed by NM, 1-Aug-2017.) (Proof shortened by Wolf Lammen, 4-Dec-2017.) (Revised by BJ, 31-Mar-2021.) |
⊢ (𝜑 → ∀𝑥𝜑) ⇒ ⊢ (𝜑 → ∃𝑥𝜑) | ||
Theorem | spnfw 1976 | Weak version of sp 2172. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 1-Aug-2017.) (Proof shortened by Wolf Lammen, 13-Aug-2017.) |
⊢ (¬ 𝜑 → ∀𝑥 ¬ 𝜑) ⇒ ⊢ (∀𝑥𝜑 → 𝜑) | ||
Theorem | spvw 1977* | Version of sp 2172 when 𝑥 does not occur in 𝜑. Converse of ax-5 1906. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 10-Apr-2017.) (Proof shortened by Wolf Lammen, 4-Dec-2017.) Shorten 19.3v 1978. (Revised by Wolf Lammen, 20-Oct-2023.) |
⊢ (∀𝑥𝜑 → 𝜑) | ||
Theorem | 19.3v 1978* | Version of 19.3 2191 with a disjoint variable condition, requiring fewer axioms. Any formula can be universally quantified using a variable which it does not contain. See also 19.9v 1980. (Contributed by Anthony Hart, 13-Sep-2011.) Remove dependency on ax-7 2004. (Revised by Wolf Lammen, 4-Dec-2017.) (Proof shortened by Wolf Lammen, 20-Oct-2023.) |
⊢ (∀𝑥𝜑 ↔ 𝜑) | ||
Theorem | 19.8v 1979* | Version of 19.8a 2170 with a disjoint variable condition, requiring fewer axioms. Converse of ax5e 1908. (Contributed by BJ, 12-Mar-2020.) |
⊢ (𝜑 → ∃𝑥𝜑) | ||
Theorem | 19.9v 1980* | Version of 19.9 2194 with a disjoint variable condition, requiring fewer axioms. Any formula can be existentially quantified using a variable which it does not contain. See also 19.3v 1978. (Contributed by NM, 28-May-1995.) Remove dependency on ax-7 2004. (Revised by Wolf Lammen, 4-Dec-2017.) |
⊢ (∃𝑥𝜑 ↔ 𝜑) | ||
Theorem | 19.39 1981 | Theorem 19.39 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) |
⊢ ((∃𝑥𝜑 → ∃𝑥𝜓) → ∃𝑥(𝜑 → 𝜓)) | ||
Theorem | 19.24 1982 | Theorem 19.24 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) |
⊢ ((∀𝑥𝜑 → ∀𝑥𝜓) → ∃𝑥(𝜑 → 𝜓)) | ||
Theorem | 19.34 1983 | Theorem 19.34 of [Margaris] p. 90. (Contributed by NM, 12-Mar-1993.) |
⊢ ((∀𝑥𝜑 ∨ ∃𝑥𝜓) → ∃𝑥(𝜑 ∨ 𝜓)) | ||
Theorem | 19.36v 1984* | Version of 19.36 2219 with a disjoint variable condition instead of a nonfreeness hypothesis. (Contributed by NM, 18-Aug-1993.) Reduce dependencies on axioms. (Revised by Wolf Lammen, 17-Jan-2020.) |
⊢ (∃𝑥(𝜑 → 𝜓) ↔ (∀𝑥𝜑 → 𝜓)) | ||
Theorem | 19.12vvv 1985* | Version of 19.12vv 2338 with a disjoint variable condition, requiring fewer axioms. See also 19.12 2316. (Contributed by BJ, 18-Mar-2020.) |
⊢ (∃𝑥∀𝑦(𝜑 → 𝜓) ↔ ∀𝑦∃𝑥(𝜑 → 𝜓)) | ||
Theorem | 19.27v 1986* | Version of 19.27 2216 with a disjoint variable condition, requiring fewer axioms. (Contributed by NM, 3-Jun-2004.) |
⊢ (∀𝑥(𝜑 ∧ 𝜓) ↔ (∀𝑥𝜑 ∧ 𝜓)) | ||
Theorem | 19.28v 1987* | Version of 19.28 2217 with a disjoint variable condition, requiring fewer axioms. (Contributed by NM, 25-Mar-2004.) |
⊢ (∀𝑥(𝜑 ∧ 𝜓) ↔ (𝜑 ∧ ∀𝑥𝜓)) | ||
Theorem | 19.37v 1988* | Version of 19.37 2221 with a disjoint variable condition, requiring fewer axioms. (Contributed by NM, 21-Jun-1993.) |
⊢ (∃𝑥(𝜑 → 𝜓) ↔ (𝜑 → ∃𝑥𝜓)) | ||
Theorem | 19.44v 1989* | Version of 19.44 2226 with a disjoint variable condition, requiring fewer axioms. (Contributed by NM, 12-Mar-1993.) |
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (∃𝑥𝜑 ∨ 𝜓)) | ||
Theorem | 19.45v 1990* | Version of 19.45 2227 with a disjoint variable condition, requiring fewer axioms. (Contributed by NM, 12-Mar-1993.) |
⊢ (∃𝑥(𝜑 ∨ 𝜓) ↔ (𝜑 ∨ ∃𝑥𝜓)) | ||
Theorem | spimevw 1991* | Existential introduction, using implicit substitution. This is to spimew 1968 what spimvw 1992 is to spimw 1967. Version of spimev 2386 and spimefv 2187 with an additional disjoint variable condition, using only Tarski's FOL axiom schemes. (Contributed by NM, 10-Jan-1993.) (Revised by BJ, 17-Mar-2020.) |
⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓)) ⇒ ⊢ (𝜑 → ∃𝑥𝜓) | ||
Theorem | spimvw 1992* | A weak form of specialization. Lemma 8 of [KalishMontague] p. 87. Uses only Tarski's FOL axiom schemes. For stronger forms using more axioms, see spimv 2384 and spimfv 2228. (Contributed by NM, 9-Apr-2017.) |
⊢ (𝑥 = 𝑦 → (𝜑 → 𝜓)) ⇒ ⊢ (∀𝑥𝜑 → 𝜓) | ||
Theorem | spvv 1993* | Specialization, using implicit substitution. Version of spv 2387 with a disjoint variable condition, which does not require ax-7 2004, ax-12 2167, ax-13 2366. (Contributed by NM, 30-Aug-1993.) (Revised by BJ, 31-May-2019.) |
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓)) ⇒ ⊢ (∀𝑥𝜑 → 𝜓) | ||
Theorem | spfalw 1994 | Version of sp 2172 when 𝜑 is false. Uses only Tarski's FOL axiom schemes. (Contributed by NM, 23-Apr-2017.) (Proof shortened by Wolf Lammen, 25-Dec-2017.) |
⊢ ¬ 𝜑 ⇒ ⊢ (∀𝑥𝜑 → 𝜑) | ||
Theorem | chvarvv 1995* | Implicit substitution of 𝑦 for 𝑥 into a theorem. Version of chvarv 2390 with a disjoint variable condition, which does not require ax-13 2366. (Contributed by NM, 20-Apr-1994.) (Revised by BJ, 31-May-2019.) |
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓)) & ⊢ 𝜑 ⇒ ⊢ 𝜓 | ||
Theorem | equs4v 1996* | Version of equs4 2410 with a disjoint variable condition, which requires fewer axioms. (Contributed by NM, 10-May-1993.) (Revised by BJ, 31-May-2019.) |
⊢ (∀𝑥(𝑥 = 𝑦 → 𝜑) → ∃𝑥(𝑥 = 𝑦 ∧ 𝜑)) | ||
Theorem | alequexv 1997* | Version of equs4v 1996 with its consequence simplified by exsimpr 1865. (Contributed by BJ, 9-Nov-2021.) |
⊢ (∀𝑥(𝑥 = 𝑦 → 𝜑) → ∃𝑥𝜑) | ||
Theorem | exsbim 1998* | One direction of the equivalence in exsb 2350 is based on fewer axioms. (Contributed by Wolf Lammen, 2-Mar-2023.) |
⊢ (∃𝑦∀𝑥(𝑥 = 𝑦 → 𝜑) → ∃𝑥𝜑) | ||
Theorem | equsv 1999* | If a formula does not contain a variable 𝑥, then it is equivalent to the corresponding prototype of substitution with a fresh variable (see sb6 2081). (Contributed by BJ, 23-Jul-2023.) |
⊢ (∀𝑥(𝑥 = 𝑦 → 𝜑) ↔ 𝜑) | ||
Theorem | equsalvw 2000* | Version of equsalv 2254 with a disjoint variable condition, and of equsal 2411 with two disjoint variable conditions, which requires fewer axioms. See also the dual form equsexvw 2001. (Contributed by BJ, 31-May-2019.) |
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓)) ⇒ ⊢ (∀𝑥(𝑥 = 𝑦 → 𝜑) ↔ 𝜓) |
< Previous Next > |
Copyright terms: Public domain | < Previous Next > |