mmtheorems34 - Metamath Proof Explorer

Jump to page: Contents + 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-5800 59 5801-5900 60 5901-6000 61 6001-6100 62 6101-6200 63 6201-6300 64 6301-6400 65 6401-6500 66 6501-6600 67 6601-6700 68 6701-6800 69 6801-6900 70 6901-7000 71 7001-7100 72 7101-7200 73 7201-7300 74 7301-7400 75 7401-7500 76 7501-7600 77 7601-7700 78 7701-7800 79 7801-7900 80 7901-8000 81 8001-8100 82 8101-8200 83 8201-8300 84 8301-8400 85 8401-8500 86 8501-8600 87 8601-8700 88 8701-8800 89 8801-8900 90 8901-9000 91 9001-9100 92 9101-9200 93 9201-9300 94 9301-9400 95 9401-9500 96 9501-9600 97 9601-9700 98 9701-9800 99 9801-9900 100 9901-10000 101 10001-10100 102 10101-10200 103 10201-10300 104 10301-10400 105 10401-10500 106 10501-10600 107 10601-10700 108 10701-10800 109 10801-10900 110 10901-11000 111 11001-11100 112 11101-11200 113 11201-11300 114 11301-11400 115 11401-11500 116 11501-11600 117 11601-11700 118 11701-11800 119 11801-11900 120 11901-12000 121 12001-12100 122 12101-12200 123 12201-12229

Statement List for Metamath Proof Explorer - 3301-3400 - Page 34 of 123

