Home New Foundations ExplorerTheorem List (p. 51 of 64) < Previous  Next > Bad symbols? Use Firefox (or GIF version for IE).

Theorem List for New Foundations Explorer - 5001-5100   *Has distinct variable group(s)
TypeLabelDescription
Statement

Theoremssdmres 5001 A domain restricted to a subclass equals the subclass. (Contributed by set.mm contributors, 2-Mar-1997.) (Revised by set.mm contributors, 28-Aug-2004.)
(A dom B ↔ dom (B A) = A)

Theoremresss 5002 A class includes its restriction. Exercise 15 of [TakeutiZaring] p. 25. (Contributed by set.mm contributors, 2-Aug-1994.)
(A B) A

Theoremrescom 5003 Commutative law for restriction. (Contributed by set.mm contributors, 27-Mar-1998.)
((A B) C) = ((A C) B)

Theoremssres 5004 Subclass theorem for restriction. (Contributed by set.mm contributors, 16-Aug-1994.)
(A B → (A C) (B C))

Theoremssres2 5005 Subclass theorem for restriction. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 22-Mar-1998.) (Revised by set.mm contributors, 27-Aug-2011.)
(A B → (C A) (C B))

Theoremrelres 5006 A restriction is a relation. Exercise 12 of [TakeutiZaring] p. 25. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 2-Aug-1994.) (Revised by set.mm contributors, 27-Aug-2011.)
Rel (A B)

Theoremresabs1 5007 Absorption law for restriction. Exercise 17 of [TakeutiZaring] p. 25. (Contributed by set.mm contributors, 9-Aug-1994.)
(B C → ((A C) B) = (A B))

Theoremresabs2 5008 Absorption law for restriction. (Contributed by set.mm contributors, 27-Mar-1998.)
(B C → ((A B) C) = (A B))

Theoremresidm 5009 Idempotent law for restriction. (Contributed by set.mm contributors, 27-Mar-1998.)
((A B) B) = (A B)

Theoremelres 5010* Membership in a restriction. (Contributed by Scott Fenton, 17-Mar-2011.)
(A (B C) ↔ x C y(A = x, y x, y B))

Theoremelsnres 5011* Memebership in restriction to a singleton. (Contributed by Scott Fenton, 17-Mar-2011.)
C V       (A (B {C}) ↔ y(A = C, y C, y B))

Theoremrelssres 5012 Simplification law for restriction. (Contributed by set.mm contributors, 16-Aug-1994.) (Revised by set.mm contributors, 15-Mar-2004.)
((Rel A dom A B) → (A B) = A)

Theoremresdm 5013 A relation restricted to its domain equals itself. (Contributed by set.mm contributors, 12-Dec-2006.)
(Rel A → (A dom A) = A)

Theoremresopab 5014* Restriction of a class abstraction of ordered pairs. (Contributed by set.mm contributors, 5-Nov-2002.)
({x, y φ} A) = {x, y (x A φ)}

Theoremiss 5015 A subclass of the identity function is the identity function restricted to its domain. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 13-Dec-2003.) (Revised by set.mm contributors, 27-Aug-2011.)
(A I ↔ A = ( I dom A))

Theoremresopab2 5016* Restriction of a class abstraction of ordered pairs. (Contributed by set.mm contributors, 24-Aug-2007.)
(A B → ({x, y (x B φ)} A) = {x, y (x A φ)})

Theoremdfres2 5017* Alternate definition of the restriction operation. (Contributed by Mario Carneiro, 5-Nov-2013.)
(R A) = {x, y (x A xRy)}

Theoremopabresid 5018* The restricted identity expressed with the class builder. (Contributed by FL, 25-Apr-2012.)
{x, y (x A y = x)} = ( I A)

Theoremdmresi 5019 The domain of a restricted identity function. (Contributed by set.mm contributors, 27-Aug-2004.)
dom ( I A) = A

Theoremresid 5020 Any relation restricted to the universe is itself. (Contributed by set.mm contributors, 16-Mar-2004.)
(Rel A → (A V) = A)

Theoremresima 5021 A restriction to an image. (Contributed by set.mm contributors, 29-Sep-2004.)
((A B) “ B) = (AB)

