Metamath Proof Explorer - mmtheorems10

Jump to page: 1 1-100 2 101-200 3 201-300 4 301-400 5 401-500 6 501-600 7 601-700 8 701-800 9 801-900 10 901-1000 11 1001-1100 12 1101-1200 13 1201-1300 14 1301-1400 15 1401-1500 16 1501-1600 17 1601-1700 18 1701-1800 19 1801-1900 20 1901-2000 21 2001-2100 22 2101-2200 23 2201-2300 24 2301-2400 25 2401-2500 26 2501-2600 27 2601-2700 28 2701-2800 29 2801-2900 30 2901-3000 31 3001-3100 32 3101-3200 33 3201-3300 34 3301-3400 35 3401-3500 36 3501-3600 37 3601-3700 38 3701-3800 39 3801-3900 40 3901-4000 41 4001-4100 42 4101-4200 43 4201-4300 44 4301-4400 45 4401-4500 46 4501-4600 47 4601-4700 48 4701-4800 49 4801-4900 50 4901-5000 51 5001-5100 52 5101-5200 53 5201-5300 54 5301-5400 55 5401-5500 56 5501-5600 57 5601-5700 58 5701-5787

Statement List for Metamath Proof Explorer - 901-1000 - Page 10 of 58

Type	Label	Description
Statement
Theorem	sbeq2 901	Substitution applied to atomic wff.
⊢ [y / x]y = x
Theorem	sbequ8 902	Elimination of equality from antecedent after substitution.
⊢ ([y / x]φ ↔ [y / x](x = y → φ))
Theorem	sbied 903	Conversion of implicit substitution to explicit substitution (deduction version of sbie 904).
⊢ (φ → ∀xφ)    &   ⊢ (φ → (χ → ∀xχ))    &   ⊢ (φ → (x = y → (ψ ↔ χ)))    ⇒   ⊢ (φ → ([y / x]ψ ↔ χ))
Theorem	sbie 904	Conversion of implicit substitution to explicit substitution.
⊢ (ψ → ∀xψ)    &   ⊢ (x = y → (φ ↔ ψ))    ⇒   ⊢ ([y / x]φ ↔ ψ)
Theorem	hbsb4 905	A variable not free remains so after substitution with a distinct variable.
⊢ (φ → ∀zφ)    ⇒   ⊢ (¬ ∀z z = y → ([y / x]φ → ∀z[y / x]φ))
Theorem	hbsb4t 906	A variable not free remains so after substitution with a distinct variable (closed form of hbsb4 905).
⊢ (∀x∀z(φ → ∀zφ) → (¬ ∀z z = y → ([y / x]φ → ∀z[y / x]φ)))
Theorem	ddelimf2 907	Proof of ddelimf 908 without using ax-11 801. This may be useful in a study to determine whether ax-11 801 can be derived from the others, which is currently unknown.
⊢ (φ → ∀xφ)    &   ⊢ (ψ → ∀zψ)    &   ⊢ (z = y → (φ ↔ ψ))    ⇒   ⊢ (¬ ∀x x = y → (ψ → ∀xψ))
Theorem	ddelimf 908	Version of ddelim 1000 without any variable restrictions.
⊢ (φ → ∀xφ)    &   ⊢ (ψ → ∀zψ)    &   ⊢ (z = y → (φ ↔ ψ))    ⇒   ⊢ (¬ ∀x x = y → (ψ → ∀xψ))
Theorem	ddelimdf 909	Deduction form of ddelimf 908. This version may be useful if we want to avoid ax-17 925 and use ax-16 922 instead.
⊢ (φ → ∀xφ)    &   ⊢ (φ → ∀zφ)    &   ⊢ (φ → (ψ → ∀xψ))    &   ⊢ (φ → (χ → ∀zχ))    &   ⊢ (φ → (z = y → (ψ ↔ χ)))    ⇒   ⊢ (φ → (¬ ∀x x = y → (χ → ∀xχ)))
Theorem	sbco 910	A composition law for substitution.
⊢ ([y / x][x / y]φ ↔ [y / x]φ)
Theorem	sbid2 911	An identity law for substitution.
⊢ (φ → ∀xφ)    ⇒   ⊢ ([y / x][x / y]φ ↔ φ)
Theorem	sbidm 912	An idempotent law for substitution.
⊢ ([y / x][y / x]φ ↔ [y / x]φ)
Theorem	sbco2 913	A composition law for substitution.
⊢ (φ → ∀zφ)    ⇒   ⊢ ([y / z][z / x]φ ↔ [y / x]φ)
Theorem	sbco2d 914	A composition law for substitution.
⊢ (φ → ∀xφ)    &   ⊢ (φ → ∀zφ)    &   ⊢ (φ → (ψ → ∀zψ))    ⇒   ⊢ (φ → ([y / z][z / x]ψ ↔ [y / x]ψ))
Theorem	sbco3 915	A composition law for substitution.
⊢ ([z / y][y / x]φ ↔ [z / x][x / y]φ)
Theorem	sbcom 916	A commutativity law for substitution.
⊢ ([y / z][y / x]φ ↔ [y / x][y / z]φ)
Theorem	sb5f1 917	Equivalence for substitution. Similar to Theorem 6.2 of [Quine] p. 40.
⊢ (φ → ∀xφ)    ⇒   ⊢ (φ ↔ ∀x(x = y → [x / y]φ))
Theorem	sb8 918	Substitution of variable in universal quantifier.
⊢ (φ → ∀yφ)    ⇒   ⊢ (∀xφ ↔ ∀y[y / x]φ)
Theorem	sb8e 919	Substitution of variable in existential quantifier.
⊢ (φ → ∀yφ)    ⇒   ⊢ (∃xφ ↔ ∃y[y / x]φ)
Theorem	sb9i 920	Commutation of quantification and substitution variables.
⊢ (∀x[x / y]φ → ∀y[y / x]φ)
Theorem	sb9 921	Commutation of quantification and substitution variables.
⊢ (∀x[x / y]φ ↔ ∀y[y / x]φ)
Axiom	ax-16 922	Axiom of Distinct Variables. The only axiom of predicate calculus requiring that variables be distinct (if we consider ax-17 925 below to be a metatheorem and not an axiom). Axiom scheme C16' in [Megill] p. 448 (p. 16 of the preprint). It apparently does not otherwise appear in the literature but is easily proved from textbook predicate calculus by cases. It is a somewhat bizarre axiom since the antecedent is always false in set theory (see dtru 1889) but nonetheless technically necessary as you can see from its uses.
⊢ (∀x x = y → (φ → ∀xφ))
Theorem	ax17eq 923	Theorem to add distinct quantifier to atomic formula.
⊢ (x = y → ∀z x = y)
Theorem	ax17el 924	Theorem to add distinct quantifier to atomic formula. (This theorem demonstrates the induction basis for ax-17 925 considered as a metatheorem. Do not use it for later proofs - use ax-17 925 instead, to avoid reference to the redundant ax-15 806.)
⊢ (x ∈ y → ∀z x ∈ y)
Axiom	ax-17 925	Axiom to quantify 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. If we allow ax-15 806 (not otherwise used in our development), this axiom is logically redundant since it is a metatheorem justified by induction on the number of primitive connectives in wff φ, using ax17eq 923 and ax17el 924 together hbne 699, hbal 700, and hbim 702. However if we omit this axiom our development would be quite inconvenient since we could work only with specific instances of wffs containing no wff variables - this axiom is effectively a definition of the concept of a set variable not occurring in a wff (as opposed to just two set variables being distinct).
⊢ (φ → ∀xφ)
Theorem	ax11a 926	This is a version of ax-11 801 when the variables are distinct. Axiom (C8) of [Monk2] p. 105.
⊢ (x = y → (φ → ∀x(x = y → φ)))
Theorem	a4b 927	A weaker version of a4a 842.
⊢ (x = y → (φ → ψ))    ⇒   ⊢ (∀xφ → ψ)
Theorem	a4b1 928	Infer specialization rule from substitution instance.
⊢ (x = y → (φ ↔ ψ))    ⇒   ⊢ (∀xφ → ψ)
Theorem	a4w 929	A weaker version of a4c 843.
⊢ (x = y → (φ → ψ))    ⇒   ⊢ (φ → ∃xψ)
Theorem	a4w1 930	Infer existence from a substitution instance.
⊢ (x = y → (φ ↔ ψ))    &   ⊢ ψ    ⇒   ⊢ ∃xφ
Theorem	eqvin.l2 931	A variable elimination law for equality. Lemma 15 of [Monk2] p. 109.
⊢ (∃z(x = z ∧ z = y) → x = y)
Theorem	eqvin 932	A variable introduction law for equality. Lemma 15 of [Monk2] p. 109.
⊢ (x = y ↔ ∃z(x = z ∧ z = y))
Theorem	a16g 933	A generalization of axiom ax-16 922.
⊢ (∀x x = y → (φ → ∀zφ))
Theorem	a16gb 934	A generalization of axiom ax-16 922.
⊢ (∀x x = y → (φ ↔ ∀zφ))
Theorem	bialdv 935	Formula-building rule for universal quantifier (deduction rule).
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (∀xψ ↔ ∀xχ))
Theorem	biexdv 936	Formula-building rule for existential quantifier (deduction rule).
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (∃xψ ↔ ∃xχ))
Theorem	bi2aldv 937	Formula-building rule for 2 existential quantifiers (deduction rule).
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (∀x∀yψ ↔ ∀x∀yχ))
Theorem	bi2exdv 938	Formula-building rule for 2 existential quantifiers (deduction rule).
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (∃x∃yψ ↔ ∃x∃yχ))
Theorem	bi3exdv 939	Formula-building rule for 3 existential quantifiers (deduction rule).
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (∃x∃y∃zψ ↔ ∃x∃y∃zχ))
Theorem	bi4exdv 940	Formula-building rule for 4 existential quantifiers (deduction rule).
⊢ (φ → (ψ ↔ χ))    ⇒   ⊢ (φ → (∃x∃y∃z∃wψ ↔ ∃x∃y∃z∃wχ))
Theorem	19.9rv 941	Special case of Theorem 19.9 of [Margaris] p. 89.
⊢ (φ ↔ ∃xφ)
Theorem	19.21v 942	Special case of Theorem 19.21 of [Margaris] p. 90. Notational convention: We sometimes suffix with "v" the label of a theorem eliminating a hypothesis such as (φ → ∀xφ) in 19.21 738 via the use of distinct variable conditions combined with ax-17 925. Conversely, we sometimes suffix with "f" the label of a theorem introducing such a hypothesis to eliminate the need for the distinct variable condition; e.g. euf 1011 derived from df-eu 1009. The "f" stands for "not free in" which is less restrictive than "does not occur in".
⊢ (∀x(φ → ψ) ↔ (φ → ∀xψ))
Theorem	19.21aiv 943	Inference from Theorem 19.21 of [Margaris] p. 90.
⊢ (φ → ψ)    ⇒   ⊢ (φ → ∀xψ)
Theorem	19.21aivv 944	Inference from Theorem 19.21 of [Margaris] p. 90.
⊢ (φ → ψ)    ⇒   ⊢ (φ → ∀x∀yψ)
Theorem	19.21adv 945	Deduction from Theorem 19.21 of [Margaris] p. 90.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → (ψ → ∀xχ))
Theorem	19.20dv 946	Deduction from Theorem 19.20 of [Margaris] p. 90.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → (∀xψ → ∀xχ))
Theorem	19.22dv 947	Deduction from Theorem 19.22 of [Margaris] p. 90.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → (∃xψ → ∃xχ))
Theorem	19.20dvv 948	Deduction from Theorem 19.22 of [Margaris] p. 90.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → (∀x∀yψ → ∀x∀yχ))
Theorem	19.22dvv 949	Deduction from Theorem 19.22 of [Margaris] p. 90.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → (∃x∃yψ → ∃x∃yχ))
Theorem	19.23v 950	Special case of Theorem 19.23 of [Margaris] p. 90.
⊢ (∀x(φ → ψ) ↔ (∃xφ → ψ))
Theorem	19.23vv 951	Theorem 19.23 of [Margaris] p. 90 extended to two variables.
⊢ (∀x∀y(φ → ψ) ↔ (∃x∃yφ → ψ))
Theorem	19.23aiv 952	Inference from Theorem 19.23 of [Margaris] p. 90.
⊢ (φ → ψ)    ⇒   ⊢ (∃xφ → ψ)
Theorem	19.23aivv 953	Inference from Theorem 19.23 of [Margaris] p. 90.
⊢ (φ → ψ)    ⇒   ⊢ (∃x∃yφ → ψ)
Theorem	19.23adv 954	Deduction from Theorem 19.23 of [Margaris] p. 90.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → (∃xψ → χ))
Theorem	19.23advv 955	Deduction from Theorem 19.23 of [Margaris] p. 90.
⊢ (φ → (ψ → χ))    ⇒   ⊢ (φ → (∃x∃yψ → χ))
Theorem	19.27v 956	Theorem 19.27 of [Margaris] p. 90.
⊢ (∀x(φ ∧ ψ) ↔ (∀xφ ∧ ψ))
Theorem	19.28v 957	Theorem 19.28 of [Margaris] p. 90.
⊢ (∀x(φ ∧ ψ) ↔ (φ ∧ ∀xψ))
Theorem	19.36v 958	Special case of Theorem 19.36 of [Margaris] p. 90.
⊢ (∃x(φ → ψ) ↔ (∀xφ → ψ))
Theorem	19.36aiv 959	Inference from Theorem 19.36 of [Margaris] p. 90.
⊢ ∃x(φ → ψ)    ⇒   ⊢ (∀xφ → ψ)
Theorem	19.12vv 960	Special case of 19.12 729 where its converse holds.
⊢ (∃x∀y(φ → ψ) ↔ ∀y∃x(φ → ψ))
Theorem	19.37v 961	Special case of Theorem 19.37 of [Margaris] p. 90.
⊢ (∃x(φ → ψ) ↔ (φ → ∃xψ))
Theorem	19.37aiv 962	Inference from Theorem 19.37 of [Margaris] p. 90.
⊢ ∃x(φ → ψ)    ⇒   ⊢ (φ → ∃xψ)
Theorem	19.41v 963	Special case of Theorem 19.41 of [Margaris] p. 90.
⊢ (∃x(φ ∧ ψ) ↔ (∃xφ ∧ ψ))
Theorem	19.41vv 964	Theorem 19.41 of [Margaris] p. 90 with 2 quantifiers.
⊢ (∃x∃y(φ ∧ ψ) ↔ (∃x∃yφ ∧ ψ))
Theorem	19.41vvv 965	Theorem 19.41 of [Margaris] p. 90 with 3 quantifiers.
⊢ (∃x∃y∃z(φ ∧ ψ) ↔ (∃x∃y∃zφ ∧ ψ))
Theorem	19.42v 966	Special case of Theorem 19.42 of [Margaris] p. 90.
⊢ (∃x(φ ∧ ψ) ↔ (φ ∧ ∃xψ))
Theorem	exdistr 967	Distribution of existential quantifiers.
⊢ (∃x∃y(φ ∧ ψ) ↔ ∃x(φ ∧ ∃yψ))
Theorem	19.42vv 968	Theorem 19.42 of [Margaris] p. 90 with 2 quantifiers.
⊢ (∃x∃y(φ ∧ ψ) ↔ (φ ∧ ∃x∃yψ))
Theorem	exdistr2 969	Distribution of existential quantifiers.
⊢ (∃x∃y∃z(φ ∧ ψ) ↔ ∃x(φ ∧ ∃y∃zψ))
Theorem	3exdistr 970	Distribution of existential quantifiers.
⊢ (∃x∃y∃z(φ ∧ ψ ∧ χ) ↔ ∃x(φ ∧ ∃y(ψ ∧ ∃zχ)))
Theorem	4exdistr 971	Distribution of existential quantifiers.
⊢ (∃x∃y∃z∃w((φ ∧ ψ) ∧ (χ ∧ θ)) ↔ ∃x(φ ∧ ∃y(ψ ∧ ∃z(χ ∧ ∃wθ))))
Theorem	cbvalv 972	Rule used to change bound variables with implicit substitution.
⊢ (x = y → (φ ↔ ψ))    ⇒   ⊢ (∀xφ ↔ ∀yψ)
Theorem	cbvexv 973	Rule used to change bound variables with implicit substitution.
⊢ (x = y → (φ ↔ ψ))    ⇒   ⊢ (∃xφ ↔ ∃yψ)
Theorem	cbval2 974	Rule used to change bound variables with implicit substitution.
⊢ (φ → ∀zφ)    &   ⊢ (φ → ∀wφ)    &   ⊢ (ψ → ∀xψ)    &   ⊢ (ψ → ∀yψ)    &   ⊢ ((x = z ∧ y = w) → (φ ↔ ψ))    ⇒   ⊢ (∀x∀yφ ↔ ∀z∀wψ)
Theorem	cbvex2 975	Rule used to change bound variables with implicit substitution.
⊢ (φ → ∀zφ)    &   ⊢ (φ → ∀wφ)    &   ⊢ (ψ → ∀xψ)    &   ⊢ (ψ → ∀yψ)    &   ⊢ ((x = z ∧ y = w) → (φ ↔ ψ))    ⇒   ⊢ (∃x∃yφ ↔ ∃z∃wψ)
Theorem	cbvex2v 976	Rule used to change bound variables with implicit substitution.
⊢ ((x = z ∧ y = w) → (φ ↔ ψ))    ⇒   ⊢ (∃x∃yφ ↔ ∃z∃wψ)
Theorem	cbvald 977	Deduction used to change bound variables with implicit substitution, particularly useful in conjunction with ddelim 1000.
⊢ (φ → ∀yφ)    &   ⊢ (φ → (ψ → ∀yψ))    &   ⊢ (φ → (x = y → (ψ ↔ χ)))    ⇒   ⊢ (φ → (∀xψ ↔ ∀yχ))
Theorem	cbvexd 978	Deduction used to change bound variables with implicit substitution, particularly useful in conjunction with ddelim 1000.
⊢ (φ → ∀yφ)    &   ⊢ (φ → (ψ → ∀yψ))    &   ⊢ (φ → (x = y → (ψ ↔ χ)))    ⇒   ⊢ (φ → (∃xψ ↔ ∃yχ))
Theorem	cbvex4v 979	Rule used to change bound variables with implicit substitution.
⊢ ((x = v ∧ y = u) → (φ ↔ ψ))    &   ⊢ ((z = f ∧ w = g) → (ψ ↔ χ))    ⇒   ⊢ (∃x∃y∃z∃wφ ↔ ∃v∃u∃f∃gχ)
Theorem	eeanv 980	Rearrange existential quantifiers.
⊢ (∃x∃y(φ ∧ ψ) ↔ (∃xφ ∧ ∃yψ))
Theorem	eeeanv 981	Rearrange existential quantifiers.
⊢ (∃x∃y∃z(φ ∧ ψ ∧ χ) ↔ (∃xφ ∧ ∃yψ ∧ ∃zχ))
Theorem	ee4anv 982	Rearrange existential quantifiers.
⊢ (∃x∃y∃z∃w(φ ∧ ψ) ↔ (∃x∃yφ ∧ ∃z∃wψ))
Theorem	nexdv 983	Deduction for generalization rule for negated wff.
⊢ (φ → ¬ ψ)    ⇒   ⊢ (φ → ¬ ∃xψ)
Theorem	chv 984	Implicit substitution of y for x into a theorem.
⊢ (x = y → (φ ↔ ψ))    &   ⊢ φ    ⇒   ⊢ ψ
Theorem	cleljust 985	When the class variables in definition df-clel 1099 are replaced with set 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 set variables in wel 803 with the class variables in wcel 1092.
⊢ (x ∈ y ↔ ∃z(z = x ∧ z ∈ y))
Theorem	hbs1 986	x is not free in [y / x]φ when x and y are distinct.
⊢ ([y / x]φ → ∀x[y / x]φ)
Theorem	hbsb 987	If z is not free in φ, it is not free in [y / x]φ when y and z are distinct.
⊢ (φ → ∀zφ)    ⇒   ⊢ ([y / x]φ → ∀z[y / x]φ)
Theorem	sb5 988	Equivalence for substitution. Similar to Theorem 6.1 of [Quine] p. 40.
⊢ ([y / x]φ ↔ ∃x(x = y ∧ φ))
Theorem	sb6 989	Equivalence for substitution. Compare Theorem 6.2 of [Quine] p. 40.
⊢ ([y / x]φ ↔ ∀x(x = y → φ))
Theorem	sb6a 990	Equivalence for substitution. Compare Theorem 6.2 of [Quine] p. 40.
⊢ ([y / x]φ ↔ ∀x(x = y → [x / y]φ))
Theorem	sb7 991	An alternate definition of proper substitution df-sb 853. By introducing a dummy variable z in the definiens, we are able to eliminate any distinct variable restrictions among the variables x, y, and φ of the definiendum. Compare Definition 2.1'' of [Quine] p. 17, which is obtained from this theorem by applying df-clab 1093.
⊢ ([y / x]φ ↔ ∃z(z = y ∧ ∃x(x = z ∧ φ)))
Theorem	sbcom2 992	Commutativity law for substitution. Used in proof of Theorem 9.7 of [Megill] p. 449 (p. 16 of the preprint).
⊢ ([w / z][y / x]φ ↔ [y / x][w / z]φ)
Theorem	sbid2v 993	An identity law for substitution. Used in proof of Theorem 9.7 of [Megill] p. 449 (p. 16 of the preprint).
⊢ ([y / x][x / y]φ ↔ φ)
Theorem	sbelx 994	Elimination of substitution.
⊢ (φ ↔ ∃x(x = y ∧ [x / y]φ))
Theorem	sbel2x 995	Elimination of double substitution.
⊢ (φ ↔ ∃x∃y((x = z ∧ y = w) ∧ [y / w][x / z]φ))
Theorem	sbal1 996	A theorem used in elimination of disjoint variable restriction on x and y by replacing it with a distinctor ¬ ∀xx = z.
⊢ (¬ ∀x x = z → ([z / y]∀xφ ↔ ∀x[z / y]φ))
Theorem	sbal 997	Move universal quantifier in and out of substitution.
⊢ ([z / y]∀xφ ↔ ∀x[z / y]φ)
Theorem	sbex 998	Move existential quantifier in and out of substitution.
⊢ ([z / y]∃xφ ↔ ∃x[z / y]φ)
Theorem	sbalv 999	Quantify with new variable inside substitution.
⊢ ([y / x]φ ↔ ψ)    ⇒   ⊢ ([y / x]∀zφ ↔ ∀zψ)
Theorem	ddelim 1000	This theorem can be used to eliminate a distinct variable restriction on x and z and replace it with the "distinctor" ¬ ∀xx = y as an antecedent. φ is considered to contain z, and ψ to have z replaced with y, and we don't require that x and y be distinct (if they aren't, the distinctor will become false and "protect" the consequent).
⊢ (φ → ∀xφ)    &   ⊢ (z = y → (φ ↔ ψ))    ⇒   ⊢ (¬ ∀x x = y → (ψ → ∀xψ))