Home | Intuitionistic Logic Explorer Theorem List (p. 19 of 102) | < Previous Next > |
Bad symbols? Try the
GIF version. |
||
Mirrors > Metamath Home Page > ILE Home Page > Theorem List Contents > Recent Proofs This page: Page List |
Type | Label | Description |
---|---|---|
Statement | ||
Theorem | cbvexdh 1801* | Deduction used to change bound variables, using implicit substitition, particularly useful in conjunction with dvelim 1893. (Contributed by NM, 2-Jan-2002.) (Proof rewritten by Jim Kingdon, 30-Dec-2017.) |
⊢ (𝜑 → ∀𝑦𝜑) & ⊢ (𝜑 → (𝜓 → ∀𝑦𝜓)) & ⊢ (𝜑 → (𝑥 = 𝑦 → (𝜓 ↔ 𝜒))) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 ↔ ∃𝑦𝜒)) | ||
Theorem | cbvexd 1802* | Deduction used to change bound variables, using implicit substitution, particularly useful in conjunction with dvelim 1893. (Contributed by NM, 2-Jan-2002.) (Revised by Mario Carneiro, 6-Oct-2016.) (Proof rewritten by Jim Kingdon, 10-Jun-2018.) |
⊢ Ⅎ𝑦𝜑 & ⊢ (𝜑 → Ⅎ𝑦𝜓) & ⊢ (𝜑 → (𝑥 = 𝑦 → (𝜓 ↔ 𝜒))) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 ↔ ∃𝑦𝜒)) | ||
Theorem | cbvaldva 1803* | Rule used to change the bound variable in a universal quantifier with implicit substitution. Deduction form. (Contributed by David Moews, 1-May-2017.) |
⊢ ((𝜑 ∧ 𝑥 = 𝑦) → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∀𝑥𝜓 ↔ ∀𝑦𝜒)) | ||
Theorem | cbvexdva 1804* | Rule used to change the bound variable in an existential quantifier with implicit substitution. Deduction form. (Contributed by David Moews, 1-May-2017.) |
⊢ ((𝜑 ∧ 𝑥 = 𝑦) → (𝜓 ↔ 𝜒)) ⇒ ⊢ (𝜑 → (∃𝑥𝜓 ↔ ∃𝑦𝜒)) | ||
Theorem | cbvex4v 1805* | Rule used to change bound variables, using implicit substitition. (Contributed by NM, 26-Jul-1995.) |
⊢ ((𝑥 = 𝑣 ∧ 𝑦 = 𝑢) → (𝜑 ↔ 𝜓)) & ⊢ ((𝑧 = 𝑓 ∧ 𝑤 = 𝑔) → (𝜓 ↔ 𝜒)) ⇒ ⊢ (∃𝑥∃𝑦∃𝑧∃𝑤𝜑 ↔ ∃𝑣∃𝑢∃𝑓∃𝑔𝜒) | ||
Theorem | eean 1806 | Rearrange existential quantifiers. (Contributed by NM, 27-Oct-2010.) (Revised by Mario Carneiro, 6-Oct-2016.) |
⊢ Ⅎ𝑦𝜑 & ⊢ Ⅎ𝑥𝜓 ⇒ ⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (∃𝑥𝜑 ∧ ∃𝑦𝜓)) | ||
Theorem | eeanv 1807* | Rearrange existential quantifiers. (Contributed by NM, 26-Jul-1995.) |
⊢ (∃𝑥∃𝑦(𝜑 ∧ 𝜓) ↔ (∃𝑥𝜑 ∧ ∃𝑦𝜓)) | ||
Theorem | eeeanv 1808* | Rearrange existential quantifiers. (Contributed by NM, 26-Jul-1995.) (Proof shortened by Andrew Salmon, 25-May-2011.) |
⊢ (∃𝑥∃𝑦∃𝑧(𝜑 ∧ 𝜓 ∧ 𝜒) ↔ (∃𝑥𝜑 ∧ ∃𝑦𝜓 ∧ ∃𝑧𝜒)) | ||
Theorem | ee4anv 1809* | Rearrange existential quantifiers. (Contributed by NM, 31-Jul-1995.) |
⊢ (∃𝑥∃𝑦∃𝑧∃𝑤(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦𝜑 ∧ ∃𝑧∃𝑤𝜓)) | ||
Theorem | ee8anv 1810* | Rearrange existential quantifiers. (Contributed by Jim Kingdon, 23-Nov-2019.) |
⊢ (∃𝑥∃𝑦∃𝑧∃𝑤∃𝑣∃𝑢∃𝑡∃𝑠(𝜑 ∧ 𝜓) ↔ (∃𝑥∃𝑦∃𝑧∃𝑤𝜑 ∧ ∃𝑣∃𝑢∃𝑡∃𝑠𝜓)) | ||
Theorem | nexdv 1811* | Deduction for generalization rule for negated wff. (Contributed by NM, 5-Aug-1993.) |
⊢ (𝜑 → ¬ 𝜓) ⇒ ⊢ (𝜑 → ¬ ∃𝑥𝜓) | ||
Theorem | chvarv 1812* | Implicit substitution of 𝑦 for 𝑥 into a theorem. (Contributed by NM, 20-Apr-1994.) |
⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜓)) & ⊢ 𝜑 ⇒ ⊢ 𝜓 | ||
Theorem | cleljust 1813* | When the class variables of set theory are replaced with setvar variables, this theorem of predicate calculus is the result. This theorem provides part of the justification for the consistency of that definition, which "overloads" the setvar variables in wel 1394 with the class variables in wcel 1393. (Contributed by NM, 28-Jan-2004.) |
⊢ (𝑥 ∈ 𝑦 ↔ ∃𝑧(𝑧 = 𝑥 ∧ 𝑧 ∈ 𝑦)) | ||
Theorem | hbs1 1814* | 𝑥 is not free in [𝑦 / 𝑥]𝜑 when 𝑥 and 𝑦 are distinct. (Contributed by NM, 5-Aug-1993.) (Proof by Jim Kingdon, 16-Dec-2017.) (New usage is discouraged.) |
⊢ ([𝑦 / 𝑥]𝜑 → ∀𝑥[𝑦 / 𝑥]𝜑) | ||
Theorem | nfs1v 1815* | 𝑥 is not free in [𝑦 / 𝑥]𝜑 when 𝑥 and 𝑦 are distinct. (Contributed by Mario Carneiro, 11-Aug-2016.) |
⊢ Ⅎ𝑥[𝑦 / 𝑥]𝜑 | ||
Theorem | sbhb 1816* | Two ways of expressing "𝑥 is (effectively) not free in 𝜑." (Contributed by NM, 29-May-2009.) |
⊢ ((𝜑 → ∀𝑥𝜑) ↔ ∀𝑦(𝜑 → [𝑦 / 𝑥]𝜑)) | ||
Theorem | hbsbv 1817* | This is a version of hbsb 1823 with an extra distinct variable constraint, on 𝑧 and 𝑥. (Contributed by Jim Kingdon, 25-Dec-2017.) |
⊢ (𝜑 → ∀𝑧𝜑) ⇒ ⊢ ([𝑦 / 𝑥]𝜑 → ∀𝑧[𝑦 / 𝑥]𝜑) | ||
Theorem | nfsbxy 1818* | Similar to hbsb 1823 but with an extra distinct variable constraint, on 𝑥 and 𝑦. (Contributed by Jim Kingdon, 19-Mar-2018.) |
⊢ Ⅎ𝑧𝜑 ⇒ ⊢ Ⅎ𝑧[𝑦 / 𝑥]𝜑 | ||
Theorem | nfsbxyt 1819* | Closed form of nfsbxy 1818. (Contributed by Jim Kingdon, 9-May-2018.) |
⊢ (∀𝑥Ⅎ𝑧𝜑 → Ⅎ𝑧[𝑦 / 𝑥]𝜑) | ||
Theorem | sbco2vlem 1820* | This is a version of sbco2 1839 where 𝑧 is distinct from 𝑥 and from 𝑦. It is a lemma on the way to proving sbco2v 1821 which only requires that 𝑧 and 𝑥 be distinct. (Contributed by Jim Kingdon, 25-Dec-2017.) (One distinct variable constraint removed by Jim Kingdon, 3-Feb-2018.) |
⊢ (𝜑 → ∀𝑧𝜑) ⇒ ⊢ ([𝑦 / 𝑧][𝑧 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑) | ||
Theorem | sbco2v 1821* | This is a version of sbco2 1839 where 𝑧 is distinct from 𝑥. (Contributed by Jim Kingdon, 12-Feb-2018.) |
⊢ (𝜑 → ∀𝑧𝜑) ⇒ ⊢ ([𝑦 / 𝑧][𝑧 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑) | ||
Theorem | nfsb 1822* | If 𝑧 is not free in 𝜑, it is not free in [𝑦 / 𝑥]𝜑 when 𝑦 and 𝑧 are distinct. (Contributed by Mario Carneiro, 11-Aug-2016.) (Proof rewritten by Jim Kingdon, 19-Mar-2018.) |
⊢ Ⅎ𝑧𝜑 ⇒ ⊢ Ⅎ𝑧[𝑦 / 𝑥]𝜑 | ||
Theorem | hbsb 1823* | If 𝑧 is not free in 𝜑, it is not free in [𝑦 / 𝑥]𝜑 when 𝑦 and 𝑧 are distinct. (Contributed by NM, 12-Aug-1993.) (Proof rewritten by Jim Kingdon, 22-Mar-2018.) |
⊢ (𝜑 → ∀𝑧𝜑) ⇒ ⊢ ([𝑦 / 𝑥]𝜑 → ∀𝑧[𝑦 / 𝑥]𝜑) | ||
Theorem | equsb3lem 1824* | Lemma for equsb3 1825. (Contributed by NM, 4-Dec-2005.) (Proof shortened by Andrew Salmon, 14-Jun-2011.) |
⊢ ([𝑥 / 𝑦]𝑦 = 𝑧 ↔ 𝑥 = 𝑧) | ||
Theorem | equsb3 1825* | Substitution applied to an atomic wff. (Contributed by Raph Levien and FL, 4-Dec-2005.) |
⊢ ([𝑥 / 𝑦]𝑦 = 𝑧 ↔ 𝑥 = 𝑧) | ||
Theorem | sbn 1826 | Negation inside and outside of substitution are equivalent. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 3-Feb-2018.) |
⊢ ([𝑦 / 𝑥] ¬ 𝜑 ↔ ¬ [𝑦 / 𝑥]𝜑) | ||
Theorem | sbim 1827 | Implication inside and outside of substitution are equivalent. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 3-Feb-2018.) |
⊢ ([𝑦 / 𝑥](𝜑 → 𝜓) ↔ ([𝑦 / 𝑥]𝜑 → [𝑦 / 𝑥]𝜓)) | ||
Theorem | sbor 1828 | Logical OR inside and outside of substitution are equivalent. (Contributed by NM, 29-Sep-2002.) (Proof rewritten by Jim Kingdon, 3-Feb-2018.) |
⊢ ([𝑦 / 𝑥](𝜑 ∨ 𝜓) ↔ ([𝑦 / 𝑥]𝜑 ∨ [𝑦 / 𝑥]𝜓)) | ||
Theorem | sban 1829 | Conjunction inside and outside of a substitution are equivalent. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 3-Feb-2018.) |
⊢ ([𝑦 / 𝑥](𝜑 ∧ 𝜓) ↔ ([𝑦 / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜓)) | ||
Theorem | sbrim 1830 | Substitution with a variable not free in antecedent affects only the consequent. (Contributed by NM, 5-Aug-1993.) |
⊢ (𝜑 → ∀𝑥𝜑) ⇒ ⊢ ([𝑦 / 𝑥](𝜑 → 𝜓) ↔ (𝜑 → [𝑦 / 𝑥]𝜓)) | ||
Theorem | sblim 1831 | Substitution with a variable not free in consequent affects only the antecedent. (Contributed by NM, 14-Nov-2013.) (Revised by Mario Carneiro, 4-Oct-2016.) |
⊢ Ⅎ𝑥𝜓 ⇒ ⊢ ([𝑦 / 𝑥](𝜑 → 𝜓) ↔ ([𝑦 / 𝑥]𝜑 → 𝜓)) | ||
Theorem | sb3an 1832 | Conjunction inside and outside of a substitution are equivalent. (Contributed by NM, 14-Dec-2006.) |
⊢ ([𝑦 / 𝑥](𝜑 ∧ 𝜓 ∧ 𝜒) ↔ ([𝑦 / 𝑥]𝜑 ∧ [𝑦 / 𝑥]𝜓 ∧ [𝑦 / 𝑥]𝜒)) | ||
Theorem | sbbi 1833 | Equivalence inside and outside of a substitution are equivalent. (Contributed by NM, 5-Aug-1993.) |
⊢ ([𝑦 / 𝑥](𝜑 ↔ 𝜓) ↔ ([𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜓)) | ||
Theorem | sblbis 1834 | Introduce left biconditional inside of a substitution. (Contributed by NM, 19-Aug-1993.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ 𝜓) ⇒ ⊢ ([𝑦 / 𝑥](𝜒 ↔ 𝜑) ↔ ([𝑦 / 𝑥]𝜒 ↔ 𝜓)) | ||
Theorem | sbrbis 1835 | Introduce right biconditional inside of a substitution. (Contributed by NM, 18-Aug-1993.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ 𝜓) ⇒ ⊢ ([𝑦 / 𝑥](𝜑 ↔ 𝜒) ↔ (𝜓 ↔ [𝑦 / 𝑥]𝜒)) | ||
Theorem | sbrbif 1836 | Introduce right biconditional inside of a substitution. (Contributed by NM, 18-Aug-1993.) |
⊢ (𝜒 → ∀𝑥𝜒) & ⊢ ([𝑦 / 𝑥]𝜑 ↔ 𝜓) ⇒ ⊢ ([𝑦 / 𝑥](𝜑 ↔ 𝜒) ↔ (𝜓 ↔ 𝜒)) | ||
Theorem | sbco2yz 1837* | This is a version of sbco2 1839 where 𝑧 is distinct from 𝑦. It is a lemma on the way to proving sbco2 1839 which has no distinct variable constraints. (Contributed by Jim Kingdon, 19-Mar-2018.) |
⊢ Ⅎ𝑧𝜑 ⇒ ⊢ ([𝑦 / 𝑧][𝑧 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑) | ||
Theorem | sbco2h 1838 | A composition law for substitution. (Contributed by NM, 30-Jun-1994.) (Proof rewritten by Jim Kingdon, 19-Mar-2018.) |
⊢ (𝜑 → ∀𝑧𝜑) ⇒ ⊢ ([𝑦 / 𝑧][𝑧 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑) | ||
Theorem | sbco2 1839 | A composition law for substitution. (Contributed by NM, 30-Jun-1994.) (Revised by Mario Carneiro, 6-Oct-2016.) |
⊢ Ⅎ𝑧𝜑 ⇒ ⊢ ([𝑦 / 𝑧][𝑧 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑) | ||
Theorem | sbco2d 1840 | A composition law for substitution. (Contributed by NM, 5-Aug-1993.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝜑 → ∀𝑧𝜑) & ⊢ (𝜑 → (𝜓 → ∀𝑧𝜓)) ⇒ ⊢ (𝜑 → ([𝑦 / 𝑧][𝑧 / 𝑥]𝜓 ↔ [𝑦 / 𝑥]𝜓)) | ||
Theorem | sbco2vd 1841* | Version of sbco2d 1840 with a distinct variable constraint between 𝑥 and 𝑧. (Contributed by Jim Kingdon, 19-Feb-2018.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝜑 → ∀𝑧𝜑) & ⊢ (𝜑 → (𝜓 → ∀𝑧𝜓)) ⇒ ⊢ (𝜑 → ([𝑦 / 𝑧][𝑧 / 𝑥]𝜓 ↔ [𝑦 / 𝑥]𝜓)) | ||
Theorem | sbco 1842 | A composition law for substitution. (Contributed by NM, 5-Aug-1993.) |
⊢ ([𝑦 / 𝑥][𝑥 / 𝑦]𝜑 ↔ [𝑦 / 𝑥]𝜑) | ||
Theorem | sbco3v 1843* | Version of sbco3 1848 with a distinct variable constraint between 𝑥 and 𝑦. (Contributed by Jim Kingdon, 19-Feb-2018.) |
⊢ ([𝑧 / 𝑦][𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥][𝑥 / 𝑦]𝜑) | ||
Theorem | sbcocom 1844 | Relationship between composition and commutativity for substitution. (Contributed by Jim Kingdon, 28-Feb-2018.) |
⊢ ([𝑧 / 𝑦][𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑦][𝑧 / 𝑥]𝜑) | ||
Theorem | sbcomv 1845* | Version of sbcom 1849 with a distinct variable constraint between 𝑥 and 𝑧. (Contributed by Jim Kingdon, 28-Feb-2018.) |
⊢ ([𝑦 / 𝑧][𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥][𝑦 / 𝑧]𝜑) | ||
Theorem | sbcomxyyz 1846* | Version of sbcom 1849 with distinct variable constraints between 𝑥 and 𝑦, and 𝑦 and 𝑧. (Contributed by Jim Kingdon, 21-Mar-2018.) |
⊢ ([𝑦 / 𝑧][𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥][𝑦 / 𝑧]𝜑) | ||
Theorem | sbco3xzyz 1847* | Version of sbco3 1848 with distinct variable constraints between 𝑥 and 𝑧, and 𝑦 and 𝑧. Lemma for proving sbco3 1848. (Contributed by Jim Kingdon, 22-Mar-2018.) |
⊢ ([𝑧 / 𝑦][𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥][𝑥 / 𝑦]𝜑) | ||
Theorem | sbco3 1848 | A composition law for substitution. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 22-Mar-2018.) |
⊢ ([𝑧 / 𝑦][𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥][𝑥 / 𝑦]𝜑) | ||
Theorem | sbcom 1849 | A commutativity law for substitution. (Contributed by NM, 27-May-1997.) (Proof rewritten by Jim Kingdon, 22-Mar-2018.) |
⊢ ([𝑦 / 𝑧][𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥][𝑦 / 𝑧]𝜑) | ||
Theorem | nfsbt 1850* | Closed form of nfsb 1822. (Contributed by Jim Kingdon, 9-May-2018.) |
⊢ (∀𝑥Ⅎ𝑧𝜑 → Ⅎ𝑧[𝑦 / 𝑥]𝜑) | ||
Theorem | nfsbd 1851* | Deduction version of nfsb 1822. (Contributed by NM, 15-Feb-2013.) |
⊢ Ⅎ𝑥𝜑 & ⊢ (𝜑 → Ⅎ𝑧𝜓) ⇒ ⊢ (𝜑 → Ⅎ𝑧[𝑦 / 𝑥]𝜓) | ||
Theorem | elsb3 1852* | Substitution applied to an atomic membership wff. (Contributed by NM, 7-Nov-2006.) (Proof shortened by Andrew Salmon, 14-Jun-2011.) |
⊢ ([𝑥 / 𝑦]𝑦 ∈ 𝑧 ↔ 𝑥 ∈ 𝑧) | ||
Theorem | elsb4 1853* | Substitution applied to an atomic membership wff. (Contributed by Rodolfo Medina, 3-Apr-2010.) (Proof shortened by Andrew Salmon, 14-Jun-2011.) |
⊢ ([𝑥 / 𝑦]𝑧 ∈ 𝑦 ↔ 𝑧 ∈ 𝑥) | ||
Theorem | sb9v 1854* | Like sb9 1855 but with a distinct variable constraint between 𝑥 and 𝑦. (Contributed by Jim Kingdon, 28-Feb-2018.) |
⊢ (∀𝑥[𝑥 / 𝑦]𝜑 ↔ ∀𝑦[𝑦 / 𝑥]𝜑) | ||
Theorem | sb9 1855 | Commutation of quantification and substitution variables. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 23-Mar-2018.) |
⊢ (∀𝑥[𝑥 / 𝑦]𝜑 ↔ ∀𝑦[𝑦 / 𝑥]𝜑) | ||
Theorem | sb9i 1856 | Commutation of quantification and substitution variables. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 23-Mar-2018.) |
⊢ (∀𝑥[𝑥 / 𝑦]𝜑 → ∀𝑦[𝑦 / 𝑥]𝜑) | ||
Theorem | sbnf2 1857* | Two ways of expressing "𝑥 is (effectively) not free in 𝜑." (Contributed by Gérard Lang, 14-Nov-2013.) (Revised by Mario Carneiro, 6-Oct-2016.) |
⊢ (Ⅎ𝑥𝜑 ↔ ∀𝑦∀𝑧([𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥]𝜑)) | ||
Theorem | hbsbd 1858* | Deduction version of hbsb 1823. (Contributed by NM, 15-Feb-2013.) (Proof rewritten by Jim Kingdon, 23-Mar-2018.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝜑 → ∀𝑧𝜑) & ⊢ (𝜑 → (𝜓 → ∀𝑧𝜓)) ⇒ ⊢ (𝜑 → ([𝑦 / 𝑥]𝜓 → ∀𝑧[𝑦 / 𝑥]𝜓)) | ||
Theorem | 2sb5 1859* | Equivalence for double substitution. (Contributed by NM, 3-Feb-2005.) |
⊢ ([𝑧 / 𝑥][𝑤 / 𝑦]𝜑 ↔ ∃𝑥∃𝑦((𝑥 = 𝑧 ∧ 𝑦 = 𝑤) ∧ 𝜑)) | ||
Theorem | 2sb6 1860* | Equivalence for double substitution. (Contributed by NM, 3-Feb-2005.) |
⊢ ([𝑧 / 𝑥][𝑤 / 𝑦]𝜑 ↔ ∀𝑥∀𝑦((𝑥 = 𝑧 ∧ 𝑦 = 𝑤) → 𝜑)) | ||
Theorem | sbcom2v 1861* | Lemma for proving sbcom2 1863. It is the same as sbcom2 1863 but with additional distinct variable constraints on 𝑥 and 𝑦, and on 𝑤 and 𝑧. (Contributed by Jim Kingdon, 19-Feb-2018.) |
⊢ ([𝑤 / 𝑧][𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥][𝑤 / 𝑧]𝜑) | ||
Theorem | sbcom2v2 1862* | Lemma for proving sbcom2 1863. It is the same as sbcom2v 1861 but removes the distinct variable constraint on 𝑥 and 𝑦. (Contributed by Jim Kingdon, 19-Feb-2018.) |
⊢ ([𝑤 / 𝑧][𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥][𝑤 / 𝑧]𝜑) | ||
Theorem | sbcom2 1863* | Commutativity law for substitution. Used in proof of Theorem 9.7 of [Megill] p. 449 (p. 16 of the preprint). (Contributed by NM, 27-May-1997.) (Proof modified to be intuitionistic by Jim Kingdon, 19-Feb-2018.) |
⊢ ([𝑤 / 𝑧][𝑦 / 𝑥]𝜑 ↔ [𝑦 / 𝑥][𝑤 / 𝑧]𝜑) | ||
Theorem | sb6a 1864* | Equivalence for substitution. (Contributed by NM, 5-Aug-1993.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ ∀𝑥(𝑥 = 𝑦 → [𝑥 / 𝑦]𝜑)) | ||
Theorem | 2sb5rf 1865* | Reversed double substitution. (Contributed by NM, 3-Feb-2005.) |
⊢ (𝜑 → ∀𝑧𝜑) & ⊢ (𝜑 → ∀𝑤𝜑) ⇒ ⊢ (𝜑 ↔ ∃𝑧∃𝑤((𝑧 = 𝑥 ∧ 𝑤 = 𝑦) ∧ [𝑧 / 𝑥][𝑤 / 𝑦]𝜑)) | ||
Theorem | 2sb6rf 1866* | Reversed double substitution. (Contributed by NM, 3-Feb-2005.) |
⊢ (𝜑 → ∀𝑧𝜑) & ⊢ (𝜑 → ∀𝑤𝜑) ⇒ ⊢ (𝜑 ↔ ∀𝑧∀𝑤((𝑧 = 𝑥 ∧ 𝑤 = 𝑦) → [𝑧 / 𝑥][𝑤 / 𝑦]𝜑)) | ||
Theorem | dfsb7 1867* | An alternate definition of proper substitution df-sb 1646. By introducing a dummy variable 𝑧 in the definiens, we are able to eliminate any distinct variable restrictions among the variables 𝑥, 𝑦, and 𝜑 of the definiendum. No distinct variable conflicts arise because 𝑧 effectively insulates 𝑥 from 𝑦. To achieve this, we use a chain of two substitutions in the form of sb5 1767, first 𝑧 for 𝑥 then 𝑦 for 𝑧. Compare Definition 2.1'' of [Quine] p. 17. Theorem sb7f 1868 provides a version where 𝜑 and 𝑧 don't have to be distinct. (Contributed by NM, 28-Jan-2004.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ ∃𝑧(𝑧 = 𝑦 ∧ ∃𝑥(𝑥 = 𝑧 ∧ 𝜑))) | ||
Theorem | sb7f 1868* | This version of dfsb7 1867 does not require that 𝜑 and 𝑧 be distinct. This permits it to be used as a definition for substitution in a formalization that omits the logically redundant axiom ax-17 1419 i.e. that doesn't have the concept of a variable not occurring in a wff. (df-sb 1646 is also suitable, but its mixing of free and bound variables is distasteful to some logicians.) (Contributed by NM, 26-Jul-2006.) (Proof shortened by Andrew Salmon, 25-May-2011.) |
⊢ (𝜑 → ∀𝑧𝜑) ⇒ ⊢ ([𝑦 / 𝑥]𝜑 ↔ ∃𝑧(𝑧 = 𝑦 ∧ ∃𝑥(𝑥 = 𝑧 ∧ 𝜑))) | ||
Theorem | sb7af 1869* | An alternative definition of proper substitution df-sb 1646. Similar to dfsb7a 1870 but does not require that 𝜑 and 𝑧 be distinct. Similar to sb7f 1868 in that it involves a dummy variable 𝑧, but expressed in terms of ∀ rather than ∃. (Contributed by Jim Kingdon, 5-Feb-2018.) |
⊢ Ⅎ𝑧𝜑 ⇒ ⊢ ([𝑦 / 𝑥]𝜑 ↔ ∀𝑧(𝑧 = 𝑦 → ∀𝑥(𝑥 = 𝑧 → 𝜑))) | ||
Theorem | dfsb7a 1870* | An alternative definition of proper substitution df-sb 1646. Similar to dfsb7 1867 in that it involves a dummy variable 𝑧, but expressed in terms of ∀ rather than ∃. For a version which only requires Ⅎ𝑧𝜑 rather than 𝑧 and 𝜑 being distinct, see sb7af 1869. (Contributed by Jim Kingdon, 5-Feb-2018.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ ∀𝑧(𝑧 = 𝑦 → ∀𝑥(𝑥 = 𝑧 → 𝜑))) | ||
Theorem | sb10f 1871* | Hao Wang's identity axiom P6 in Irving Copi, Symbolic Logic (5th ed., 1979), p. 328. In traditional predicate calculus, this is a sole axiom for identity from which the usual ones can be derived. (Contributed by NM, 9-May-2005.) |
⊢ (𝜑 → ∀𝑥𝜑) ⇒ ⊢ ([𝑦 / 𝑧]𝜑 ↔ ∃𝑥(𝑥 = 𝑦 ∧ [𝑥 / 𝑧]𝜑)) | ||
Theorem | sbid2v 1872* | An identity law for substitution. Used in proof of Theorem 9.7 of [Megill] p. 449 (p. 16 of the preprint). (Contributed by NM, 5-Aug-1993.) |
⊢ ([𝑦 / 𝑥][𝑥 / 𝑦]𝜑 ↔ 𝜑) | ||
Theorem | sbelx 1873* | Elimination of substitution. (Contributed by NM, 5-Aug-1993.) |
⊢ (𝜑 ↔ ∃𝑥(𝑥 = 𝑦 ∧ [𝑥 / 𝑦]𝜑)) | ||
Theorem | sbel2x 1874* | Elimination of double substitution. (Contributed by NM, 5-Aug-1993.) |
⊢ (𝜑 ↔ ∃𝑥∃𝑦((𝑥 = 𝑧 ∧ 𝑦 = 𝑤) ∧ [𝑦 / 𝑤][𝑥 / 𝑧]𝜑)) | ||
Theorem | sbalyz 1875* | Move universal quantifier in and out of substitution. Identical to sbal 1876 except that it has an additional distinct variable constraint on 𝑦 and 𝑧. (Contributed by Jim Kingdon, 29-Dec-2017.) |
⊢ ([𝑧 / 𝑦]∀𝑥𝜑 ↔ ∀𝑥[𝑧 / 𝑦]𝜑) | ||
Theorem | sbal 1876* | Move universal quantifier in and out of substitution. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 12-Feb-2018.) |
⊢ ([𝑧 / 𝑦]∀𝑥𝜑 ↔ ∀𝑥[𝑧 / 𝑦]𝜑) | ||
Theorem | sbal1yz 1877* | Lemma for proving sbal1 1878. Same as sbal1 1878 but with an additional distinct variable constraint on 𝑦 and 𝑧. (Contributed by Jim Kingdon, 23-Feb-2018.) |
⊢ (¬ ∀𝑥 𝑥 = 𝑧 → ([𝑧 / 𝑦]∀𝑥𝜑 ↔ ∀𝑥[𝑧 / 𝑦]𝜑)) | ||
Theorem | sbal1 1878* | A theorem used in elimination of disjoint variable restriction on 𝑥 and 𝑦 by replacing it with a distinctor ¬ ∀𝑥𝑥 = 𝑧. (Contributed by NM, 5-Aug-1993.) (Proof rewitten by Jim Kingdon, 24-Feb-2018.) |
⊢ (¬ ∀𝑥 𝑥 = 𝑧 → ([𝑧 / 𝑦]∀𝑥𝜑 ↔ ∀𝑥[𝑧 / 𝑦]𝜑)) | ||
Theorem | sbexyz 1879* | Move existential quantifier in and out of substitution. Identical to sbex 1880 except that it has an additional distinct variable constraint on 𝑦 and 𝑧. (Contributed by Jim Kingdon, 29-Dec-2017.) |
⊢ ([𝑧 / 𝑦]∃𝑥𝜑 ↔ ∃𝑥[𝑧 / 𝑦]𝜑) | ||
Theorem | sbex 1880* | Move existential quantifier in and out of substitution. (Contributed by NM, 27-Sep-2003.) (Proof rewritten by Jim Kingdon, 12-Feb-2018.) |
⊢ ([𝑧 / 𝑦]∃𝑥𝜑 ↔ ∃𝑥[𝑧 / 𝑦]𝜑) | ||
Theorem | sbalv 1881* | Quantify with new variable inside substitution. (Contributed by NM, 18-Aug-1993.) |
⊢ ([𝑦 / 𝑥]𝜑 ↔ 𝜓) ⇒ ⊢ ([𝑦 / 𝑥]∀𝑧𝜑 ↔ ∀𝑧𝜓) | ||
Theorem | sbco4lem 1882* | Lemma for sbco4 1883. It replaces the temporary variable 𝑣 with another temporary variable 𝑤. (Contributed by Jim Kingdon, 26-Sep-2018.) |
⊢ ([𝑥 / 𝑣][𝑦 / 𝑥][𝑣 / 𝑦]𝜑 ↔ [𝑥 / 𝑤][𝑦 / 𝑥][𝑤 / 𝑦]𝜑) | ||
Theorem | sbco4 1883* | Two ways of exchanging two variables. Both sides of the biconditional exchange 𝑥 and 𝑦, either via two temporary variables 𝑢 and 𝑣, or a single temporary 𝑤. (Contributed by Jim Kingdon, 25-Sep-2018.) |
⊢ ([𝑦 / 𝑢][𝑥 / 𝑣][𝑢 / 𝑥][𝑣 / 𝑦]𝜑 ↔ [𝑥 / 𝑤][𝑦 / 𝑥][𝑤 / 𝑦]𝜑) | ||
Theorem | exsb 1884* | An equivalent expression for existence. (Contributed by NM, 2-Feb-2005.) |
⊢ (∃𝑥𝜑 ↔ ∃𝑦∀𝑥(𝑥 = 𝑦 → 𝜑)) | ||
Theorem | 2exsb 1885* | An equivalent expression for double existence. (Contributed by NM, 2-Feb-2005.) |
⊢ (∃𝑥∃𝑦𝜑 ↔ ∃𝑧∃𝑤∀𝑥∀𝑦((𝑥 = 𝑧 ∧ 𝑦 = 𝑤) → 𝜑)) | ||
Theorem | dvelimALT 1886* | Version of dvelim 1893 that doesn't use ax-10 1396. Because it has different distinct variable constraints than dvelim 1893 and is used in important proofs, it would be better if it had a name which does not end in ALT (ideally more close to set.mm naming). (Contributed by NM, 17-May-2008.) (Proof modification is discouraged.) (New usage is discouraged.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝑧 = 𝑦 → (𝜑 ↔ 𝜓)) ⇒ ⊢ (¬ ∀𝑥 𝑥 = 𝑦 → (𝜓 → ∀𝑥𝜓)) | ||
Theorem | dvelimfv 1887* | Like dvelimf 1891 but with a distinct variable constraint on 𝑥 and 𝑧. (Contributed by Jim Kingdon, 6-Mar-2018.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝜓 → ∀𝑧𝜓) & ⊢ (𝑧 = 𝑦 → (𝜑 ↔ 𝜓)) ⇒ ⊢ (¬ ∀𝑥 𝑥 = 𝑦 → (𝜓 → ∀𝑥𝜓)) | ||
Theorem | hbsb4 1888 | A variable not free remains so after substitution with a distinct variable. (Contributed by NM, 5-Aug-1993.) (Proof rewritten by Jim Kingdon, 23-Mar-2018.) |
⊢ (𝜑 → ∀𝑧𝜑) ⇒ ⊢ (¬ ∀𝑧 𝑧 = 𝑦 → ([𝑦 / 𝑥]𝜑 → ∀𝑧[𝑦 / 𝑥]𝜑)) | ||
Theorem | hbsb4t 1889 | A variable not free remains so after substitution with a distinct variable (closed form of hbsb4 1888). (Contributed by NM, 7-Apr-2004.) (Proof shortened by Andrew Salmon, 25-May-2011.) |
⊢ (∀𝑥∀𝑧(𝜑 → ∀𝑧𝜑) → (¬ ∀𝑧 𝑧 = 𝑦 → ([𝑦 / 𝑥]𝜑 → ∀𝑧[𝑦 / 𝑥]𝜑))) | ||
Theorem | nfsb4t 1890 | A variable not free remains so after substitution with a distinct variable (closed form of hbsb4 1888). (Contributed by NM, 7-Apr-2004.) (Revised by Mario Carneiro, 4-Oct-2016.) (Proof rewritten by Jim Kingdon, 9-May-2018.) |
⊢ (∀𝑥Ⅎ𝑧𝜑 → (¬ ∀𝑧 𝑧 = 𝑦 → Ⅎ𝑧[𝑦 / 𝑥]𝜑)) | ||
Theorem | dvelimf 1891 | Version of dvelim 1893 without any variable restrictions. (Contributed by NM, 1-Oct-2002.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝜓 → ∀𝑧𝜓) & ⊢ (𝑧 = 𝑦 → (𝜑 ↔ 𝜓)) ⇒ ⊢ (¬ ∀𝑥 𝑥 = 𝑦 → (𝜓 → ∀𝑥𝜓)) | ||
Theorem | dvelimdf 1892 | Deduction form of dvelimf 1891. This version may be useful if we want to avoid ax-17 1419 and use ax-16 1695 instead. (Contributed by NM, 7-Apr-2004.) (Revised by Mario Carneiro, 6-Oct-2016.) (Proof shortened by Wolf Lammen, 11-May-2018.) |
⊢ Ⅎ𝑥𝜑 & ⊢ Ⅎ𝑧𝜑 & ⊢ (𝜑 → Ⅎ𝑥𝜓) & ⊢ (𝜑 → Ⅎ𝑧𝜒) & ⊢ (𝜑 → (𝑧 = 𝑦 → (𝜓 ↔ 𝜒))) ⇒ ⊢ (𝜑 → (¬ ∀𝑥 𝑥 = 𝑦 → Ⅎ𝑥𝜒)) | ||
Theorem | dvelim 1893* |
This theorem can be used to eliminate a distinct variable restriction on
𝑥 and 𝑧 and replace it with the
"distinctor" ¬ ∀𝑥𝑥 = 𝑦
as an antecedent. 𝜑 normally has 𝑧 free and can be read
𝜑(𝑧), and 𝜓 substitutes 𝑦 for
𝑧
and can be read
𝜑(𝑦). We don't require that 𝑥 and
𝑦
be distinct: if
they aren't, the distinctor will become false (in multiple-element
domains of discourse) and "protect" the consequent.
To obtain a closed-theorem form of this inference, prefix the hypotheses with ∀𝑥∀𝑧, conjoin them, and apply dvelimdf 1892. Other variants of this theorem are dvelimf 1891 (with no distinct variable restrictions) and dvelimALT 1886 (that avoids ax-10 1396). (Contributed by NM, 23-Nov-1994.) |
⊢ (𝜑 → ∀𝑥𝜑) & ⊢ (𝑧 = 𝑦 → (𝜑 ↔ 𝜓)) ⇒ ⊢ (¬ ∀𝑥 𝑥 = 𝑦 → (𝜓 → ∀𝑥𝜓)) | ||
Theorem | dvelimor 1894* | Disjunctive distinct variable constraint elimination. A user of this theorem starts with a formula 𝜑 (containing 𝑧) and a distinct variable constraint between 𝑥 and 𝑧. The theorem makes it possible to replace the distinct variable constraint with the disjunct ∀𝑥𝑥 = 𝑦 (𝜓 is just a version of 𝜑 with 𝑦 substituted for 𝑧). (Contributed by Jim Kingdon, 11-May-2018.) |
⊢ Ⅎ𝑥𝜑 & ⊢ (𝑧 = 𝑦 → (𝜑 ↔ 𝜓)) ⇒ ⊢ (∀𝑥 𝑥 = 𝑦 ∨ Ⅎ𝑥𝜓) | ||
Theorem | dveeq1 1895* | Quantifier introduction when one pair of variables is distinct. (Contributed by NM, 2-Jan-2002.) (Proof rewritten by Jim Kingdon, 19-Feb-2018.) |
⊢ (¬ ∀𝑥 𝑥 = 𝑦 → (𝑦 = 𝑧 → ∀𝑥 𝑦 = 𝑧)) | ||
Theorem | dveel1 1896* | Quantifier introduction when one pair of variables is distinct. (Contributed by NM, 2-Jan-2002.) |
⊢ (¬ ∀𝑥 𝑥 = 𝑦 → (𝑦 ∈ 𝑧 → ∀𝑥 𝑦 ∈ 𝑧)) | ||
Theorem | dveel2 1897* | Quantifier introduction when one pair of variables is distinct. (Contributed by NM, 2-Jan-2002.) |
⊢ (¬ ∀𝑥 𝑥 = 𝑦 → (𝑧 ∈ 𝑦 → ∀𝑥 𝑧 ∈ 𝑦)) | ||
Theorem | sbal2 1898* | Move quantifier in and out of substitution. (Contributed by NM, 2-Jan-2002.) |
⊢ (¬ ∀𝑥 𝑥 = 𝑦 → ([𝑧 / 𝑦]∀𝑥𝜑 ↔ ∀𝑥[𝑧 / 𝑦]𝜑)) | ||
Theorem | nfsb4or 1899 | A variable not free remains so after substitution with a distinct variable. (Contributed by Jim Kingdon, 11-May-2018.) |
⊢ Ⅎ𝑧𝜑 ⇒ ⊢ (∀𝑧 𝑧 = 𝑦 ∨ Ⅎ𝑧[𝑦 / 𝑥]𝜑) | ||
Syntax | weu 1900 | Extend wff definition to include existential uniqueness ("there exists a unique 𝑥 such that 𝜑"). |
wff ∃!𝑥𝜑 |
< Previous Next > |
Copyright terms: Public domain | < Previous Next > |