Theoremresima2 5022 Image under a restricted class. (Contributed by FL, 31-Aug-2009.)
(B C → ((A C) “ B) = (AB))

Theoremimadmrn 5023 The image of the domain of a class is the range of the class. (Contributed by set.mm contributors, 14-Aug-1994.)
(A “ dom A) = ran A

Theoremimassrn 5024 The image of a class is a subset of its range. Theorem 3.16(xi) of [Monk1] p. 39. (Contributed by set.mm contributors, 31-Mar-1995.)
(AB) ran A

Theoremimai 5025 Image under the identity relation. Theorem 3.16(viii) of [Monk1] p. 38. (Contributed by set.mm contributors, 30-Apr-1998.)
( I “ A) = A

Theoremrnresi 5026 The range of the restricted identity function. (Contributed by set.mm contributors, 27-Aug-2004.)
ran ( I A) = A

Theoremresiima 5027 The image of a restriction of the identity function. (Contributed by FL, 31-Dec-2006.)
(B A → (( I A) “ B) = B)

Theoremima0 5028 Image of the empty set. Theorem 3.16(ii) of [Monk1] p. 38. (Contributed by set.mm contributors, 20-May-1998.)
(A) =

Theorem0ima 5029 Image under the empty relation. (Contributed by FL, 11-Jan-2007.)
(A) =

Theoremimadisj 5030 A class whose image under another is empty is disjoint with the other's domain. (Contributed by FL, 24-Jan-2007.)
((AB) = ↔ (dom AB) = )

Theoremcnvimass 5031 A preimage under any class is included in the domain of the class. (Contributed by FL, 29-Jan-2007.)
(AB) dom A

Theoremcnvimarndm 5032 The preimage of the range of a class is the domain of the class. (Contributed by Jeff Hankins, 15-Jul-2009.)
(A “ ran A) = dom A

Theoremimasn 5033* The image of a singleton. (Contributed by set.mm contributors, 9-Jan-2015.)
(R “ {A}) = {y ARy}

Theoremelimasn 5034 Membership in an image of a singleton. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 15-Mar-2004.) (Revised by set.mm contributors, 27-Aug-2011.)
(C (A “ {B}) ↔ B, C A)

Theoremeliniseg 5035 Membership in an initial segment. The idiom (A “ {B}), meaning {x xAB}, is used to specify an initial segment in (for example) Definition 6.21 of [TakeutiZaring] p. 30. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 28-Apr-2004.) (Revised by set.mm contributors, 27-Aug-2011.)
(C (A “ {B}) ↔ CAB)

Theoremepini 5036 Any set is equal to its preimage under the converse epsilon relation. (Contributed by Mario Carneiro, 9-Mar-2013.)
A V       ( E “ {A}) = A

Theoreminiseg 5037* An idiom that signifies an initial segment of an ordering, used, for example, in Definition 6.21 of [TakeutiZaring] p. 30. (Contributed by set.mm contributors, 28-Apr-2004.)
(A “ {B}) = {x xAB}

Theoremimass1 5038 Subset theorem for image. (Contributed by set.mm contributors, 16-Mar-2004.)
(A B → (AC) (BC))

Theoremimass2 5039 Subset theorem for image. Exercise 22(a) of [Enderton] p. 53. (Contributed by set.mm contributors, 22-Mar-1998.)
(A B → (CA) (CB))

Theoremndmima 5040 The image of a singleton outside the domain is empty. (Contributed by set.mm contributors, 22-May-1998.)
A dom B → (B “ {A}) = )

Theoremrelcnv 5041 A converse is a relation. Theorem 12 of [Suppes] p. 62. (Contributed by set.mm contributors, 29-Oct-1996.)
Rel A

Theoremrelco 5042 A composition is a relation. Exercise 24 of [TakeutiZaring] p. 25. (Contributed by set.mm contributors, 26-Jan-1997.)
Rel (A B)

Theoremcotr 5043* Two ways of saying a relation is transitive. Definition of transitivity in [Schechter] p. 51. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 27-Dec-1996.) (Revised by set.mm contributors, 27-Aug-2011.)
((R R) Rxyz((xRy yRz) → xRz))