Type	Label	Description
Statement
Theorem	ralxp 3301	Universal quantification restricted to a cross product is equivalent to a double restricted quantification. The hypothesis specifies an implicit substitution.
|- (x = <.y, z>. -> (ph <-> ps))   =>   |- (A.x e. (A X. B)ph <-> A.y e. A A.z e. B ps)
Theorem	rexxp 3302	Existential quantification restricted to a cross product is equivalent to a double restricted quantification.
|- (x = <.y, z>. -> (ph <-> ps))   =>   |- (E.x e. (A X. B)ph <-> E.y e. A E.z e. B ps)
Theorem	ralxpf 3303	Version of ralxp 3301 with bound-variable hypotheses.
|- (ph -> A.yph)   &   |- (ph -> A.zph)   &   |- (ps -> A.xps)   &   |- (x = <.y, z>. -> (ph <-> ps))   =>   |- (A.x e. (A X. B)ph <-> A.y e. A A.z e. B ps)
Theorem	rexxpf 3304	Version of rexxp 3302 with bound-variable hypotheses.
|- (ph -> A.yph)   &   |- (ph -> A.zph)   &   |- (ps -> A.xps)   &   |- (x = <.y, z>. -> (ph <-> ps))   =>   |- (E.x e. (A X. B)ph <-> E.y e. A E.z e. B ps)
Theorem	iunxpf 3305	Indexed union on a cross product is equals a double indexed union. The hypothesis specifies an implicit substitution.
|- (w e. C -> A.y w e. C)   &   |- (w e. C -> A.z w e. C)   &   |- (w e. D -> A.x w e. D)   &   |- (x = <.y, z>. -> C = D)   =>   |- U_x e. (A X. B)C = U_y e. A U_z e. B D
Theorem	opthprc 3306	Justification theorem for an ordered pair definition that works for any classes, including proper classes. This is a possible definition implied by the footnote in [Jech] p. 78, which says, "The sophisticated reader will not object to our use of a pair of classes."
|- (((A X. {(/)}) u. (B X. {{(/)}})) = ((C X. {(/)}) u. (D X. {{(/)}})) <-> (A = C /\ B = D))
Theorem	brelg 3307	Two things in a binary relation belong to the relation's domain.
|- R (_ (C X. D)   =>   |- (B e. S -> (ARB -> (A e. C /\ B e. D)))
Theorem	brel 3308	Membership in superset of binary relation.
|- B e. V   &   |- R (_ (C X. D)   =>   |- (ARB -> (A e. C /\ B e. D))
Theorem	elxp3 3309	Membership in a cross product.
|- (A e. (B X. C) <-> E.xE.y(<.x, y>. = A /\ <.x, y>. e. (B X. C)))
Theorem	xpundi 3310	Distributive law for cross product over union. Theorem 103 of [Suppes] p. 52.
|- (A X. (B u. C)) = ((A X. B) u. (A X. C))
Theorem	xpundir 3311	Distributive law for cross product over union. Similar to Theorem 103 of [Suppes] p. 52.
|- ((A u. B) X. C) = ((A X. C) u. (B X. C))
Theorem	xpun 3312	The cross product of two unions.
|- ((A u. B) X. (C u. D)) = (((A X. C) u. (A X. D)) u. ((B X. C) u. (B X. D)))
Theorem	elvv 3313	Membership in universal class of ordered pairs.
|- (A e. (V X. V) <-> E.xE.y A = <.x, y>.)
Theorem	elvvv 3314	Membership in universal class of ordered triples.
|- (A e. ((V X. V) X. V) <-> E.xE.yE.z A = <.<.x, y>., z>.)
Theorem	elvvuni 3315	An ordered pair contains its union.
|- (A e. (V X. V) -> U.A e. A)
Theorem	xpss 3316	A cross product is included in the ordered pair universe. Exercise 3 of [TakeutiZaring] p. 25.
|- (A X. B) (_ (V X. V)
Theorem	brinxp2 3317	Intersection of binary relation with cross product.
|- (B e. S -> (A(R i^i (C X. D))B <-> (A e. C /\ B e. D /\ ARB)))
Theorem	brinxp 3318	Intersection of binary relation with cross product.
|- ((A e. C /\ B e. D) -> (ARB <-> A(R i^i (C X. D))B))
Theorem	weinxp 3319	Intersection of well-ordering with cross product of its field.
|- (R We A <-> (R i^i (A X. A)) We A)
Theorem	opabssxp 3320	An abstraction relation is a subset of a related cross product.
|- {<.x, y>. | ((x e. A /\ y e. B) /\ ph)} (_ (A X. B)
Theorem	optocl 3321	Implicit substitution of class for ordered pair.
|- D = (B X. C)   &   |- (<.x, y>. = A -> (ph <-> ps))   &   |- ((x e. B /\ y e. C) -> ph)   =>   |- (A e. D -> ps)
Theorem	2optocl 3322	Implicit substitution of classes for ordered pairs.
|- R = (C X. D)   &   |- (<.x, y>. = A -> (ph <-> ps))   &   |- (<.z, w>. = B -> (ps <-> ch))   &   |- (((x e. C /\ y e. D) /\ (z e. C /\ w e. D)) -> ph)   =>   |- ((A e. R /\ B e. R) -> ch)
Theorem	3optocl 3323	Implicit substitution of classes for ordered pairs.
|- R = (D X. F)   &   |- (<.x, y>. = A -> (ph <-> ps))   &   |- (<.z, w>. = B -> (ps <-> ch))   &   |- (<.v, u>. = C -> (ch <-> th))   &   |- (((x e. D /\ y e. F) /\ (z e. D /\ w e. F) /\ (v e. D /\ u e. F)) -> ph)   =>   |- ((A e. R /\ B e. R /\ C e. R) -> th)
Theorem	opbrop 3324	Ordered pair membership in a relation. Special case.
|- (((z = A /\ w = B) /\ (v = C /\ u = D)) -> (ph <-> ps))   &   |- R = {<.x, y>. | ((x e. (S X. S) /\ y e. (S X. S)) /\ E.zE.wE.vE.u((x = <.z, w>. /\ y = <.v, u>.) /\ ph))}   =>   |- (((A e. S /\ B e. S) /\ (C e. S /\ D e. S)) -> (<.A, B>.R<.C, D>. <-> ps))
Theorem	xp0r 3325	The cross product with the empty set is empty. Part of Theorem 3.13(ii) of [Monk1] p. 37.
|- ((/) X. A) = (/)
Theorem	0nelxp 3326	The empty set is not a member of a cross product.
|- -. (/) e. (A X. B)
Theorem	0nelelxp 3327	A member of a cross product (ordered pair) doesn't contain the empty set.
|- (C e. (A X. B) -> -. (/) e. C)
Theorem	onxpdisj 3328	Ordinal numbers and ordered pairs are disjoint collections. This theorem can be used if we want to extend a set of ordinal numbers or ordered pairs with disjoint elements. See also snsn0non 3088.
|- (On i^i (V X. V)) = (/)
Theorem	onnev 3329	The class of ordinal numbers is not equal to the universe.
|- On =/= V
Theorem	releq 3330	Equality theorem for the relation predicate.
|- (A = B -> (Rel A <-> Rel B))
Theorem	releqi 3331	Equality inference for the relation predicate.
|- A = B   =>   |- (Rel A <-> Rel B)
Theorem	hbrel 3332	Bound-variable hypothesis builder for a relation.
|- (y e. A -> A.x y e. A)   =>   |- (Rel A -> A.xRel A)
Theorem	relss 3333	Subclass theorem for relation predicate. Theorem 2 of [Suppes] p. 58.
|- (A (_ B -> (Rel B -> Rel A))
Theorem	ssrel 3334	A subclass relationship depends only on a relation's ordered pairs. Theorem 3.2(i) of [Monk1] p. 33.
|- (Rel A -> (A (_ B <-> A.xA.y(<.x, y>. e. A -> <.x, y>. e. B)))
Theorem	eqrel 3335	Extensionality principle for relations. Theorem 3.2(ii) of [Monk1] p. 33.
|- ((Rel A /\ Rel B) -> (A = B <-> A.xA.y(<.x, y>. e. A <-> <.x, y>. e. B)))
Theorem	relssi 3336	Inference from subclass principle for relations.
|- Rel A   &   |- (<.x, y>. e. A -> <.x, y>. e. B)   =>   |- A (_ B
Theorem	relssdv 3337	Deduction from subclass principle for relations.
|- (ph -> Rel A)   &   |- (ph -> (<.x, y>. e. A -> <.x, y>. e. B))   =>   |- (ph -> A (_ B)
Theorem	eqrelriv 3338	Inference from extensionality principle for relations.
|- Rel A   &   |- Rel B   &   |- (<.x, y>. e. A <-> <.x, y>. e. B)   =>   |- A = B
Theorem	eqbrriv 3339	Inference from extensionality principle for relations.
|- Rel A   &   |- Rel B   &   |- (xAy <-> xBy)   =>   |- A = B
Theorem	ssrelrel 3340	A subclass relationship determined by ordered triples. Use relrelss 3618 to express the antecedent in terms of the relation predicate.
|- (A (_ ((V X. V) X. V) -> (A (_ B <-> A.xA.yA.z(<.<.x, y>., z>. e. A -> <.<.x, y>., z>. e. B)))
Theorem	eqrelrel 3341	Extensionality principle for ordered triples (used by 2-place operations df-oprab 4024), analogous to eqrel 3335. Use relrelss 3618 to express the antecedent in terms of the relation predicate.
|- ((A u. B) (_ ((V X. V) X. V) -> (A = B <-> A.xA.yA.z(<.<.x, y>., z>. e. A <-> <.<.x, y>., z>. e. B)))
Theorem	elrel 3342	A member of a relation is an ordered pair.
|- ((Rel R /\ A e. R) -> E.xE.y A = <.x, y>.)
Theorem	relsn 3343	A singleton of an ordered pair is a relation.
|- A e. V   =>   |- Rel {<.A, B>.}
Theorem	relxp 3344	A cross product is a relation. Theorem 3.13(i) of [Monk1] p. 37.
|- Rel (A X. B)
Theorem	ssxp 3345	Subset theorem for cross product. Generalization of Theorem 101 of [Suppes] p. 52.
|- ((A (_ B /\ C (_ D) -> (A X. C) (_ (B X. D))
Theorem	xpsspw 3346	A cross product is included in the power of the power of the union of its arguments.
|- (A X. B) (_ P~P~(A u. B)
Theorem	unixpss 3347	The double class union of a cross product is included in the union of its arguments.
|- U.U.(A X. B) (_ (A u. B)
Theorem	xpexg 3348	The cross product of two sets is a set. Proposition 6.2 of [TakeutiZaring] p. 23.
|- ((A e. C /\ B e. D) -> (A X. B) e. V)
Theorem	xpex 3349	The cross product of two sets is a set. Proposition 6.2 of [TakeutiZaring] p. 23.
|- A e. V   &   |- B e. V   =>   |- (A X. B) e. V
Theorem	relun 3350	The union of two relations is a relation. Compare Exercise 5 of [TakeutiZaring] p. 25.
|- (Rel (A u. B) <-> (Rel A /\ Rel B))
Theorem	relin1 3351	The intersection with a relation is a relation.
|- (Rel A -> Rel (A i^i B))
Theorem	relin2 3352	The intersection with a relation is a relation.
|- (Rel B -> Rel (A i^i B))
Theorem	reldif 3353	A difference cutting down a relation is a relation.
|- (Rel A -> Rel (A \ B))
Theorem	reliun 3354	An indexed union is a relation iff each member of its indexed family is a relation.
|- (Rel U_x e. A B <-> A.x e. A Rel B)
Theorem	rel0 3355	The empty set is a relation.
|- Rel (/)
Theorem	reluni 3356	Union law for relations. Exercise 6 of [TakeutiZaring] p. 25 and its converse.
|- (Rel U.A <-> A.x e. A Rel x)
Theorem	relopab 3357	A class of ordered pairs is a relation.
|- Rel {<.x, y>. | ph}
Theorem	reli 3358	The identity relation is a relation. Part of Exercise 4.12(p) of [Mendelson] p. 235.
|- Rel I
Theorem	rele 3359	The membership relation is a relation.
|- Rel E
Theorem	opabid2 3360	A relation expressed as an ordered pair abstraction.
|- (Rel A -> {<.x, y>. | <.x, y>. e. A} = A)
Theorem	inopab 3361	Intersection of two ordered pair class abstractions.
|- ({<.x, y>. | ph} i^i {<.x, y>. | ps}) = {<.x, y>. | (ph /\ ps)}
Theorem	inxp 3362	The intersection of two cross products. Exercise 9 of [TakeutiZaring] p. 25.
|- ((A X. B) i^i (C X. D)) = ((A i^i C) X. (B i^i D))
Theorem	xpindi 3363	Distributive law for cross product over intersection. Theorem 102 of [Suppes] p. 52.
|- (A X. (B i^i C)) = ((A X. B) i^i (A X. C))
Theorem	xpindir 3364	Distributive law for cross product over intersection. Similar to Theorem 102 of [Suppes] p. 52.
|- ((A i^i B) X. C) = ((A X. C) i^i (B X. C))
Theorem	relop 3365	A necessary and sufficient condition for a Kuratowski ordered pair to be a relation.
|- A e. V   &   |- B e. V   =>   |- (Rel <.A, B>. <-> E.xE.y(A = {x} /\ B = {x, y}))
Theorem	ideqg 3366	For sets, the identity relation is the same as equality.
|- (B e. C -> (AIB <-> A = B))
Theorem	ideq 3367	For sets, the identity relation is the same as equality.
|- B e. V   =>   |- (AIB <-> A = B)
Theorem	ididg 3368	A set is identical to itself.
|- (A e. B -> AIA)
Theorem	opelxpex2 3369	The second member of an ordered pair of classes in a cross product exists when the order pair doesn't belong to I.
|- (<.A, B>. e. ((C X. D) \ I) -> B e. V)
Theorem	issetid 3370	Two ways of expressing set existence.
|- (A e. V <-> AIV)
Theorem	coeq1 3371	Equality theorem for composition of two classes.
|- (A = B -> (A o. C) = (B o. C))
Theorem	coeq2 3372	Equality theorem for composition of two classes.
|- (A = B -> (C o. A) = (C o. B))
Theorem	coeq1i 3373	Equality inference for composition of two classes.
|- A = B   =>   |- (A o. C) = (B o. C)
Theorem	coeq2i 3374	Equality inference for composition of two classes.
|- A = B   =>   |- (C o. A) = (C o. B)
Theorem	coeq1d 3375	Equality deduction for composition of two classes.
|- (ph -> A = B)   =>   |- (ph -> (A o. C) = (B o. C))
Theorem	coeq2d 3376	Equality deduction for composition of two classes.
|- (ph -> A = B)   =>   |- (ph -> (C o. A) = (C o. B))
Theorem	hbco 3377	Bound-variable hypothesis builder for function value.
|- (y e. A -> A.x y e. A)   &   |- (y e. B -> A.x y e. B)   =>   |- (y e. (A o. B) -> A.x y e. (A o. B))
Theorem	opelco 3378	Ordered pair membership in a composition.
|- A e. V   &   |- B e. V   =>   |- (<.A, B>. e. (C o. D) <-> E.x(ADx /\ xCB))
Theorem	brco 3379	Binary relation on a composition.
|- A e. V   &   |- B e. V   =>   |- (A(C o. D)B <-> E.x(ADx /\ xCB))
Theorem	opelco2g 3380	Ordered pair membership in a composition.
|- ((A e. R /\ B e. S) -> (<.A, B>. e. (C o. D) <-> E.x(<.A, x>. e. D /\ <.x, B>. e. C)))
Theorem	cnvss 3381	Subset theorem for converse.
|- (A (_ B -> `'A (_ `'B)
Theorem	cnveq 3382	Equality theorem for converse.
|- (A = B -> `'A = `'B)
Theorem	cnveqi 3383	Equality theorem for converse.
|- A = B   =>   |- `'A = `'B
Theorem	elcnv 3384	Membership in a converse. Equation 5 of [Suppes] p. 62.
|- (A e. `'R <-> E.xE.y(A = <.x, y>. /\ yRx))
Theorem	elcnv2 3385	Membership in a converse. Equation 5 of [Suppes] p. 62.
|- (A e. `'R <-> E.xE.y(A = <.x, y>. /\ <.y, x>. e. R))
Theorem	hbcnv 3386	Bound-variable hypothesis builder for converse.
|- (y e. A -> A.x y e. A)   =>   |- (y e. `'A -> A.x y e. `'A)
Theorem	opelcnvg 3387	Ordered-pair membership in converse.
|- ((A e. C /\ B e. D) -> (<.A, B>. e. `'R <-> <.B, A>. e. R))
Theorem	brcnvg 3388	The converse of a binary relation swaps arguments. Theorem 11 of [Suppes] p. 61.
|- ((A e. C /\ B e. D) -> (A`'RB <-> BRA))
Theorem	opelcnv 3389	Ordered-pair membership in converse.
|- A e. V   &   |- B e. V   =>   |- (<.A, B>. e. `'R <-> <.B, A>. e. R)
Theorem	brcnv 3390	The converse of a binary relation swaps arguments. Theorem 11 of [Suppes] p. 61.
|- A e. V   &   |- B e. V   =>   |- (A`'RB <-> BRA)
Theorem	cnvco 3391	Distributive law of converse over class composition. Theorem 26 of [Suppes] p. 64.
|- `'(A o. B) = (`'B o. `'A)
Theorem	cnvuni 3392	The converse of a class union is the (indexed) union of the converses of its members.
|- `'U.A = U_x e. A `'x
Theorem	dfdm3 3393	Alternate definition of domain. Definition 6.5(1) of [TakeutiZaring] p. 24.
|- dom A = {x | E.y<.x, y>. e. A}
Theorem	dfrn2 3394	Alternate definition of range. Definition 4 of [Suppes] p. 60.
|- ran A = {y | E.x xAy}
Theorem	dfrn3 3395	Alternate definition of range. Definition 6.5(2) of [TakeutiZaring] p. 24.
|- ran A = {y | E.x<.x, y>. e. A}
Theorem	dfdm4 3396	Alternate definition of domain.
|- dom A = ran `' A
Theorem	dfdmf 3397	Definition of domain, using bound-variable hypotheses instead of distinct variable conditions.
|- (z e. A -> A.x z e. A)   &   |- (z e. A -> A.y z e. A)   =>   |- dom A = {x | E.y<.x, y>. e. A}
Theorem	eldm 3398	Membership in a domain. Theorem 4 of [Suppes] p. 59.
|- A e. V   =>   |- (A e. dom B <-> E.y ABy)
Theorem	eldm2 3399	Membership in a domain. Theorem 4 of [Suppes] p. 59.
|- A e. V   =>   |- (A e. dom B <-> E.y<.A, y>. e. B)
Theorem	eldm2g 3400	Domain membership. Theorem 4 of [Suppes] p. 59.
|- (A e. C -> (A e. dom B <-> E.y<.A, y>. e. B))