P. 418 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 41701-41800   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	bgoldbachlt 41701*	The binary Goldbach conjecture is valid for small even numbers (i.e. for all even numbers less than or equal to a fixed big m). This is verified for m = 4 x 10^18 by Oliveira e Silva, see ax-bgbltosilva 41698. (Contributed by AV, 3-Aug-2020.) (Revised by AV, 9-Sep-2021.)
|- E. m e. NN ( ( 4 x. (; 1 0 ^; 1 8 ) ) <_ m /\ A. n e. Even ( ( 4 < n /\ n < m ) -> n e. GoldbachEven ) )
Axiom	ax-hgprmladder 41702	There is a partition ("ladder") of primes from 7 to 8.8 x 10^30 with parts ("rungs") having lengths of at least 4 and at most N - 4, see section 1.2.2 in [Helfgott] p. 4. Temporarily provided as "axiom". (Contributed by AV, 3-Aug-2020.) (Revised by AV, 9-Sep-2021.)
|- E. d e. ( ZZ>= ` 3 ) E. f e. (RePart ` d ) ( ( ( f ` 0 ) = 7 /\ ( f ` 1 ) = ; 1 3 /\ ( f ` d ) = (; 8 9 x. (; 1 0 ^; 2 9 ) ) ) /\ A. i e. ( 0..^ d ) ( ( f ` i ) e. ( Prime \ { 2 } ) /\ ( ( f ` ( i + 1 ) ) - ( f ` i ) ) < ( ( 4 x. (; 1 0 ^; 1 8 ) ) - 4 ) /\ 4 < ( ( f ` ( i + 1 ) ) - ( f ` i ) ) ) )
Theorem	tgblthelfgott 41703	The ternary Goldbach conjecture is valid for all odd numbers less than 8.8 x 10^30 (actually 8.875694 x 10^30, see section 1.2.2 in [Helfgott] p. 4, using bgoldbachlt 41701, ax-hgprmladder 41702 and bgoldbtbnd 41697. (Contributed by AV, 4-Aug-2020.) (Revised by AV, 9-Sep-2021.)
|- ( ( N e. Odd /\ 7 < N /\ N < (; 8 8 x. (; 1 0 ^; 2 9 ) ) ) -> N e. GoldbachOdd )
Theorem	tgoldbachlt 41704*	The ternary Goldbach conjecture is valid for small odd numbers (i.e. for all odd numbers less than a fixed big m greater than 8 x 10^30). This is verified for m = 8.875694 x 10^30 by Helfgott, see tgblthelfgott 41703. (Contributed by AV, 4-Aug-2020.) (Revised by AV, 9-Sep-2021.)
|- E. m e. NN ( ( 8 x. (; 1 0 ^; 3 0 ) ) < m /\ A. n e. Odd ( ( 7 < n /\ n < m ) -> n e. GoldbachOdd ) )
Theorem	tgoldbach 41705	The ternary Goldbach conjecture is valid. Main theorem in [Helfgott] p. 2. This follows from tgoldbachlt 41704 and ax-tgoldbachgt 41699. (Contributed by AV, 2-Aug-2020.) (Revised by AV, 9-Sep-2021.)
|- A. n e. Odd ( 7 < n -> n e. GoldbachOdd )
Axiom	ax-bgbltosilvaOLD 41706	Obsolete version of ax-bgbltosilva 41698 as of 9-Sep-2021. (Contributed by AV, 3-Aug-2020.) (New usage is discouraged.)
|- ( ( N e. Even /\ 4 < N /\ N <_ ( 4 x. ( 10 ^; 1 8 ) ) ) -> N e. GoldbachEven )
Theorem	bgoldbachltOLD 41707*	Obsolete version of bgoldbachlt 41701 as of 9-Sep-2021. (Contributed by AV, 3-Aug-2020.) (Proof modification is discouraged.) (New usage is discouraged.)
|- E. m e. NN ( ( 4 x. ( 10 ^; 1 8 ) ) <_ m /\ A. n e. Even ( ( 4 < n /\ n < m ) -> n e. GoldbachEven ) )
Axiom	ax-hgprmladderOLD 41708	Obsolete version of ax-hgprmladder 41702 as of 9-Sep-2021. (Contributed by AV, 3-Aug-2020.) (New usage is discouraged.)
|- E. d e. ( ZZ>= ` 3 ) E. f e. (RePart ` d ) ( ( ( f ` 0 ) = 7 /\ ( f ` 1 ) = ; 1 3 /\ ( f ` d ) = (; 8 9 x. ( 10 ^; 2 9 ) ) ) /\ A. i e. ( 0..^ d ) ( ( f ` i ) e. ( Prime \ { 2 } ) /\ ( ( f ` ( i + 1 ) ) - ( f ` i ) ) < ( ( 4 x. ( 10 ^; 1 8 ) ) - 4 ) /\ 4 < ( ( f ` ( i + 1 ) ) - ( f ` i ) ) ) )
Theorem	tgblthelfgottOLD 41709	Obsolete version of tgblthelfgott 41703 as of 9-Sep-2021. (Contributed by AV, 4-Aug-2020.) (Proof modification is discouraged.) (New usage is discouraged.)
|- ( ( N e. Odd /\ 7 < N /\ N < (; 8 8 x. ( 10 ^; 2 9 ) ) ) -> N e. GoldbachOdd )
Theorem	tgoldbachltOLD 41710*	Obsolete version of tgoldbachlt 41704 as of 9-Sep-2021. (Contributed by AV, 4-Aug-2020.) (Proof modification is discouraged.) (New usage is discouraged.)
|- E. m e. NN ( ( 8 x. ( 10 ^; 3 0 ) ) < m /\ A. n e. Odd ( ( 7 < n /\ n < m ) -> n e. GoldbachOdd ) )
Axiom	ax-tgoldbachgtOLD 41711*	Obsolete version of ax-tgoldbachgt 41699 as of 9-Sep-2021. (Contributed by AV, 2-Aug-2020.) (New usage is discouraged.)
|- E. m e. NN ( m <_ ( 10 ^; 2 7 ) /\ A. n e. Odd ( m < n -> n e. GoldbachOdd ) )
Theorem	tgoldbachOLD 41712	Obsolete version of tgoldbach 41705 as of 9-Sep-2021. (Contributed by AV, 2-Aug-2020.) (Proof modification is discouraged.) (New usage is discouraged.)
|- A. n e. Odd ( 7 < n -> n e. GoldbachOdd )
20.35.9  Graph theory (extension)
20.35.9.1  Loop-free graphs - extension
Theorem	1hegrlfgr 41713*	A graph G with one hyperedge joining at least two vertices is a loop-free graph. (Contributed by AV, 23-Feb-2021.)
|- ( ph -> A e. X )   &    |- ( ph -> B e. V )   &    |- ( ph -> C e. V )   &    |- ( ph -> B =/= C )   &    |- ( ph -> E e. ~P V )   &    |- ( ph -> (iEdg ` G ) = { <. A , E >. } )   &    |- ( ph -> { B , C } C_ E )   =>    |- ( ph -> (iEdg ` G ) : { A } --> { x e. ~P V | 2 <_ ( # ` x ) } )
20.35.9.2  Walks - extension
Syntax	cupwlks 41714	Extend class notation with walks (of a pseudograph).
class UPWalks
Definition	df-upwlks 41715*	Define the set of all walks (in a pseudograph), called "simple walks" in the following. According to Wikipedia ("Path (graph theory)", https://en.wikipedia.org/wiki/Path_(graph_theory), 3-Oct-2017): "A walk of length k in a graph is an alternating sequence of vertices and edges, v0 , e0 , v1 , e1 , v2 , ... , v(k-1) , e(k-1) , v(k) which begins and ends with vertices. If the graph is undirected, then the endpoints of e(i) are v(i) and v(i+1)." According to Bollobas: " A walk W in a graph is an alternating sequence of vertices and edges x0 , e1 , x1 , e2 , ... , e(l) , x(l) where e(i) = x(i-1)x(i), 0<i<=l.", see Definition of [Bollobas] p. 4. Therefore, a walk can be represented by two mappings f from { 1 , ... , n } and p from { 0 , ... , n }, where f enumerates the (indices of the) edges, and p enumerates the vertices. So the walk is represented by the following sequence: p(0) e(f(1)) p(1) e(f(2)) ... p(n-1) e(f(n)) p(n). Although this definition is also applicable for arbitrary hypergraphs, it allows only walks consisting of not proper hyperedges (i.e. edges connecting at most two vertices). Therefore, it should be used for pseudograhs only. (Contributed by Alexander van der Vekens and Mario Carneiro, 4-Oct-2017.) (Revised by AV, 28-Dec-2020.)
|- UPWalks = ( g e. _V |-> { <. f , p >. | ( f e. Word dom (iEdg ` g ) /\ p : ( 0 ... ( # ` f ) ) --> (Vtx ` g ) /\ A. k e. ( 0..^ ( # ` f ) ) ( (iEdg ` g ) ` ( f ` k ) ) = { ( p ` k ) , ( p ` ( k + 1 ) ) } ) } )
Theorem	upwlksfval 41716*	The set of simple walks (in an undirected graph). (Contributed by Alexander van der Vekens, 19-Oct-2017.) (Revised by AV, 28-Dec-2020.)
|- V = (Vtx ` G )   &    |- I = (iEdg ` G )   =>    |- ( G e. W -> (UPWalks ` G ) = { <. f , p >. | ( f e. Word dom I /\ p : ( 0 ... ( # ` f ) ) --> V /\ A. k e. ( 0..^ ( # ` f ) ) ( I ` ( f ` k ) ) = { ( p ` k ) , ( p ` ( k + 1 ) ) } ) } )
Theorem	isupwlk 41717*	Properties of a pair of functions to be a simple walk. (Contributed by Alexander van der Vekens, 20-Oct-2017.) (Revised by AV, 28-Dec-2020.)
|- V = (Vtx ` G )   &    |- I = (iEdg ` G )   =>    |- ( ( G e. W /\ F e. U /\ P e. Z ) -> ( F (UPWalks ` G ) P <-> ( F e. Word dom I /\ P : ( 0 ... ( # ` F ) ) --> V /\ A. k e. ( 0..^ ( # ` F ) ) ( I ` ( F ` k ) ) = { ( P ` k ) , ( P ` ( k + 1 ) ) } ) ) )
Theorem	isupwlkg 41718*	Generalisation of isupwlk 41717: Conditions for two classes to represent a simple walk. (Contributed by AV, 5-Nov-2021.)
|- V = (Vtx ` G )   &    |- I = (iEdg ` G )   =>    |- ( G e. W -> ( F (UPWalks ` G ) P <-> ( F e. Word dom I /\ P : ( 0 ... ( # ` F ) ) --> V /\ A. k e. ( 0..^ ( # ` F ) ) ( I ` ( F ` k ) ) = { ( P ` k ) , ( P ` ( k + 1 ) ) } ) ) )
Theorem	upwlkbprop 41719	Basic properties of a simple walk. (Contributed by Alexander van der Vekens, 31-Oct-2017.) (Revised by AV, 29-Dec-2020.)
|- V = (Vtx ` G )   &    |- I = (iEdg ` G )   =>    |- ( F (UPWalks ` G ) P -> ( G e. _V /\ F e. _V /\ P e. _V ) )
Theorem	upwlkwlk 41720	A simple walk is a walk. (Contributed by AV, 30-Dec-2020.) (Proof shortened by AV, 27-Feb-2021.)
|- ( F (UPWalks ` G ) P -> F (Walks ` G ) P )
Theorem	upgrwlkupwlk 41721	In a pseudograph, a walk is a simple walk. (Contributed by AV, 30-Dec-2020.) (Proof shortened by AV, 2-Jan-2021.)
|- ( ( G e. UPGraph /\ F (Walks ` G ) P ) -> F (UPWalks ` G ) P )
Theorem	upgrwlkupwlkb 41722	In a pseudograph, the definitions for a walk and a simple walk are equivalent. (Contributed by AV, 30-Dec-2020.)
|- ( G e. UPGraph -> ( F (Walks ` G ) P <-> F (UPWalks ` G ) P ) )
Theorem	upgrisupwlkALT 41723*	Alternate proof of upgriswlk 26537 using the definition of UPGraph and related theorems. (Contributed by AV, 2-Jan-2021.) (Proof modification is discouraged.) (New usage is discouraged.)
|- V = (Vtx ` G )   &    |- I = (iEdg ` G )   =>    |- ( ( G e. UPGraph /\ F e. U /\ P e. Z ) -> ( F (Walks ` G ) P <-> ( F e. Word dom I /\ P : ( 0 ... ( # ` F ) ) --> V /\ A. k e. ( 0..^ ( # ` F ) ) ( I ` ( F ` k ) ) = { ( P ` k ) , ( P ` ( k + 1 ) ) } ) ) )
20.35.10  Set of unordered pairs
Theorem	sprid 41724	Two identical representations of the class of all unordered pairs. (Contributed by AV, 21-Nov-2021.)
|- { p | E. a e. _V E. b e. _V p = { a , b } } = { p | E. a E. b p = { a , b } }
Theorem	elsprel 41725*	An unordered pair is an element of all unordered pairs. At least one of the two elements of the unordered pair must be a set. Otherwise, the unordered pair would be the empty set, see prprc 4302, which is not an element of all unordered pairs, see spr0nelg 41726. (Contributed by AV, 21-Nov-2021.)
|- ( ( A e. V \/ B e. W ) -> { A , B } e. { p | E. a E. b p = { a , b } } )
Theorem	spr0nelg 41726*	The empty set is not an element of all unordered pairs. (Contributed by AV, 21-Nov-2021.)
|- (/) e/ { p | E. a E. b p = { a , b } }
Syntax	cspr 41727	Extend class notation with set of pairs.
class Pairs
Definition	df-spr 41728*	Define the function which maps a set v to the set of pairs consisting of elements of the set v. (Contributed by AV, 21-Nov-2021.)
|- Pairs = ( v e. _V |-> { p | E. a e. v E. b e. v p = { a , b } } )
Theorem	sprval 41729*	The set of all unordered pairs over a given set V. (Contributed by AV, 21-Nov-2021.)
|- ( V e. W -> (Pairs ` V ) = { p | E. a e. V E. b e. V p = { a , b } } )
Theorem	sprvalpw 41730*	The set of all unordered pairs over a given set V, expressed by a restricted class abstraction. (Contributed by AV, 21-Nov-2021.)
|- ( V e. W -> (Pairs ` V ) = { p e. ~P V | E. a e. V E. b e. V p = { a , b } } )
Theorem	sprssspr 41731*	The set of all unordered pairs over a given set V is a subset of the set of all unordered pairs. (Contributed by AV, 21-Nov-2021.)
|- (Pairs ` V ) C_ { p | E. a E. b p = { a , b } }
Theorem	spr0el 41732	The empty set is not an unordered pair over any set V. (Contributed by AV, 21-Nov-2021.)
|- (/) e/ (Pairs ` V )
Theorem	sprvalpwn0 41733*	The set of all unordered pairs over a given set V, expressed by a restricted class abstraction. (Contributed by AV, 21-Nov-2021.)
|- ( V e. W -> (Pairs ` V ) = { p e. ( ~P V \ { (/) } ) | E. a e. V E. b e. V p = { a , b } } )
Theorem	sprel 41734*	An element of the set of all unordered pairs over a given set V is a pair of elements of the set V. (Contributed by AV, 22-Nov-2021.)
|- ( X e. (Pairs ` V ) -> E. a e. V E. b e. V X = { a , b } )
Theorem	prssspr 41735*	An element of a subset of the set of all unordered pairs over a given set V, is a pair of elements of the set V. (Contributed by AV, 22-Nov-2021.)
|- ( ( P C_ (Pairs ` V ) /\ X e. P ) -> E. a e. V E. b e. V X = { a , b } )
Theorem	prelspr 41736	An unordered pair of elements of a fixed set V belongs to the set of all unordered pairs over the set V. (Contributed by AV, 21-Nov-2021.)
|- ( ( V e. W /\ ( X e. V /\ Y e. V ) ) -> { X , Y } e. (Pairs ` V ) )
Theorem	prsprel 41737	The elements of a pair from the set of all unordered pairs over a given set V are elements of the set V. (Contributed by AV, 22-Nov-2021.)
|- ( ( { X , Y } e. (Pairs ` V ) /\ ( X e. U /\ Y e. W ) ) -> ( X e. V /\ Y e. V ) )
Theorem	prsssprel 41738	The elements of a pair from a subset of the set of all unordered pairs over a given set V are elements of the set V. (Contributed by AV, 21-Nov-2021.)
|- ( ( P C_ (Pairs ` V ) /\ { X , Y } e. P /\ ( X e. U /\ Y e. W ) ) -> ( X e. V /\ Y e. V ) )
Theorem	sprvalpwle2 41739*	The set of all unordered pairs over a given set V, expressed by a restricted class abstraction. (Contributed by AV, 24-Nov-2021.)
|- ( V e. W -> (Pairs ` V ) = { p e. ( ~P V \ { (/) } ) | ( # ` p ) <_ 2 } )
Theorem	sprsymrelfvlem 41740*	Lemma for sprsymrelf 41745 and sprsymrelfv 41744. (Contributed by AV, 19-Nov-2021.)
|- ( P C_ (Pairs ` V ) -> { <. x , y >. | E. c e. P c = { x , y } } e. ~P ( V X. V ) )
Theorem	sprsymrelf1lem 41741*	Lemma for sprsymrelf1 41746. (Contributed by AV, 22-Nov-2021.)
|- ( ( a C_ (Pairs ` V ) /\ b C_ (Pairs ` V ) ) -> ( { <. x , y >. | E. c e. a c = { x , y } } = { <. x , y >. | E. c e. b c = { x , y } } -> a C_ b ) )
Theorem	sprsymrelfolem1 41742*	Lemma 1 for sprsymrelfo 41747. (Contributed by AV, 22-Nov-2021.)
|- Q = { q e. (Pairs ` V ) | A. a e. V A. b e. V ( q = { a , b } -> a R b ) }   =>    |- Q e. ~P (Pairs ` V )
Theorem	sprsymrelfolem2 41743*	Lemma 2 for sprsymrelfo 41747. (Contributed by AV, 23-Nov-2021.)
|- Q = { q e. (Pairs ` V ) | A. a e. V A. b e. V ( q = { a , b } -> a R b ) }   =>    |- ( ( V e. W /\ R C_ ( V X. V ) /\ A. x e. V A. y e. V ( x R y <-> y R x ) ) -> ( x R y <-> E. c e. Q c = { x , y } ) )
Theorem	sprsymrelfv 41744*	The value of the function F which maps a subset of the set of pairs over a fixed set V to the relation relating two elements of the set V iff they are in a pair of the subset. (Contributed by AV, 19-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   &    |- F = ( p e. P |-> { <. x , y >. | E. c e. p c = { x , y } } )   =>    |- ( X e. P -> ( F ` X ) = { <. x , y >. | E. c e. X c = { x , y } } )
Theorem	sprsymrelf 41745*	The mapping F is a function from the subsets of the set of pairs over a fixed set V into the symmetric relations R on the fixed set V. (Contributed by AV, 19-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   &    |- F = ( p e. P |-> { <. x , y >. | E. c e. p c = { x , y } } )   =>    |- F : P --> R
Theorem	sprsymrelf1 41746*	The mapping F is a one-to-one function from the subsets of the set of pairs over a fixed set V into the symmetric relations R on the fixed set V. (Contributed by AV, 19-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   &    |- F = ( p e. P |-> { <. x , y >. | E. c e. p c = { x , y } } )   =>    |- F : P -1-1-> R
Theorem	sprsymrelfo 41747*	The mapping F is a function from the subsets of the set of pairs over a fixed set V onto the symmetric relations R on the fixed set V. (Contributed by AV, 23-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   &    |- F = ( p e. P |-> { <. x , y >. | E. c e. p c = { x , y } } )   =>    |- ( V e. W -> F : P -onto-> R )
Theorem	sprsymrelf1o 41748*	The mapping F is a bijection between the subsets of the set of pairs over a fixed set V into the symmetric relations R on the fixed set V. (Contributed by AV, 23-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   &    |- F = ( p e. P |-> { <. x , y >. | E. c e. p c = { x , y } } )   =>    |- ( V e. W -> F : P -1-1-onto-> R )
Theorem	sprbisymrel 41749*	There is a bijection between the subsets of the set of pairs over a fixed set V and the symmetric relations R on the fixed set V. (Contributed by AV, 23-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   =>    |- ( V e. W -> E. f f : P -1-1-onto-> R )
Theorem	sprsymrelen 41750*	The class P of subsets of the set of pairs over a fixed set V and the class R of symmetric relations on the fixed set V are equinumerous. (Contributed by AV, 27-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   =>    |- ( V e. W -> P ~~ R )
Theorem	upgredgssspr 41751	The set of edges of a pseudograph is a subset of the set of unordered pairs of vertices. (Contributed by AV, 24-Nov-2021.)
|- ( G e. UPGraph -> (Edg ` G ) C_ (Pairs ` (Vtx ` G ) ) )
Theorem	uspgropssxp 41752*	The set G of "simple pseudographs" for a fixed set V of vertices is a subset of an Cartesian product. For more details about the class G of all "simple pseudographs" see comments on uspgrbisymrel 41762. (Contributed by AV, 24-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   =>    |- ( V e. W -> G C_ ( W X. P ) )
Theorem	uspgrsprfv 41753*	The value of the function F which maps a "simple pseudograph" for a fixed set V of vertices to the set of edges (i.e. range of the edge function) of the graph. Solely for G as defined here, the function F is a bijection between the "simple pseudographs" and the subsets of the set of pairs P over the the fixed set V of vertices, see uspgrbispr 41759. (Contributed by AV, 24-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- F = ( g e. G |-> ( 2nd ` g ) )   =>    |- ( X e. G -> ( F ` X ) = ( 2nd ` X ) )
Theorem	uspgrsprf 41754*	The mapping F is a function from the "simple pseudographs" with a fixed set of vertices V into the subsets of the set of pairs over the set V. (Contributed by AV, 24-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- F = ( g e. G |-> ( 2nd ` g ) )   =>    |- F : G --> P
Theorem	uspgrsprf1 41755*	The mapping F is a one-to-one function from the "simple pseudographs" with a fixed set of vertices V into the subsets of the set of pairs over the set V. (Contributed by AV, 25-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- F = ( g e. G |-> ( 2nd ` g ) )   =>    |- F : G -1-1-> P
Theorem	uspgrsprfo 41756*	The mapping F is a function from the "simple pseudographs" with a fixed set of vertices V onto the subsets of the set of pairs over the set V. (Contributed by AV, 25-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- F = ( g e. G |-> ( 2nd ` g ) )   =>    |- ( V e. W -> F : G -onto-> P )
Theorem	uspgrsprf1o 41757*	The mapping F is a bijection between the "simple pseudographs" with a fixed set of vertices V and the subsets of the set of pairs over the set V. See also the comments on uspgrbisymrel 41762. (Contributed by AV, 25-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- F = ( g e. G |-> ( 2nd ` g ) )   =>    |- ( V e. W -> F : G -1-1-onto-> P )
Theorem	uspgrex 41758*	The class G of all "simple pseudographs" with a fixed set of vertices V is a set. (Contributed by AV, 26-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   =>    |- ( V e. W -> G e. _V )
Theorem	uspgrbispr 41759*	There is a bijection between the "simple pseudographs" with a fixed set of vertices V and the subsets of the set of pairs over the set V. (Contributed by AV, 26-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   =>    |- ( V e. W -> E. f f : G -1-1-onto-> P )
Theorem	uspgrspren 41760*	The set G of the "simple pseudographs" with a fixed set of vertices V and the class P of subsets of the set of pairs over the fixed set V are equinumerous. (Contributed by AV, 27-Nov-2021.)
|- P = ~P (Pairs ` V )   &    |- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   =>    |- ( V e. W -> G ~~ P )
Theorem	uspgrymrelen 41761*	The set G of the "simple pseudographs" with a fixed set of vertices V and the class R of the symmetric relations on the fixed set V are equinumerous. For more details about the class G of all "simple pseudographs" see comments on uspgrbisymrel 41762. (Contributed by AV, 27-Nov-2021.)
|- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   =>    |- ( V e. W -> G ~~ R )
Theorem	uspgrbisymrel 41762*	There is a bijection between the "simple pseudographs" for a fixed set V of vertices and the class R of the symmetric relations on the fixed set V. The simple pseudographs, which are graphs without hyper- or multiedges, but which may contain loops, are expressed as ordered pairs of the vertices and the edges (as proper or improper unordered pairs of vertices, not as indexed edges!) in this theorem. That class G of such simple pseudographs is a set (if V is a set, see uspgrex 41758) of equivalence classes of graphs abstracting from the index sets of their edge functions. Solely for this abstraction, there is a bijection between the "simple pseudographs" as members of G and the symmetric relations R on the fixed set V of vertices. This theorem would not hold for G = { g e. USPGraph | (Vtx ` g ) = V } and even not for G = { <. v , e >. | ( v = V /\ <. v , e >. e. USPGraph ) }, because these are much bigger classes. (Proposed by Gerard Lang, 16-Nov-2021.) (Contributed by AV, 27-Nov-2021.)
|- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   =>    |- ( V e. W -> E. f f : G -1-1-onto-> R )
Theorem	uspgrbisymrelALT 41763*	Alternate proof of uspgrbisymrel 41762 not using the definition of equinumerosity. (Contributed by AV, 26-Nov-2021.) (New usage is discouraged.) (Proof modification is discouraged.)
|- G = { <. v , e >. | ( v = V /\ E. q e. USPGraph ( (Vtx ` q ) = v /\ (Edg ` q ) = e ) ) }   &    |- R = { r e. ~P ( V X. V ) | A. x e. V A. y e. V ( x r y <-> y r x ) }   =>    |- ( V e. W -> E. f f : G -1-1-onto-> R )
20.35.11  Monoids (extension)
20.35.11.1  Auxiliary theorems
Theorem	ovn0dmfun 41764	If a class operation value for two operands is not the empty set, then the operands are contained in the domain of the class, and the class restricted to the operands is a function, analogous to fvfundmfvn0 6226. (Contributed by AV, 27-Jan-2020.)
|- ( ( A F B ) =/= (/) -> ( <. A , B >. e. dom F /\ Fun ( F |` { <. A , B >. } ) ) )
Theorem	xpsnopab 41765*	A Cartesian product with a singleton expressed as ordered-pair class abstraction. (Contributed by AV, 27-Jan-2020.)
|- ( { X } X. C ) = { <. a , b >. | ( a = X /\ b e. C ) }
Theorem	xpiun 41766*	A Cartesian product expressed as indexed union of ordered-pair class abstractions. (Contributed by AV, 27-Jan-2020.)
|- ( B X. C ) = U_ x e. B { <. a , b >. | ( a = x /\ b e. C ) }
Theorem	ovn0ssdmfun 41767*	If a class' operation value for two operands is not the empty set, the operands are contained in the domain of the class, and the class restricted to the operands is a function, analogous to fvfundmfvn0 6226. (Contributed by AV, 27-Jan-2020.)
|- ( A. a e. D A. b e. E ( a F b ) =/= (/) -> ( ( D X. E ) C_ dom F /\ Fun ( F |` ( D X. E ) ) ) )
Theorem	fnxpdmdm 41768	The domain of the domain of a function over a Cartesian square. (Contributed by AV, 13-Jan-2020.)
|- ( F Fn ( A X. A ) -> dom dom F = A )
Theorem	cnfldsrngbas 41769	The base set of a subring of the field of complex numbers. (Contributed by AV, 31-Jan-2020.)
|- R = (ℂfld ↾s S )   =>    |- ( S C_ CC -> S = ( Base ` R ) )
Theorem	cnfldsrngadd 41770	The group addition operation of a subring of the field of complex numbers. (Contributed by AV, 31-Jan-2020.)
|- R = (ℂfld ↾s S )   =>    |- ( S e. V -> + = ( +g ` R ) )
Theorem	cnfldsrngmul 41771	The ring multiplication operation of a subring of the field of complex numbers. (Contributed by AV, 31-Jan-2020.)
|- R = (ℂfld ↾s S )   =>    |- ( S e. V -> x. = ( .r ` R ) )
20.35.11.2  Magmas and Semigroups (extension)
Theorem	plusfreseq 41772	If the empty set is not contained in the range of the group addition function of an extensible structure (not necessarily a magma), the restriction of the addition operation to (the Cartesian square of) the base set is the functionalization of it. (Contributed by AV, 28-Jan-2020.)
|- B = ( Base ` M )   &    |- .+ = ( +g ` M )   &    |- .+^ = ( +f ` M )   =>    |- ( (/) e/ ran .+^ -> ( .+ |` ( B X. B ) ) = .+^ )
Theorem	mgmplusfreseq 41773	If the empty set is not contained in the base set of a magma, the restriction of the addition operation to (the Cartesian square of) the base set is the functionalization of it. (Contributed by AV, 28-Jan-2020.)
|- B = ( Base ` M )   &    |- .+ = ( +g ` M )   &    |- .+^ = ( +f ` M )   =>    |- ( ( M e. Mgm /\ (/) e/ B ) -> ( .+ |` ( B X. B ) ) = .+^ )
Theorem	0mgm 41774	A set with an empty base set is always a magma". (Contributed by AV, 25-Feb-2020.)
|- ( Base ` M ) = (/)   =>    |- ( M e. V -> M e. Mgm )
Theorem	mgmpropd 41775*	If two structures have the same (nonempty) base set, and the values of their group (addition) operations are equal for all pairs of elements of the base set, one is a magma iff the other one is. (Contributed by AV, 25-Feb-2020.)
|- ( ph -> B = ( Base ` K ) )   &    |- ( ph -> B = ( Base ` L ) )   &    |- ( ph -> B =/= (/) )   &    |- ( ( ph /\ ( x e. B /\ y e. B ) ) -> ( x ( +g ` K ) y ) = ( x ( +g ` L ) y ) )   =>    |- ( ph -> ( K e. Mgm <-> L e. Mgm ) )
Theorem	ismgmd 41776*	Deduce a magma from its properties. (Contributed by AV, 25-Feb-2020.)
|- ( ph -> B = ( Base ` G ) )   &    |- ( ph -> G e. V )   &    |- ( ph -> .+ = ( +g ` G ) )   &    |- ( ( ph /\ x e. B /\ y e. B ) -> ( x .+ y ) e. B )   =>    |- ( ph -> G e. Mgm )
20.35.11.3  Magma homomorphisms and submagmas
Syntax	cmgmhm 41777	Hom-set generator class for magmas.
class MgmHom
Syntax	csubmgm 41778	Class function taking a magma to its lattice of submagmas.
class SubMgm
Definition	df-mgmhm 41779*	A magma homomorphism is a function on the base sets which preserves the binary operation. (Contributed by AV, 24-Feb-2020.)
|- MgmHom = ( s e. Mgm , t e. Mgm |-> { f e. ( ( Base ` t ) ^m ( Base ` s ) ) | A. x e. ( Base ` s ) A. y e. ( Base ` s ) ( f ` ( x ( +g ` s ) y ) ) = ( ( f ` x ) ( +g ` t ) ( f ` y ) ) } )
Definition	df-submgm 41780*	A submagma is a subset of a magma which is closed under the operation. Such subsets are themselves magmas. (Contributed by AV, 24-Feb-2020.)
|- SubMgm = ( s e. Mgm |-> { t e. ~P ( Base ` s ) | A. x e. t A. y e. t ( x ( +g ` s ) y ) e. t } )
Theorem	mgmhmrcl 41781	Reverse closure of a magma homomorphism. (Contributed by AV, 24-Feb-2020.)
|- ( F e. ( S MgmHom T ) -> ( S e. Mgm /\ T e. Mgm ) )
Theorem	submgmrcl 41782	Reverse closure for submagmas. (Contributed by AV, 24-Feb-2020.)
|- ( S e. (SubMgm ` M ) -> M e. Mgm )
Theorem	ismgmhm 41783*	Property of a magma homomorphism. (Contributed by AV, 25-Feb-2020.)
|- B = ( Base ` S )   &    |- C = ( Base ` T )   &    |- .+ = ( +g ` S )   &    |- .+^ = ( +g ` T )   =>    |- ( F e. ( S MgmHom T ) <-> ( ( S e. Mgm /\ T e. Mgm ) /\ ( F : B --> C /\ A. x e. B A. y e. B ( F ` ( x .+ y ) ) = ( ( F ` x ) .+^ ( F ` y ) ) ) ) )
Theorem	mgmhmf 41784	A magma homomorphism is a function. (Contributed by AV, 25-Feb-2020.)
|- B = ( Base ` S )   &    |- C = ( Base ` T )   =>    |- ( F e. ( S MgmHom T ) -> F : B --> C )
Theorem	mgmhmpropd 41785*	Magma homomorphism depends only on the operation of structures. (Contributed by AV, 25-Feb-2020.)
|- ( ph -> B = ( Base ` J ) )   &    |- ( ph -> C = ( Base ` K ) )   &    |- ( ph -> B = ( Base ` L ) )   &    |- ( ph -> C = ( Base ` M ) )   &    |- ( ph -> B =/= (/) )   &    |- ( ph -> C =/= (/) )   &    |- ( ( ph /\ ( x e. B /\ y e. B ) ) -> ( x ( +g ` J ) y ) = ( x ( +g ` L ) y ) )   &    |- ( ( ph /\ ( x e. C /\ y e. C ) ) -> ( x ( +g ` K ) y ) = ( x ( +g ` M ) y ) )   =>    |- ( ph -> ( J MgmHom K ) = ( L MgmHom M ) )
Theorem	mgmhmlin 41786	A magma homomorphism preserves the binary operation. (Contributed by AV, 25-Feb-2020.)
|- B = ( Base ` S )   &    |- .+ = ( +g ` S )   &    |- .+^ = ( +g ` T )   =>    |- ( ( F e. ( S MgmHom T ) /\ X e. B /\ Y e. B ) -> ( F ` ( X .+ Y ) ) = ( ( F ` X ) .+^ ( F ` Y ) ) )
Theorem	mgmhmf1o 41787	A magma homomorphism is bijective iff its converse is also a magma homomorphism. (Contributed by AV, 25-Feb-2020.)
|- B = ( Base ` R )   &    |- C = ( Base ` S )   =>    |- ( F e. ( R MgmHom S ) -> ( F : B -1-1-onto-> C <-> `' F e. ( S MgmHom R ) ) )
Theorem	idmgmhm 41788	The identity homomorphism on a magma. (Contributed by AV, 27-Feb-2020.)
|- B = ( Base ` M )   =>    |- ( M e. Mgm -> ( _I |` B ) e. ( M MgmHom M ) )
Theorem	issubmgm 41789*	Expand definition of a submagma. (Contributed by AV, 25-Feb-2020.)
|- B = ( Base ` M )   &    |- .+ = ( +g ` M )   =>    |- ( M e. Mgm -> ( S e. (SubMgm ` M ) <-> ( S C_ B /\ A. x e. S A. y e. S ( x .+ y ) e. S ) ) )
Theorem	issubmgm2 41790	Submagmas are subsets that are also magmas. (Contributed by AV, 25-Feb-2020.)
|- B = ( Base ` M )   &    |- H = ( M ↾s S )   =>    |- ( M e. Mgm -> ( S e. (SubMgm ` M ) <-> ( S C_ B /\ H e. Mgm ) ) )
Theorem	rabsubmgmd 41791*	Deduction for proving that a restricted class abstraction is a submagma. (Contributed by AV, 26-Feb-2020.)
|- B = ( Base ` M )   &    |- .+ = ( +g ` M )   &    |- ( ph -> M e. Mgm )   &    |- ( ( ph /\ ( ( x e. B /\ y e. B ) /\ ( th /\ ta ) ) ) -> et )   &    |- ( z = x -> ( ps <-> th ) )   &    |- ( z = y -> ( ps <-> ta ) )   &    |- ( z = ( x .+ y ) -> ( ps <-> et ) )   =>    |- ( ph -> { z e. B | ps } e. (SubMgm ` M ) )
Theorem	submgmss 41792	Submagmas are subsets of the base set. (Contributed by AV, 26-Feb-2020.)
|- B = ( Base ` M )   =>    |- ( S e. (SubMgm ` M ) -> S C_ B )
Theorem	submgmid 41793	Every magma is trivially a submagma of itself. (Contributed by AV, 26-Feb-2020.)
|- B = ( Base ` M )   =>    |- ( M e. Mgm -> B e. (SubMgm ` M ) )
Theorem	submgmcl 41794	Submagmas are closed under the monoid operation. (Contributed by AV, 26-Feb-2020.)
|- .+ = ( +g ` M )   =>    |- ( ( S e. (SubMgm ` M ) /\ X e. S /\ Y e. S ) -> ( X .+ Y ) e. S )
Theorem	submgmmgm 41795	Submagmas are themselves magmas under the given operation. (Contributed by AV, 26-Feb-2020.)
|- H = ( M ↾s S )   =>    |- ( S e. (SubMgm ` M ) -> H e. Mgm )
Theorem	submgmbas 41796	The base set of a submagma. (Contributed by AV, 26-Feb-2020.)
|- H = ( M ↾s S )   =>    |- ( S e. (SubMgm ` M ) -> S = ( Base ` H ) )
Theorem	subsubmgm 41797	A submagma of a submagma is a submagma. (Contributed by AV, 26-Feb-2020.)
|- H = ( G ↾s S )   =>    |- ( S e. (SubMgm ` G ) -> ( A e. (SubMgm ` H ) <-> ( A e. (SubMgm ` G ) /\ A C_ S ) ) )
Theorem	resmgmhm 41798	Restriction of a magma homomorphism to a submagma is a homomorphism. (Contributed by AV, 26-Feb-2020.)
|- U = ( S ↾s X )   =>    |- ( ( F e. ( S MgmHom T ) /\ X e. (SubMgm ` S ) ) -> ( F |` X ) e. ( U MgmHom T ) )
Theorem	resmgmhm2 41799	One direction of resmgmhm2b 41800. (Contributed by AV, 26-Feb-2020.)
|- U = ( T ↾s X )   =>    |- ( ( F e. ( S MgmHom U ) /\ X e. (SubMgm ` T ) ) -> F e. ( S MgmHom T ) )
Theorem	resmgmhm2b 41800	Restriction of the codomain of a homomorphism. (Contributed by AV, 26-Feb-2020.)
|- U = ( T ↾s X )   =>    |- ( ( X e. (SubMgm ` T ) /\ ran F C_ X ) -> ( F e. ( S MgmHom T ) <-> F e. ( S MgmHom U ) ) )