Theoremcnvsym 5044* Two ways of saying a relation is symmetric. Similar to definition of symmetry in [Schechter] p. 51. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 28-Dec-1996.) (Revised by set.mm contributors, 27-Aug-2011.)
(R Rxy(xRyyRx))

Theoremintasym 5045* Two ways of saying a relation is antisymmetric. Definition of antisymmetry in [Schechter] p. 51. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 9-Sep-2004.) (Revised by set.mm contributors, 27-Aug-2011.)
((RR) I ↔ xy((xRy yRx) → x = y))

Theoremintirr 5046* Two ways of saying a relation is irreflexive. Definition of irreflexivity in [Schechter] p. 51. (Contributed by NM, 9-Sep-2004.) (Revised by Andrew Salmon, 27-Aug-2011.)
((R ∩ I ) = x ¬ xRx)

Theoremcnvopab 5047* The converse of a class abstraction of ordered pairs. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 11-Dec-2003.) (Revised by set.mm contributors, 27-Aug-2011.)
{x, y φ} = {y, x φ}

Theoremcnv0 5048 The converse of the empty set. (Contributed by set.mm contributors, 6-Apr-1998.)
=

Theoremcnvi 5049 The converse of the identity relation. Theorem 3.7(ii) of [Monk1] p. 36. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 26-Apr-1998.) (Revised by set.mm contributors, 27-Aug-2011.)
I = I

Theoremcnvun 5050 The converse of a union is the union of converses. Theorem 16 of [Suppes] p. 62. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 25-Mar-1998.) (Revised by set.mm contributors, 27-Aug-2011.)
(AB) = (AB)

Theoremcnvdif 5051 Distributive law for converse over set difference. (Contributed by set.mm contributors, 26-Jun-2014.)
(A B) = (A B)

Theoremcnvin 5052 Distributive law for converse over intersection. Theorem 15 of [Suppes] p. 62. (Contributed by set.mm contributors, 25-Mar-1998.) (Revised by set.mm contributors, 26-Jun-2014.)
(AB) = (AB)

Theoremrnun 5053 Distributive law for range over union. Theorem 8 of [Suppes] p. 60. (Contributed by set.mm contributors, 24-Mar-1998.)
ran (AB) = (ran A ∪ ran B)

Theoremrnin 5054 The range of an intersection belongs the intersection of ranges. Theorem 9 of [Suppes] p. 60. (Contributed by set.mm contributors, 15-Sep-2004.)
ran (AB) (ran A ∩ ran B)

Theoremrnuni 5055* The range of a union. Part of Exercise 8 of [Enderton] p. 41. (Contributed by set.mm contributors, 17-Mar-2004.)
ran A = x A ran x

Theoremimaundi 5056 Distributive law for image over union. Theorem 35 of [Suppes] p. 65. (Contributed by set.mm contributors, 30-Sep-2002.)
(A “ (BC)) = ((AB) ∪ (AC))

Theoremimaundir 5057 The image of a union. (Contributed by Jeff Hoffman, 17-Feb-2008.)
((AB) “ C) = ((AC) ∪ (BC))

Theoremdminss 5058 An upper bound for intersection with a domain. Theorem 40 of [Suppes] p. 66, who calls it "somewhat surprising." (Contributed by set.mm contributors, 11-Aug-2004.)
(dom RA) (R “ (RA))

Theoremimainss 5059 An upper bound for intersection with an image. Theorem 41 of [Suppes] p. 66. (Contributed by set.mm contributors, 11-Aug-2004.)
((RA) ∩ B) (R “ (A ∩ (RB)))

Theoremcnvxp 5060 The converse of a cross product. Exercise 11 of [Suppes] p. 67. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 14-Aug-1999.) (Revised by set.mm contributors, 27-Aug-2011.)
(A × B) = (B × A)

Theoremxp0 5061 The cross product with the empty set is empty. Part of Theorem 3.13(ii) of [Monk1] p. 37. (Contributed by set.mm contributors, 12-Apr-2004.)
(A × ) =

Theoremxpnz 5062 The cross product of nonempty classes is nonempty. (Variation of a theorem contributed by Raph Levien, 30-Jun-2006.) (Contributed by set.mm contributors, 30-Jun-2006.) (Revised by set.mm contributors, 19-Apr-2007.)
((A B) ↔ (A × B) ≠ )

Theoremxpeq0 5063 At least one member of an empty cross product is empty. (Contributed by set.mm contributors, 27-Aug-2006.)
((A × B) = ↔ (A = B = ))

Theoremxpdisj1 5064 Cross products with disjoint sets are disjoint. (Contributed by set.mm contributors, 13-Sep-2004.)
((AB) = → ((A × C) ∩ (B × D)) = )

Theoremxpdisj2 5065 Cross products with disjoint sets are disjoint. (Contributed by set.mm contributors, 13-Sep-2004.)
((AB) = → ((C × A) ∩ (D × B)) = )

Theoremxpsndisj 5066 Cross products with two different singletons are disjoint. (Contributed by set.mm contributors, 28-Jul-2004.) (Revised by set.mm contributors, 3-Jun-2007.)
(BD → ((A × {B}) ∩ (C × {D})) = )

Theoremresdisj 5067 A double restriction to disjoint classes is the empty set. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 7-Oct-2004.) (Revised by set.mm contributors, 27-Aug-2011.)
((AB) = → ((C A) B) = )

Theoremrnxp 5068 The range of a cross product. Part of Theorem 3.13(x) of [Monk1] p. 37. (Contributed by set.mm contributors, 12-Apr-2004.) (Revised by set.mm contributors, 9-Apr-2007.)
(A → ran (A × B) = B)

Theoremdmxpss 5069 The domain of a cross product is a subclass of the first factor. (Contributed by set.mm contributors, 19-Mar-2007.)
dom (A × B) A

Theoremrnxpss 5070 The range of a cross product is a subclass of the second factor. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 16-Jan-2006.) (Revised by set.mm contributors, 27-Aug-2011.)
ran (A × B) B

Theoremrnxpid 5071 The range of a square cross product. (Contributed by FL, 17-May-2010.)
ran (A × A) = A

Theoremssxpb 5072 A cross-product subclass relationship is equivalent to the relationship for it components. (Contributed by set.mm contributors, 17-Dec-2008.)
((A × B) ≠ → ((A × B) (C × D) ↔ (A C B D)))

Theoremxp11 5073 The cross product of non-empty classes is one-to-one. (Contributed by set.mm contributors, 31-May-2008.)
((A B) → ((A × B) = (C × D) ↔ (A = C B = D)))

Theoremxpcan 5074 Cancellation law for cross-product. (Contributed by set.mm contributors, 30-Aug-2011.)
(C → ((C × A) = (C × B) ↔ A = B))

Theoremxpcan2 5075 Cancellation law for cross-product. (Contributed by set.mm contributors, 30-Aug-2011.)
(C → ((A × C) = (B × C) ↔ A = B))

Theoremssrnres 5076 Subset of the range of a restriction. (Contributed by set.mm contributors, 16-Jan-2006.)
(B ran (C A) ↔ ran (C ∩ (A × B)) = B)

Theoremrninxp 5077* Range of the intersection with a cross product. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 17-Jan-2006.) (Revised by set.mm contributors, 27-Aug-2011.)
(ran (C ∩ (A × B)) = By B x A xCy)

Theoremdminxp 5078* Domain of the intersection with a cross product. (Contributed by set.mm contributors, 17-Jan-2006.)
(dom (C ∩ (A × B)) = Ax A y B xCy)

Theoremdfrel2 5079 Alternate definition of relation. Exercise 2 of [TakeutiZaring] p. 25. (Contributed by set.mm contributors, 29-Dec-1996.) (Revised by set.mm contributors, 15-Aug-2004.)
(Rel RR = R)

Theoremcnveqb 5080 Equality theorem for converse. (Contributed by FL, 19-Sep-2011.)
((Rel A Rel B) → (A = BA = B))

Theoremcnvcnv 5081 The double converse of a class strips out all elements that are not ordered pairs. (Contributed by set.mm contributors, 8-Dec-2003.)
A = (A ∩ (V × V))

Theoremcnvcnv2 5082 The double converse of a class equals its restriction to the universe. (Contributed by set.mm contributors, 8-Oct-2007.)
A = (A V)

Theoremcnvcnvss 5083 The double converse of a class is a subclass. Exercise 2 of [TakeutiZaring] p. 25. (Contributed by set.mm contributors, 23-Jul-2004.)
A A

Theoremdmsnn0 5084 The domain of a singleton is nonzero iff the singleton argument is an ordered pair. (Contributed by NM, 14-Dec-2008.) (Proof shortened by Andrew Salmon, 27-Aug-2011.)
(A (V × V) ↔ dom {A} ≠ )

Theoremrnsnn0 5085 The range of a singleton is nonzero iff the singleton argument is an ordered pair. (Contributed by set.mm contributors, 14-Dec-2008.)
(A (V × V) ↔ ran {A} ≠ )

Theoremdmsnopg 5086 The domain of a singleton of an ordered pair is the singleton of the first member. (Contributed by Mario Carneiro, 26-Apr-2015.)
(B V → dom {A, B} = {A})

Theoremdmsnopss 5087 The domain of a singleton of an ordered pair is a subset of the singleton of the first member (with no sethood assumptions on B). (Contributed by Mario Carneiro, 30-Apr-2015.)
dom {A, B} {A}

Theoremdmpropg 5088 The domain of an unordered pair of ordered pairs. (Contributed by Mario Carneiro, 26-Apr-2015.)
((B V D W) → dom {A, B, C, D} = {A, C})

Theoremdmsnop 5089 The domain of a singleton of an ordered pair is the singleton of the first member. (Contributed by NM, 30-Jan-2004.) (Proof shortened by Andrew Salmon, 27-Aug-2011.) (Revised by Mario Carneiro, 26-Apr-2015.)
B V       dom {A, B} = {A}

Theoremdmprop 5090 The domain of an unordered pair of ordered pairs. (Contributed by NM, 13-Sep-2011.)
B V    &   D V       dom {A, B, C, D} = {A, C}

Theoremdmtpop 5091 The domain of an unordered triple of ordered pairs. (Contributed by NM, 14-Sep-2011.)
B V    &   D V    &   F V       dom {A, B, C, D, E, F} = {A, C, E}

Theoremop1sta 5092 Extract the first member of an ordered pair. (Contributed by Raph Levien, 4-Dec-2003.)
A V    &   B V       dom {A, B} = A

Theoremcnvsn 5093 Converse of a singleton of an ordered pair. (Contributed by NM, 11-May-1998.)
A V    &   B V       {A, B} = {B, A}

Theoremopswap 5094 Swap the members of an ordered pair. (Contributed by set.mm contributors, 14-Dec-2008.)
A V    &   B V       {A, B} = B, A

Theoremrnsnop 5095 The range of a singleton of an ordered pair is the singleton of the second member. (Contributed by set.mm contributors, 24-Jul-2004.)
A V       ran {A, B} = {B}

Theoremop2nda 5096 Extract the second member of an ordered pair. (Contributed by set.mm contributors, 9-Jan-2015.)
A V    &   B V       ran {A, B} = B

Theoremdfrel3 5097 Alternate definition of relation. (Contributed by set.mm contributors, 14-May-2008.)
(Rel R ↔ (R V) = R)

Theoremdmresv 5098 The domain of a universal restriction. (Contributed by set.mm contributors, 14-May-2008.)
dom (A V) = dom A

Theoremrnresv 5099 The range of a universal restriction. (Contributed by set.mm contributors, 14-May-2008.)
ran (A V) = ran A

Theoremrescnvcnv 5100 The restriction of the double converse of a class. (The proof was shortened by Andrew Salmon, 27-Aug-2011.) (Contributed by set.mm contributors, 8-Apr-2007.) (Revised by set.mm contributors, 27-Aug-2011.)
(A B) = (A B)

Page List
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-6308
 Copyright terms: Public domain < Previous  Next >