Structure Theory and a Generalization of the Isomorphism Theorems by Alan Bertl A thesis submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Master of Science Auburn, Alabama August 3, 2013 Keywords: Structure, Universal Algebra, Topology, Graph Theory Copyright 2013 by Alan Bertl Approved by Michel Smith, Professor of Mathematics Randall Holmes, Professor of Mathematics Dean Ho man, Professor of Mathematics Abstract A general format in which the mathematical structure of topological spaces, algebraic structures, and graphs can be expressed is described. A generalization of the fundamental homomorphism theorem and the isomorphism theorems of algebra is proved. ii Acknowledgments Firstly, special thanks to my wife Yesenia for all her love and support, for bearing with me during the evenings we spent in our studio apartment while I worked out the proofs on my laptop. Special thanks to my mentor Dr. Gordon Johnson for instilling in me a love for mathe- matics, and patiently picking apart my arguments while I was learning to think carefully. Thanks to Dr. Michel Smith for allowing me to run with the idea I had, and his patience in examining my arguments. Thanks to Dr. Randall Holmes for all his feedback, through which I?ve been able to express my ideas much more clearly, and for his interest early on and willingness to hear my scheme. Finally thanks to my colleagues who showed an interest in my work, and were willing to wade through my de nitions back when I wasn?t sure I had anything: John Asplund, Daniel Brice, Glenn Hughes, Zachary Sarver, Alexander Byaly. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Structurizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4 Fundamental (Co)Homomorphism Theorems . . . . . . . . . . . . . . . . . . . . 39 5 First Isomorphism Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6 Second Isomorphism Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 7 Third Isomorphism Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 8 Correspondence Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 iv Chapter 1 De nitions De nition The statement that r is a relation means r is a set of ordered pairs. If S is a set then r(S) denotes the set to which an element y belongs if and only if there is an element x2S such that (x;y)2r. Theorem 1.1. Suppose each of r and s is a relation, r s, each of U and V is a set, and U V. Then r(U) s(V). Proof: y2r(U) =)9x2U such that (x;y)2r =)x2V and (x;y)2s =)y2s(V) So r(U) s(V). De nition Suppose each of r and s is a relation. The composition of r and s is the relation to which a pair (x;z) belongs if and only if there is an element y such that (x;y) 2s and (y;z)2r. Denote the composition of r and s by rs. Theorem 1.2. Suppose each of r, s, and t is a relation. Then (rs)t = r(st). 1 Proof: (a;d)2(rs)t ()9c such that (a;c)2rs and (c;d)2t ()9b and a c such that (a;b)2r;(b;c)2s, and (c;d)2t ()9b such that (a;b)2r and (b;d)2st ()(a;d)2r(st) So (rs)t = r(st). Theorem 1.3. Suppose each of f, g, r, and s is a relation, f g, and r s. Then rf sg. Proof: (x;z)2rf =)9y such that (x;y)2f and (y;z)2r =)(x;y)2g and (y;z)2s =)(x;z)2sg So rf sg. De nition Suppose r is a relation. The inverse of r is the relation to which a pair (x;y) belongs if and only if (y;x) is in r. Denote the inverse of r by r 1. Theorem 1.4. Suppose r is a relation. Then (r 1) 1 = r. 2 Proof: (x;y)2(r 1) 1 ()(y;x)2r 1 ()(x;y)2r So (r 1) 1 = r. Theorem 1.5. Suppose each of r and s is a relation. Then (rs) 1 = s 1r 1. Proof: (x;z)2(rs) 1 ()(z;x)2rs ()9y such that (y;x)2r and (z;y)2s ()9y such that (x;y)2r 1 and (y;z)2s 1 ()(x;z)2s 1r 1 So (rs) 1 = s 1r 1. De nition Suppose r is a relation. The statement that D is the domain of r means D is the set to which an element x belongs if and only if x is the rst element of a pair in r. Denote the domain of r by dom(r). De nition Suppose r is a relation. The statement that R is the image of r means R is the set to which an element x belongs if and only if x is the second element of a pair in r. Denote the image of r by im(r). Theorem 1.6. Suppose r is a relation. Then im(r) = r(dom(r)). 3 Proof: y2im(r) ()9(x;y)2r ()9x2dom(r) such that (x;y)2r ()y2r(dom(r)) So im(r) = r(dom(r)). Theorem 1.7. Suppose each of r and s is a relation. Then im(rs) = r(im(s)). Proof: z2im(rs) ()9(x;z)2rs ()9y such that (y;z)2r and 9(x;y)2s ()9y2im(s) such that (y;z)2r ()z2r(im(s)) So im(rs) = r(im(s)). De nition The statement that f is a function means f is a relation such that no two pairs in f share the same rst element. If (x;y)2f, then denote y by f(x). Theorem 1.8. Suppose each of f and g is a function. Then fg is a function. 4 Proof: (x;z1)2fg and (x;z2)2fg =)9y1 such that (x;y1)2g and (y1;z1)2f and 9y2 such that (x;y2)2g and (y2;z2)2f =)y1 = y2 and (y1;z1)2f and (y1;z2) = (y2;z2)2f (since g is a function) =)z1 = z2 (since f is a function) So no two pairs of fg contain the rst element. So fg is a function. De nition The statement that f is an injection means f is a function and f 1 is a function. Theorem 1.9. Suppose each of f and g is an injection. Then fg is a injection. Proof: f is an injection and g is an injection =)f is a function, g is a function, f 1 is a function, and g 1 is a function =)fg is a function and (fg) 1 = g 1f 1 is a function =)fg is an injection De nition The statement that f is a surjection with respect to Y means f is a function with image Y. Theorem 1.10. Suppose S is a set, and f is a surjection with respect to S, and g is a surjection with respect to dom(f). Then fg is a surjection with respect to S. 5 Proof: z2S ()z2im(f) ()9y2dom(f) = im(g) such that (y;z)2f ()9x2dom(g) and 9y2dom(f) such that (x;y)2g and (y;z)2f ()9x2dom(g) such that (x;z)2fg ()z2im(fg) So S = im(fg) and thus fg is a surjection with respect to S. De nition The statement that f is a bijection with respect to Y means f is an injection and a surjection with respect to Y. De nition The notation r : X !Y means r is a relation and X is the domain of r and the image of r is a subset of Y, and henceforth if the terms surjection or bijection are used to describe r they will be understood to be with respect to Y. De nition Suppose A is a set. Denote by 1A the relation f(a;a)ja2Ag. Theorem 1.11. Suppose A is a set. Then 1A = 1 1A . Proof: (a;a)21A ()(a;a)21 1A So 1A = 1 1A . De nition Suppose A is a set and r is a relation. Denote by rjA the relation to which a pair (x;y) belongs if and only if (x;y)2r and x2A. 6 Theorem 1.12. Suppose A is a set and r is a relation. Then r = rjA if and only if dom(r) A. Proof: Suppose r = rjA. a2dom(r) =)9b such that (a;b)2r =)9b such that (a;b)2rjA =)a2A So dom(r) A. Suppose dom(r) A. (a;b)2r ()a2dom(r) A and (a;b)2r ()(a;b)2rjA So r = rjA. Theorem 1.13. Suppose A is a set, and r is a relation. Then r1A = rjA. Proof: (x;z)2r1A ()9y such that (x;y)21A and (y;z)2r ()9y such that x2A, x = y, and (y;z)2r ()x2A and (x;z)2r ()(x;z)2rjA 7 So r1A = rjA. De nition Suppose A is a set and r is a relation. Denote by rjA the relation to which a pair (x;y) belongs if and only if (x;y)2r and y2A. Theorem 1.14. Suppose A is a set and r is a relation. Then r = rjA if and only if im(r) A. Proof: Suppose r = rjA. a2im(r) =)9b such that (b;a)2r =)9b such that (b;a)2rjA =)a2A So im(r) A. Suppose im(r) A. (b;a)2r ()a2im(r) A and (b;a)2r ()(b;a)2rjA So r = rjA. Theorem 1.15. Suppose A is a set, and r is a relation. Then 1Ar = rjA. 8 Proof: (x;z)21Ar ()9y such that (x;y)2r and (y;z)21A ()9y such that (x;y)2r, y2A, and y = z ()(x;z)2r and z2A ()(x;z)2rjA So 1Ar = rjA. Theorem 1.16. Suppose each of A and B is a set, and f : A!B is a function. Then 1A f 1f, and 1A = f 1f if and only if f is an injection. Proof: (a;a)21A =)a2A =)(a;f(a))2f and (f(a);a)2f 1 =)(a;a)2f 1f So 1A f 1f. Suppose 1A = f 1f. (b;a1)2f 1 and (b;a2)2f 1 =)(a1;b)2f and (b;a2)2f 1 =)(a1;a2)2f 1f = 1A =)a1 = a2 9 So f 1 is a function and thus f is an injection. Suppose f is an injection. (a1;a2)2f 1f =)9b such that (a1;b)2f and (b;a2)2f 1 =)(b;a1)2f 1 and (b;a2)2f 1 =)a1 = a2 (since f 1 is a function) =)(a1;a2)21A So f 1f 1A, and thus 1A = f 1f. Theorem 1.17. Suppose each of A and B is a set, and f : A!B is a function. Then ff 1 1B, and ff 1 = 1B if and only if f is a surjection. Proof: Suppose each of b1 and b2 is in B. (b1;b2)2ff 1 =)9a2A such that (b1;a)2f 1 and (a;b2)2f =)(a;b1)2f and (a;b2)2f =)b1 = b2 (since f is a function) =)(b1;b2)21B So ff 1 1B. Suppose ff 1 = 1B. 10 Suppose b2B. (b;b)21B = ff 1 =)9a2A such that (b;a)2f 1 and (a;b)2f =)a2A such that b = f(a) im(f) So f is a surjection. Suppose f is a surjection. Suppose (b;b)21B (so b2B). There is an a2A such that f(a) = b. (a;b)2f and (b;a)2f 1 =)(b;b)2ff 1 So 1B ff 1, and thus ff 1 = 1B. Theorem 1.18. Suppose A is a set. Then 1A is a bijection with respect to A. Proof: 1. 1A is an injection: 1A = 1A1A = 1 1A 1A So 1A is an injection. 2. 1A is a surjection with respect to A: 1A = 1A1A = 1A1 1A 11 So A = im(1A) and thus 1A is a surjection with respect to A. So 1A is a bijection with respect to A. De nition Suppose each of A and B is a set. Denote by A B the relation to which an ordered pair (a;b) belongs if and only if a2A and b2B. De nition Let I be a set. The statement that (A;R) is an I-structure means A is a set, and R is a set of relations each of which is a subset of I A. A is called the base set of (A;R) and I is called the index set of (A;R). De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function : A!B is preservative means for each r2R, r2S. De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function : A!B is saturating means for each s2S such that im(s) im( ), there is an r2R such that r = s. De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function : A!B is continuous means for each s2S, 1s2R. De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function : A ! B is conservative means for each r 2R, there is an s 2S such that im(s) im( ) and 1s = r. De nition Suppose ? : A!B is a function and each of (A;R) and (B;S) is an I-structure. The statement that ? is an I-structure homomorphism from (A;R) to (B;S) means ? is preservative and saturating. De nition Suppose ? : A!B is a function and each of (A;R) and (B;S) is an I-structure. The statement that ? is an I-structure cohomomorphism from (A;R) to (B;S) means ? is continuous and conservative. 12 De nition Suppose ? : A ! B is a function and each of (A;R) and (B;S) is an I- structure. The statement that ? is an I-structure isomorphism from (A;R) to (B;S) means ? is a continuous, preservative bijection. De nition The statement that an I-structure (A;R) and an I-structure (B;S) are iso- morphic means there is an isomorphism ? : A ! B from (A;R) to (B;S). In this case (A;R) = (B;S) denotes \(A;R) and (B;S) are isomorphic". Lemma 1.19.1. Suppose each of (A;R) and (B;S) is an I-structure and ? : A!B is a continuous function. Then ? is saturating. Proof: Suppose s2S such that im(s) im(?). ? is continuous, so ? 1s2R. So ? 1s2R and s = 1im(?)s = ?? 1s. So ? is saturating. Theorem 1.19. Suppose each of (A;R) and (B;S) is an I-structure and : A!B is a function. Then is a bijective I-structure homomorphism if and only if is an I-structure isomorphism. Proof: Suppose is a bijective I-structure homomorphism. is bijective and preservative, so it remains only to show that is continuous. Suppose s 2S. is surjective, so im(s) B = im( ). is saturating, so there is an r2R such that r = s. 1s = 1 r = 1Ar = r2R So is continuous and is thus an isomorphism. 13 Suppose is an I-structure isomorphism. is bijective and preservative. is continuous, so by Lemma 1.19.1, is saturating. So is a bijective homomorphism. Lemma 1.20.1. Suppose each of (A;R) and (B;S) is an I-structure and ? : A!B is a conservative function. Then ? is preservative. Proof: Suppose r2R. ? is conservative, so there is an s2S such that im(s) im(?) and ? 1s = r. So ?r = ?? 1s = 1im(?)s = s2S. So ? is preservative. Theorem 1.20. Suppose each of (A;R) and (B;S) is an I-structure and : A!B is a cohomomorphism. Then is a homomorphism. Proof: is conservative, so by Lemma 1.20.1, is preservative. is continuous, so by Lemma 1.19.1, is saturating. is both preservative and saturating, so is a homomorphism. Theorem 1.21. Suppose each of (A;R) and (B;S) is an I-structure and : A!B is a function. Then is a bijective cohomomorphism if and only if is an isomorphism. Proof: Suppose is a bijective cohomomorphism. 14 is bijective and continuous. is conservative, so by Lemma 1.20.1, is preservative. So is an isomorphism. Suppose is an isomorphism. is bijective and continuous, so it remains only to show that is conservative. Suppose r2R. is preservative, so r2S. im( r) im( ). 1 r = 1Ar = r So is conservative and is thus a bijective cohomomorphism. De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function ? : A ! B is a structure monomorphism means ? is an injective I-structure homomorphism. De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function ? : A!B is a structure epimorphism means ? is a surjective I-structure homo- morphism. Theorem 1.22. Suppose each of M = (A;R), N = (B;S), L = (C;T) is an I-structure, : A!B is an epimorphism from M to N, and : B!C is a homomorphism from N to L. Then is a homomorphism from M to L. Proof: Suppose r2R. is preservative, so r2S. is preservative, so r2T. So is preservative. Suppose t2T such that im(t) im( ). is saturating, and im(t) im( ) im( ), so 15 there is an s2S such that s = t. im(s) B = im( ), so there is an r2R such that r = s. So r2R such that r = s = t. So is saturating. is both preservative and saturating, and is thus a homomorphism. De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function ? : A ! B is a structure comonomorphism means ? is an injective I-structure cohomomorphism. De nition Suppose each of (A;R) and (B;S) is an I-structure. The statement that a function ? : A!B is a structure coepimorphism means ? is a surjective I-structure coho- momorphism. Theorem 1.23. Suppose each of M = (A;R), N = (B;S), L = (C;T) is an I-structure, : A!B is an coepimorphism from M to N, and : B!C is a cohomomorphism from N to L. Then is a cohomomorphism from M to L. Proof: Suppose t 2 T. is continuous, so 1t 2 S. is continuous, so ( ) 1t = 1 1t2R. So is continuous. Suppose r 2R. is conservative, so there is an s 2S such that im(s) im( ) and 1s = r. s2S, so there is an t2T such that im(t) im( ) and 1t = s. So t2T such that ( ) 1t = 1 1t = 1s = r. So is conservative. 16 is both continuous and conservative, and is thus a cohomomorphism. 17 Chapter 2 Equivalence Relations De nition Suppose r is a relation. The statement that r is symmetric means r 1 r. Lemma 2.1.1. Let r be a symmetric relation. Then r 1 = r. Proof: (x;y)2r =)(y;x)2r 1 r =)(x;y)2r 1 So r r 1 and since r 1 r, r 1 = r. De nition Suppose r is a relation. The statement that r is transitive means rr r. De nition Suppose r is a relation. The statement that r is an equivalence relation means r is symmetric and transitive. De nition Suppose r is a relation. The statement that r is re exive with respect to A means 1A r. Lemma 2.1.2. Suppose r is an equivalence relation. Then r is re exive with respect to dom(r). 18 Proof: (a;a)21dom(r) ()a2dom(r) ()9b such that (a;b)2r ()9b such that (a;b)2r and (b;a)2r 1 = r ()(a;a)2rr So 1dom(r) rr r. Remark Suppose A is a set. Then 1A is an equivalence relation. Lemma 2.1.3. Suppose r is a re exive relation. Then for each a2dom(r), a2r(fag). Proof: Suppose a2dom(r). 1dom(r) r, so a2fag= 1dom(r)(fag) r(fag). Lemma 2.1.4. Suppose r is an equivalence relation. Then rr = r. Proof: r = 1im(r)r = 1dom(r 1)r = 1dom(r)r rr So r rr. Then since rr r, rr = r. De nition Suppose A is a set. The statement that P is a partition of A means if P 2P then P A, and if a2A then a belongs to exactly one element of P. Theorem 2.1. Suppose r is an equivalence relation. Then r induces a partitionP of dom(r) by P =fr(fag) a2dom(r)g, each member of which is nonempty. 19 Proof: P 2P =)P = r(fag) for some a2dom(r) =)r(fag) = r 1(fag) dom(r) So each member of P is a subset of dom(r). Suppose a2dom(r). a2fag= 1dom(r)(fag) r(fag) So a belongs to one member of P. Suppose b2dom(r) and a2r(fbg). Then (b;a)2r and r = r 1 so (a;b)2r. p2r(fag) p2r(fbg) =)(a;p)2r =)(b;p)2r =)(b;p)2rr =)(a;p)2rr =)(b;p)2r =)(a;p)2r =)p2r(fbg) =)p2r(fag) So r(fag) = r(fbg). So a belongs to no more than one member of P. So P is a partition. 20 If P 2P, then P = r(fag) for some a 2 dom(r) so by Lemma 2.1.3, a 2 r(fag) = P, so P is nonempty. So each member of P is nonempty. Theorem 2.2. Suppose A is a set and f is a function with domain A. Then f 1f is an equivalence relation on A. Proof: 1. f 1f is symmetric: (f 1f) 1 = f 1(f 1) 1 = f 1f 2. f 1f is transitive: f 1ff 1f = f 11im(f)f = f 1f So f 1f is an equivalence relation. De nition Suppose A is a set and f is a function with domain A. Then denote by A=f the partition of Aff 1f(fag) a2Ag. Theorem 2.3. Suppose A is a set and r is an equivalence relation with domain A. Suppose P is the partition of A induced by r, and : A !P is the function which assigns each member of A to its part in P. Then r = 1 . Proof: (a1;a2)2r ()9P 2P such that a1 2P and a2 2P ()9P 2P such that (a1;P)2 and (a2;P)2 ()9P 2P such that (a1;P)2 and (P;a2)2 1 ()(a1;a2)2 1 So r = 1 . 21 De nition Suppose f is a function with domain A. Denote by f : A!A=f the function such that for each a2A, f(a) is the part in A=f to which a belongs. Theorem 2.4. Suppose A is a set, and f is a function with domain A. Then f is a surjection with respect to A=f. Proof: Suppose P 2A=f. P is nonempty, so there is an a2P, and by the de nition of f, f(a) = P. So f is a surjection with respect to A=f. Theorem 2.5. Suppose A is a set, and f is a function with domain A. Then for each a2A, f(a) = f 1f(fag). Proof: For each a2A, f(a) is the part in A=f to which a belongs. By Lemma 2.1.3, a belongs to f 1f(fag)2A=f, so f(a) = f 1f(fag). Theorem 2.6. Suppose A is a set, and f is a function with domain A. Then 1f f = f 1f. Proof: (a1;a2)2 1f f =)9P 2A=f such that (a1;P)2 f and (P;a2)2 1f =)(a1;P)2 f and (a2;P)2 f =)f 1(ff(a1)g) = f 1f(fa1g) = f(a1) = P = f(a2) = f 1f(fa2g) = f 1(ff(a2)g) =)f(a1) = 1im(f)f(a1) = ff 1f(a1) = ff 1f(a2) = 1im(f)f(a2) = f(a2) =)(a1;f(a1))2f and (f(a1);a2)2f 1 =)(a1;a2)2f 1f 22 So 1f f f 1f. (a1;a2)2f 1f =) f(a1) = f 1(f(fa1g)) = f 1(f(fa2g)) = f(a2) =)(a1; f(a1))2 f and (a2; f(a1))2 f =)(a1; f(a1))2 f and ( f(a1);a2)2 1f =)(a1;a2)2 1f f So f 1f 1f f. So 1f f = f 1f. Theorem 2.7. Suppose A is a set, and f is a function with domain A. Then A= f = A=f. Proof: A=f =ff 1f(fag) a2Ag=f 1f f(fag) a2Ag= A= f Theorem 2.8. Suppose A is a set, and f is a function with domain A. Then f = f. Proof: Suppose a2A. f(a) = f 1f(fag) = 1f f(fag) = f(a) Since this is true for each a2A, f = f. Theorem 2.9. Suppose A is a set, and f is a function with domain A. Then if P 2A=f then P = 1f (fPg) and f(P) =fPg. 23 Proof: Suppose P 2A=f and a2P. P = f(a) = f 1f(fag) = 1f f(fag) = 1f ( f(fag)) = 1f (f f(a)g) = 1f (fPg) So P = 1f (fPg). P = 1f (fPg) =) f(P) = f( 1f (fPg)) = f 1f (fPg) = 1A=f(fPg) =fPg So f(P) =fPg. Theorem 2.10. Suppose A is a set, f is a function with domain A, and each of a1 and a2 is in A. Then the following are equivalent: 1. There is a P 2A=f such that a1 and a2 belong to P. 2. f(a1) = f(a2) 3. a2 2 1f ( f(fa1g)) 4. (a1;a2)2 1f f 5. (a1;a2)2f 1f 6. a2 2f 1(f(fa1g)) 7. f(a1) = f(a2) Proof: 1 =) 2: Suppose there is a P 2A=f such that a1 and a2 belong to P. a1 2P so f(a1) = P and a2 2P so f(a2) = P. 24 So f(a1) = P = f(a2). 2 =) 3: Suppose f(a1) = f(a2). 1A 1f f =)fa2g= 1A(fa2g) 1f f(fa2g) = 1f (f f(a2)g) = 1f (f f(a1)g) = 1f ( f(fa1g)) =)a2 2 1f ( f(fa1g)) 3 =) 4: Suppose a2 2 1f ( f(fa1g)) = 1f f(fa1g). Then there is a pair (x;a2)2 1f f such that x2fa1g. So x = a1 and (a1;a2)2 1f f. 4 =) 5: Suppose (a1;a2)2 1f f. 1f f = f 1f, so (a1;a2)2 1f f = f 1f. 5 =) 6: Suppose (a1;a2)2f 1f. 25 Then a1 2fa1g such that (a1;a2)2f 1f, so a2 2f 1f(fa1g) = f 1(f(fa1g)). 6 =) 7: Suppose a2 2f 1(f(fa1g)). a2 2f 1(f(fa1g)) =)fa2g f 1f(fa1g) =)ff(a2)g= f(fa2g) f(f 1f(fa1g)) = ff 1f(fa1g) = 1im(f)f(fa1g) = f(fa1g) =ff(a1)g =)f(a1) = f(a2) 7 =) 1: Suppose f(a1) = f(a2). Consider f 1f(fa1g)2A=f. By Lemma 2.1.3: a1 2f 1f(fa1g) and a2 2f 1f(fa2g) = f 1(ff(a2)g) = f 1(ff(a1)g) = f 1(f(fa1g)) = f 1f(fa1g) So f 1f(fa1g)2A=f such that a1 and a2 belong to f 1f(fa1g). 26 Chapter 3 Structurizations Remark In this chapter 1 is used set theoretically, i.e., 1 =f0g. De nition Suppose (X; ) is a topological space[2]. Then the structurization of (X; ) is the 1-structure (X; _ ), where _ is f1 SjS2 g. Example Consider the set R with the standard topology R. Then the structurization of (R; R) is (R;R), where R=f1 S S2 Rg. E.g., 1 ( 3;1)2R. Theorem 3.1. Suppose each of (X; X) and (Y; Y ) is a topological space, and (X; _ X) is the structurization of (X; X), and (Y; _ Y ) is the structurization of (Y; Y ). Then : X!Y is preservative if and only if is an open function with respect to (X; X) and (Y; Y ). Proof: Suppose : X!Y is preservative. Suppose S 2 X. 1 S 2 _ X. De ne r = 1 S. r 2 _ Y so r = 1 T for some T in Y . [S] = [r[1]] = r[1] = T 2 Y . So is an open function with respect to (X; X) and (Y; Y ). Suppose : X!Y is an open function. Suppose r 2 _ X. Then r = 1 S for some S in X. Since is open, [S] 2 Y , so r = (1 S) = 1 [S]2 _ Y . So is preservative with respect to the 1-structures (X; _ X) and (Y; _ Y ). 27 Theorem 3.2. Suppose each of (X; X) and (Y; Y ) is a topological space, and (X; _ X) is the structurization of (X; X), and (Y; _ Y ) is the structurization of (Y; Y ). Then : X!Y is continuous if and only if is a continuous function with respect to (X; X) and (Y; Y ). Proof: Suppose : X!Y is (structurally) continuous. Suppose T 2 Y . Then 1 T 2 _ Y . De ne s = 1 T. 1s2 _ X so 1(T) = 1[s[1]] = 1s[1]2 X. So is a (topologically) continuous function with respect to (X; X) and (Y; Y ). Suppose : X!Y is a (topologically) continuous function. Suppose s2 _ Y . Then s = 1 T for some T 2 Y . Since is continuous, 1[T] 2 X, so 1s = 1(1 T) = 1 1[T]2 _ X So is (structurally) continuous with respect to the 1-structures (X; _ X) and (Y; _ Y ). Theorem 3.3. Suppose each of (X; X) and (Y; Y ) is a topological space, and the 1-structure (X; _ X) is the structurization of (X; X), and the 1-structure (Y; _ Y ) is the structurization of (Y; Y ). Then (X; X) and (Y; Y ) are homeomorphic if and only if (X; _ X) and (Y; _ Y ) are isomorphic. Proof: Let ? : A!B be a function. ? is a homeomorphism ()? is bijective, open, and (topologically) continuous ()? is bijective, preservative, and (structurally) continuous (Thm 3.1, Thm 3.2) ()? is a 1-structure isomorphism 28 Lemma 3.4.1. Suppose J is a nonempty set, and for each j2J, rj is a relation, and ? is a function. Then ? 1(Tj2Jrj) = Tj2J(? 1rj). Proof: (x;y)2? 1( \ j2J rj) ()9z such that (z;y)2? 1 and (x;z)2 \ j2J rj ()9z such that (z;y)2? 1 and (x;z)2rj for each j2J ()(x;y)2? 1rj for each j2J ()(x;y)2 \ j2J (? 1rj) So ? 1(Tj2Jrj) = Tj2J(? 1rj). Lemma 3.4.2. Suppose J is a set, and for each j2J rj is a relation, and ? is a function. Then ?(Sj2Jrj) = Sj2J(?rj). Proof: (x;y)2?( [ j2J rj) ()9z such that (z;y)2? and (x;z)2 [ j2J rj ()9z such that (z;y)2? and (x;z)2rj for some j2J ()(x;y)2?rj for some j2J ()(x;y)2 [ j2J (?rj) So ?(Sj2Jrj) = Sj2J(?rj). 29 Theorem 3.4. Suppose each of (A;R) and (B;S) is a 1-structure, ? : A ! B is a co- epimorphism, and (A;R) is the structurization of a topological space. Then (B;S) is the structurization of a topological space. Proof: ? is a cohomomorphism, so by Theorem 1.20, ? is a homomorphism. 1. ?2R, and ? is preservative, so ? = ??2S. 2. 1 A2R, so suppose r = 1 A. ? is surjective, and ? is preservative, so 1 B = 1 ?[A] = ?(1 A) = ?r2S. 3. Suppose J is a set, and for each j2J, sj2S. ? is continuous, so for each j 2 J, ? 1sj 2R. (A;R) is the structurization of a topological space, so Sj2J? 1sj2R. ? is preservative and surjective, so by Lemma 3.4.2, [ j2J sj = [ j2J ?? 1sj = ? [ j2J ? 1sj2S 4. Suppose each of s0 and s1 is in S. ? is continuous, so each of ? 1s0 and ? 1s1 is in R. (A;R) is the structurization of a topological space, so by Lemma 3.4.1, ? 1(s0\s1) = (? 1s0)\(? 1s1)2R. ? is preservative and surjective, so s0\s1 = ?? 1(s0\s1)2S. So by the above, (B;S) is the structurization of a topological space. Theorem 3.5. Suppose each of (A;R) and (B;S) is a 1-structure, ? : A ! B is a comonomorphism, and (B;S) is the structurization of a topological space. Then (A;R) is the structurization of a topological space. 30 Proof: Suppose (B;S) is the structurization of a topological space. 1. ?2S, and ? is continuous, so ? = ? 1?2R. 2. 1 B2S, so suppose s = 1 B. ? is continuous, so 1 A = 1 ? 1[B] = ? 1(1 B) = ? 1s2R. 3. Suppose J is a set, and for each j2J, rj2R. ? is preservative, so for each j 2 J, ?rj 2 S. (B;S) is the structurization of a topological space, so Sj2J?rj2S. ? is continuous and injective, so by Lemma 3.4.2, [ j2J rj = ? 1?( [ j2J rj) = ? 1( [ j2J ?rj)2R 4. Suppose each of r0 and r1 is in R. ? is preservative, so each of ?r0 and ?r1 is in S. (B;S) is the structurization of a topological space, so (?r0)\(?r1)2S. ? is continuous and injective, so by Lemma 3.4.1, r0 \r1 = (? 1?r0)\(? 1?r1) = ? 1((?r0)\(?r1))2R. So by the above, (A;R) is the structurization of a topological space. De nition The statement that F is a type means F is a function with domain a set of symbols and image a subset of the cardinal numbers[3]. De nition LetF be a type. The statement that A = (A;F) is an algebra of typeF means A is a set, F is a set of functions each having image a subset of A, and there is a bijection g : dom(F)!F such that for each f2dom(F), dom(g(f)) = AF(f). For each f2dom(F), denote g(f) by fA. 31 De nition Let A = (A;F) be an algebra of type F. De ne I to be the set of symbols S f2dom(F) fpfg[Sq2F(f)fqfg . The structurization of (A;F) is the I-structure (A;R) where R is the set of functions to which a function r belongs if and only if there is an f in dom(F) and an element a in AF(f) such that the domain of r is fpfg[Sq2F(f)fqfg and for each element q in F(f), r(qf) = a(q), and r(pf) = fA(a). Example Suppose F = f(e;0);( 1;1);( ;2)g is the type associated with groups. e is the symbol corresponding with the 0-ary function that for each group, picks out the identity el- ement of the group, 1 is the symbol corresponding with the unary function that associates each element of the group with its inverse, and is the symbol corresponding with the binary function of the group. Consider the dihedral group D6 =f ; ; 2; ; ; 2g. Then the structurization of D6 is the I-structure (D6;R), with I = fpe;p 1;0 1;p ;0 ;1 g 32 and R=f f(pe; )g; f(p 1; );(0 1; )g;f(p 1; );(0 1; 2)g;f(p 1; 2);(0 1; )g; f(p 1; );(0 1; )g;f(p 1; );(0 1; )g;f(p 1; 2);(0 1; 2)g; f(p ; );(0 ; );(1 ; )g;f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; 2);(1 ; )g; f(p ; );(0 ; );(1 ; )g;f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; 2);(1 ; )g; f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; );(1 ; )g;f(p ; );(0 ; 2);(1 ; )g; f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; );(1 ; )g;f(p ; );(0 ; 2);(1 ; )g; f(p ; 2);(0 ; );(1 ; 2)g;f(p ; );(0 ; );(1 ; 2)g;f(p ; );(0 ; 2);(1 ; 2)g; f(p ; 2);(0 ; );(1 ; 2)g;f(p ; );(0 ; );(1 ; 2)g;f(p ; );(0 ; 2);(1 ; 2)g; f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; );(1 ; )g;f(p ; );(0 ; 2);(1 ; )g; f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; );(1 ; )g;f(p ; );(0 ; 2);(1 ; )g; f(p ; );(0 ; );(1 ; )g;f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; 2);(1 ; )g; f(p ; );(0 ; );(1 ; )g;f(p ; );(0 ; );(1 ; )g;f(p ; 2);(0 ; 2);(1 ; )g; f(p ; 2);(0 ; );(1 ; 2)g;f(p ; );(0 ; );(1 ; 2)g;f(p ; );(0 ; 2);(1 ; 2)g; f(p ; 2);(0 ; );(1 ; 2)g;f(p ; );(0 ; );(1 ; 2)g;f(p ; );(0 ; 2);(1 ; 2)g g 33 Theorem 3.6. Suppose each of A = (A;F) and B = (B;G) is an algebra of type F, and (A;R) is the structurization of (A;F) and (B;S) is the structurization of (B;G). Then a function ? : A!B is an algebraic homomorphism if and only if it is aSf2dom(F) fpfg[Sq2F(f)fqfg - structure homomorphism. Proof: Suppose ? is an algebraic homomorphism. Suppose r 2 R. Then there is an f in dom(F) and an element a in AF(f) such that the domain of r is fpfg[Sq2F(f)fqfg and for each element q in F(f), r(qf) = a(q), and r(pf) = fA(a). ?a is an element in BF(f), so there is an s2S such that the domain of s isfpfg[Sq2F(f)fqfg and for each element q in F(f), s(qf) = ?a(q) = ?(a(q)) = ?(r(qf)) = ?r(qf), and s(pf) = fB(?a) = ?(fA(a)) = ?(r(pf)) = ?r(pf). So ?r = s2S and ? is preservative. Suppose s2S such that im(s) im(?). There is an f in dom(F) and an element b in BF(f) such that the domain of s is fpfg[ S q2F(f)fqfg, and for each element q in F(f), s(qf) = b(q), and s(pf) = f B(b). Moreover, for each q 2F(f), since b(q) = s(qf) 2 im(s) im(?), there is an aq 2 A such that b(q) = ?(aq). De nea :F(f)!Asuch that for eachq2F(f), a(q) = aq. ais an element inAF(f), so there is an r2Rsuch that the domain of r isfpfg[Sq2F(f)fqfgand for each element q inF(f), r(qf) = a(q), and r(pf) = fA(a). Note for each q2F(f), b(q) = ?(aq) = ?(a(q)) = ?a(q), 34 so b = ?a. For each q in F(f), s(qf) = b(q) = ?a(q) = ?(a(q)) = ?(r(qf)) = ?r(qf). s(pf) = fB(b) = fB(?a) = ?(fA(a)) = ?(r(pf)) = ?r(pf). So r is a relation in R such that ?r = s, and ? is saturating. Thus ? is an Sf2dom(F) fpfg[Sq2F(f)fqfg -structure homomorphism. Suppose ? is an Sf2dom(F) fpfg[Sq2F(f)fqfg -structure homomorphism. Suppose f is in dom(F) and a is an element in AF(f). Then there is an r 2R such that such that the domain of r is fpfg[Sq2F(f)fqfg and for each element q in F(f), r(qf) = a(q), and r(pf) = fA(a). ? is an I-structure homomorphism, so ?r2S. Since ?r is in S, and has domain fpfg[Sq2F(f)fqfg, and for each q 2F(f), ?r(qf) = ?(r(qf)) = ?(a(q)) = ?a(q), f is the member of dom(F) and ?a is the element in BF(f) such that ?r(pf) = fB(?a). ?(fA(a)) = ?(r(pf)) = ?r(pf) = fB(?a). So ? is an algebraic homomorphism. 35 Theorem 3.7. Suppose each of A = (A;F) and B = (B;G) is an algebra of type F, and (A;R) is the structurization of (A;F) and (B;S) is the structurization of (B;G). Then a function ? : A!B is an algebraic isomorphism if and only if it is anSf2dom(F) fpfg[Sq2F(f)fqfg - structure isomorphism. Proof: Suppose ? : A!B is a function. ? is an algebraic isomorphism ()? is a bijective algebraic homomorphism ()? is a bijective structure homomorphism ()? is an I-structure isomorphism Remark Graph will hereafter be used to refer to graphs which may contain loops and multiple edges[4]. De nition Let G be a graph. De ne V(G) to be the vertex set of G. De nition Let G be a graph. De ne E(G) to be the edge set of G. De nition Let G be a graph. The structurization of G is the Nnf0g-structure (A;R) where R is the set of relations to which a relation f : Nnf0g!V(G) belongs if and only if f contains either one or two pairs each having the same rst element n, and there are at least n edges joining the vertices in f[fng]. (If there is exactly one pair (n;v) in f, then the n edges correspond to n loops at v). Theorem 3.8. Suppose each of G and H is a graph. Suppose the Nnf0g-structure (V(G);R) is the structurization of G and the Nnf0g-structure (V(H);S) is the structurization of H. Then the graphs G and H are isomorphic if and only if (V(G);R) and (V(H);S) are iso- morphic. 36 Proof: Suppose G and H are isomorphic, and ? : V(G) !V(H) is a graph isomorphism. ? is a bijection. Suppose r 2R. Suppose r contains exactly one element (n;v). Then there are at least n loops at vertex v in G, so there are at least n loops at vertex ?(v) in H. Thus there is a s2S such that s contains exactly one element (n;?(v)), so s[fng] = ?[r[fng]] = ?r[fng]. So s = ?r. Suppose r contains exactly two elements (n;v) and (n;w). Then there are at least n edges connecting vertices v and w in G, so there are at least n edges connecting vertices ?(v) and ?(w) in H. Thus there is a s2S such that s contains exactly two elements (n;?(v)) and (n;?(w)), so s[fng] = ?[r[fng]] = ?r[fng]. So s = ?r. So in both cases there is a s in S such that s = ?r, so ? is preservative. Suppose s2S. Suppose s contains exactly one element (n;v). Then there are at least n loops at vertex w in H, so there are at least n loops at vertex ? 1(v) in G. Thus there is a r2R such that r contains exactly one element (n;? 1(v)), so r[fng] = ? 1[s[fng]] = ? 1s[fng]. So r = ? 1s. Suppose s contains exactly two elements (n;v) and (n;w). Then there are at least n edges connecting vertices v and w in H, so there are at least n edges connecting vertices ? 1(v) and ? 1(w) in G. Thus there is a r2R such that r contains exactly two elements (n;? 1(v)) and (n;? 1(w)), so r[fng] = ? 1[s[fng]] = ? 1s[fng]. So r = ? 1s. So ? is continuous and thus ? is a Nnf0g-structure isomorphism. 37 Suppose (V(G);R) and (V(H);S) are isomorphic and : V(G)!V(H) is a Nnf0g-structure isomorphism and hence a bijection. Suppose n 2 N, and there are exactly n loops at vertex v in G. If n 6= 0 then there is a relation r2R such that r = f(n;v)g, and f(n; (v))g = r2S, so there are at least n loops in H at vertex (v). Suppose s =f(n+ 1; (v))g. If s2S, thenf(n+ 1;v)g=f(n+ 1; 1( (v)))g= 1s2R, and thus there are n + 1 loops at v, contradicting the assumption that there are exactly n loops at v in G. So s =2S, and thus there are not n + 1 loops at (v). So there are exactly n loops at (v) in H. Suppose n2N, and there are exactly n edges connecting vertices v and w in G. If n6= 0 then there is a relation r2Rsuch that r =f(n;v);(n;w)g, andf(n; (v));(n; (w))g= r2S, so there are at least n edges in H connecting vertices (v) and (w). Suppose s = f(n + 1; (v));(n + 1; (w))g. If s2S, then f(n + 1;v);(n + 1;w)g = f(n + 1; 1( (v)));(n+ 1; 1( (w)))g= 1s2R, and thus there are n+ 1 edges connecting v and w, contradicting the assumption that there are exactly n edges connecting v and w in G. So s =2S, and thus there are not n + 1 edges connecting (v) and (w). So there are exactly n edges connecting (v) and (w) in H. So is a graph isomorphism and G and H are isomorphic. 38 Chapter 4 Fundamental (Co)Homomorphism Theorems Lemma 4.1.1. Suppose each of A, B, and C is a set, : A!B is a surjection, : A!C is a function, and 1 1 . Then 1 is a unique function with domain B such that ( 1) = . Moreover, im( 1) = im( ). A ?? ??? ??? ??? ??? ?? B 1 //_____________ C Proof: (b;c1)2 1 and (b;c2)2 1 =)9a1 2A such that (b;a1)2 1 and (a1;c1)2 and 9a2 2A such that (b;a2)2 1 and (a2;c2)2 =)(a1;b)2 and (b;a2)2 1; c1 = (a1); c2 = (a2) =)(a1;a2)2 1 1 ; c1 = (a1); c2 = (a2) =)9c2C such that (a1;c)2 and (c;a2)2 1; c1 = (a1); c2 = (a2) =)(a1;c)2 and (a2;c)2 ; c1 = (a1); c2 = (a2) =)c1 = (a1) = c = (a2) = c2 So 1 is a function. 39 Note 1A 1 and 1 1C. ( 1) = ( 1 ) ( 1 ) = ( 1) 1C = = 1A ( 1 ) = ( 1) So ( 1) = . Suppose is a function with domain B such that = . is a surjection, so 1 = 1B = =) = 1B = 1 = 1 So 1 is the only function having domain B with the property that ( 1) = . im( 1) = (im( 1)) = (dom( )) = (A) = im( ) So im( 1) = im( ). Corollary 4.1.1. Suppose each of A, B, and C is a set, : A ! B is a surjection, : A!C is a function, and 1 1 . Then is a surjection if and only if 1 is a surjection with respect to C. Proof: Suppose is a surjection. By Lemma 4.1.1, 1 is a function. C = im( ) = im( 1), so 1 is a surjection with respect to C. Suppose 1 is a surjection with respect to C. 40 C = im( 1) = im( ), so is a surjection. Corollary 4.1.2. Suppose each of A, B, and C is a set, : A ! B is a surjection, : A!C is a function, and 1 1 . Then 1 = 1 if and only if 1 is an injection. Proof: Suppose 1 = 1 . ( 1) 1 1 = 1 1 = 1 1 = 1B1B = 1B So 1 is an injection. Suppose 1 is an injection. Note 1 = 1 = 1A 1 1 1 = 1 1( 1 ) = 1( 1) 1 1 = 11B = 1 So 1 1 and thus 1 = 1 . Lemma 4.1.2. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : A!B is a saturating surjection, : A!C is a preservative function, and 1 1 . Then 1 is preservative. Proof: Suppose s2S. im(s) B = im( ), so since is saturating, there is an r 2R such that r = s. is preservative, so r 2 T. By Lemma 4.1.1, 1 = , so 1s = 1 r = r. Thus 1s = r2T. So 1 is preservative. Lemma 4.1.3. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : A!B is a preservative surjection, : A!C is a saturating function, and 1 1 . Then 1 is saturating. 41 Proof: Suppose t2T and im(t) im( 1) = im( ). is saturating, so there is an r2R such that r = t. is preservative, so r2S. By Lemma 4.1.1, 1 = , so ( 1)( r) = ( 1 )r = r = t. So r is a relation in S such that ( 1) r = t. So 1 is saturating. Theorem 4.1. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : A!B is an epimorphism, : A!C is a homomorphism, and 1 1 . Then 1 is a unique homomorphism with domain B such that 1 = . Proof: By Lemma 4.1.1, 1 is a unique function with domain B such that 1 = . is a homomorphism and thus is saturating, and is a homomorphism and thus is preser- vative, so by Lemma 4.1.2, 1 is preservative. is a homomorphism and thus is preservative, and is a homomorphism and thus is saturating, so by Lemma 4.1.3, 1 is saturating. Since 1 is both preservative and saturating, 1 is an I-structure homomorphism. Lemma 4.2.1. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : A!B is a conservative surjection, : A!C is a continuous function, and 1 1 . Then 1 is continuous. Proof: Suppose t 2T. is continuous, so, 1t 2R. is conservative, so there is an s2S such that im(s) im( ) and 1s = 1t. is surjective, so 1 = 1B. ( 1) 1t = 1t = 1s = 1Bs = s 42 Thus ( 1) 1t = s2S. So 1 is continuous. Lemma 4.2.2. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : A!B is a continuous surjection, : A!C is a conservative function, and 1 1 . Then 1 is conservative. Proof: Suppose s2S. is continuous, so 1s2R. is conservative, so there is a t2T such that im(t) im( ) and 1t = 1s. is surjective, so 1 = 1B. ( 1) 1t = 1t = 1s = 1Bs = s Thus ( 1) 1t = s, and t is a relation in T such that im(t) im( ) = im( 1) and ( 1) 1t = s. So 1 is conservative. Theorem 4.2. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : A!B is a coepimorphism, : A!C is a cohomomorphism, and 1 1 . Then 1 is a unique cohomomorphism with domain B such that 1 = . Proof: By Lemma 4.1.1, 1 is a unique function with domain B such that 1 = . is a cohomomorphism and thus is conservative, and is a cohomomorphism and thus is continuous, so by Lemma 4.2.1, 1 is continuous. is a cohomomorphism and thus is continuous, and is a cohomomorphism and thus is conservative, so by Lemma 4.2.2, 1 is conservative. Since 1 is both continuous and conservative, 1 is an I-structure cohomomorphism. Lemma 4.3.1. Suppose each of and is a function. Then 1 1 if and only if im( ) im( ). 43 Proof: Suppose 1 1. im( ) = im(1im( )) = im( 1) im( 1) = im(1im( )) = im( ) Suppose im( ) im( ). 1 = 1im( ) 1im( ) = 1 Lemma 4.3.2. Suppose each of A, B, and C is a set, : B!A is a function, : C!A is an injection, and 1 1. Then 1 is a unique function with image a subset of C such that ( 1 ) = . Moreover, dom( 1 ) = dom( ). A?? __ / O?? ??? ??? ??? ??? ?? B 1 //_____________ C Proof: (b;c1)2 1 and (b;c2)2 1 =)9a1 2A such that (b;a1)2 and (a1;c1)2 1 and 9a2 2A such that (b;a2)2 and (a2;c2)2 1 =)a1 = a2 since is a function =)(c1;a1)2 and (c2;a1)2 =)c1 = c2 since is an injection So 1 is a function. 44 Note 1 1A and 1 = 1im( ). ( 1 ) = ( 1) 1A = = 1im( ) = ( 1) ( 1) = ( 1 ) So ( 1 ) = . Suppose is a function with image a subset of C such that = . Note since is an injection, 1 = 1C. = =) = 1C = 1 = 1 So 1 is the only function with image a subset of C with the property that ( 1 ) = . b2dom( 1 ) =)9c2C such that (b;c)2 1 =)9a2A such that (b;a)2 and (a;c)2 1 =)b2dom( ) So dom( 1 ) dom( ). b2dom( ) =)9a2A such that (b;a)2 = ( 1 ) =)9c2C such that (c;a)2 and (b;c)2 1 =)b2dom( 1 ) 45 So dom( ) dom( 1 ), and thus dom( 1 ) = dom( ). Corollary 4.3.1. Suppose each of A, B, and C is a set, : B!A is a function, : C!A is an injection, and 1 1. Then is an injection if and only if 1 is an injection. Proof: Suppose is an injection. im( ) im( ). ( 1 ) 1 1 = 1 1 = 11im( ) = 1 = 1B So 1 is an injection. Suppose 1 is an injection. 1 = 11im( ) = 1 1 = ( 1 ) 1 1 = 1B So is an injection. Corollary 4.3.2. Suppose each of A, B, and C is a set, : B!A is a function, : C!A is an injection, and 1 1. Then 1 = 1 if and only if 1 is a surjection with respect to C. Proof: Suppose 1 = 1. 1 ( 1 ) 1 = 1 1 = 1 1 = 1C1C = 1C So 1 is a surjection with respect to C. Suppose 1 is a surjection with respect to C. 1 = 1C 1 = 1 ( 1 ) 1 1 = 1 1 1 = 1im( ) 11im( ) = 1 46 Lemma 4.3.3. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : B!A is a preservative function, : C!A is a saturating injection, and 1 1. Then 1 is preservative. Proof: Suppose s2S. is preservative, so s2R. im( s) im( ) im( ), so since is saturating, there is a t2T such that t = s. Thus 1 s = 1 t = 1At = t2T. So 1 is preservative. Lemma 4.3.4. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : B!A is a saturating function, : C!A is a preservative injection, and 1 1. Then 1 is saturating. Proof: Suppose t 2 T such that im(t) im( 1 ). is preservative, so t 2 R. im( t) = (im(t)) (im( 1 )) = im( 1 ) im(1A ) = im( ), so since is sat- urating, there is an s2S such that s = t. So s is a relation in S such that 1 s = 1 t = 1At = t. So 1 is saturating. Theorem 4.3. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : B !A is a homomorphism, : C !A is a monomorphism, and 1 1. Then 1 is a unique homomorphism with image a subset of C such that 1 = . Proof: By Lemma 4.3.2, 1 is a unique function with image a subset of C such that 1 = . is a homomorphism and thus is preservative, and is a homomorphism and thus is saturating, so by Lemma 4.3.3, 1 is preservative. 47 is a homomorphism and thus is saturating, and is a homomorphism and thus is preser- vative, so by Lemma 4.3.4, 1 is saturating. Since 1 is both preservative and saturating, 1 is an I-structure homomorphism. Lemma 4.4.1. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : B !A is a continuous function, : C !A is a conservative injection, and 1 1. Then 1 is continuous. Proof: Suppose t2T. is conservative, so there is an r2Rsuch that im(r) im( ) and 1r = t. is continuous, so 1r2S. ( 1 ) 1t = 1 t = 1 1r = 11im( )r = 1r Thus ( 1 ) 1t = 1r2S. So 1 is continuous. Lemma 4.4.2. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : B !A is a conservative function, : C!A is a continuous injection, and im( ) im( ). Then 1 is conservative. Proof: Suppose s2S. is conservative, so there is an r2R such that im(r) im( ) im( ) and s = 1r. is continuous, so 1r2T. ( 1 ) 1 1r = 1 1r = 11im( )r = 1r = s Thus ( 1 ) 1 1r = s, and 1r is a relation in T such that im( 1r) = 1(im(r)) 1(im( )) = im( 1 ) and ( 1 ) 1 1r = s. So 1 is conservative. Theorem 4.4. Suppose each of (A;R), (B;S), and (C;T) is an I-structure, : B!A is a cohomomorphism, : C!A is a comonomorphism, and 1 1. Then 1 is a unique cohomomorphism with image a subset of C such that 1 = . 48 Proof: By Lemma 4.3.2, 1 is a unique function with image a subset of C such that 1 = . is a cohomomorphism and thus is continuous, and is a cohomomorphism and thus is conservative, so by Lemma 4.4.1, 1 is continuous. is a cohomomorphism and thus is conservative, and is a cohomomorphism and thus is continuous, so by Lemma 4.4.2, 1 is conservative. Since 1 is both continuous and conservative, 1 is an I-structure cohomomorphism. 49 Chapter 5 First Isomorphism Theorems De nition Suppose M = (A;R) is an I-structure and B A. The I-substructure of M induced by B is the I-structure (B; ^R) where ^R is the set of relations to which a relation ^r belongs if and only if ^r 2R and im(^r) B. Denote the I-structure (B; ^R) by MjB. The statement that (C;T) is an I-substructure of M means C A and (C;T) is the I- substructure of M induced by C. De nition Suppose M = (A;R) is an I-structure and ? is a function with domain A. Suppose R is the set of relations to which a relation r belongs if and only if there is a relation r2R such that r = ?r. Denote the I-structure (A=?; R) by M=?. Lemma 5.1.1. Suppose each of A and B is a set, and ? : A!B is a function. Then ? 1? is a bijection with respect to im(?). Proof: By Theorem 2.4, ? is a surjection with respect to A=?, and by Theorem 2.6, 1? ? ? 1?, so by Lemma 4.1.1, ? 1? is a function. ? is a surjection with respect to im(?), so by Corollary 4.1.1, ? 1? is a surjection with respect to im(?). By Theorem 2.6 ? 1? = 1? ?, so by Corollary 4.1.2, ? 1? is an injection. Thus ? 1? is a function which is both an injection and a surjection with respect to im(?), so ? 1? is a bijection with respect to im(?). 50 Lemma 5.1.2. Suppose each of M = (A;R) and (B;S) is an I-structure, and ? : A!B is a function. Then ? is a I-structure epimorphism with respect to the I-structure M=? = (A=?; R). Proof: 1. ? is preservative: Suppose r2R, then ?r2 R by de nition of M=?. 2. ? is saturating: Suppose r2 R such that im( r) im( ?), then by the de nition of M=? there is an r2R such that ?r = r. 3. ? is a surjection: By Theorem 2.4. So ? is an epimorphism. Lemma 5.1.3. Suppose each of M = (A;R) and N = (B;S) is an I-structure, and ? : A!B is a function. Then ? is an I-structure homomorphism from M to N if and only if ? is an I-structure homomorphism from A to the I-substructure of M induced by im(?), (im(?); ^S). Proof: Suppose ? is an I-structure homomorphism from M to N. Suppose r2R. ? is preservative, so ?r2S. Suppose b 2 im(?r). Then there is an i 2 I such that (i;b) 2 ?r. There is an a 2 A such that ?(a) = b and (i;a)2r. b = ?(a)2im(?). So im(?r) im(?), and thus ?r2 ^S. So ? is preservative between (A;R) and (im(?); ^S). Suppose ^s2 ^S such that im(^s) im(?). ? is saturating and ^s2S, so there is an r2R such that ?r = ^s. 51 So ? is saturating between (A;R) and (im(?); ^S). ? is both preservative and saturating between (A;R) and (im(?); ^S), so ? is an I-structure homomorphism between (A;R) and (im(?); ^S). Suppose ? is an I-structure homomorphism from A to the I-substructure of M induced by im(?). Suppose r2R. ? is preservative with respect to (im(?); ^S), so ?r2 ^S, so ?r2S. So ? is preservative between M and N. Suppose s 2S such that im(s) im(?). Then s 2 ^S, and since ? is saturating with respect to (im(?); ^S), there is an r2R such that ?r = s. So ? is saturating between M and N. ? is both preservative and saturating between M and N, so ? is an I-structure homo- morphism between M and N. Theorem 5.1. Suppose each of M = (A;R) and N = (B;S) is an I-structure and ? : A!B is a function. Then ? is an I-structure homomorphism if and only if ? 1? is an isomorphism from M=? to the I-substructure of N induced by im(?). Proof: Suppose ? is an I-structure homomorphism. M=? = (A=?; R) where R is the set of relations to which a relation r belongs if and only if there is a relation r2R such that ?r = r. 52 The I-substructure of N induced by im(?) is (im(?); ^S) where ^S is the set of relations to which a relation ^s belongs if and only if ^s2S and im(^s) im(?). By Lemma 5.1.2, ? is an I-structure epimorphism, by Lemma 5.1.3, ? is an I-structure homomorphism between (A;R) and (im(?); ^S), and by Lemma 2.6, 1? ? ? 1?. So by Theorem 4.1, ? 1? is a homomorphism. By Lemma 5.1.1, ? 1? is a bijection, so by Theorem 1.19, ? 1? is an isomorphism. So M=? is isomorphic to the I-substructure of N induced by im(?). Suppose ? 1? is an isomorphism from M=? to the I-substructure of N induced by im(?). By Lemma 5.1.2 ? is an epimorphism, and by assumption, ? 1? is a homomorphism from M=? to the I-substructure of N induced by im(?). So by Theorem 1.22, (? 1? ) ? is a homomorphism from M to the I-substructure of N induced by im(?). By Lemma 4.1.1, ? = (? 1? ) ?, so ? is a homomorphism from M to the I-substructure of N induced by im(?), and thus by Lemma 5.1.3, ? is a homomorphism from M to N. Corollary 5.1.1. Suppose each of M = (A;R) and (B;S) is a 1-structure, and ? : A!B is a homomorphism. Then if each of (A;R) and (B;S) is the structurization of a topological space, then (A=?; R) is the structurization of a topological space. Proof: 1. 1 A=?2 R: 53 (A;R) is the structurization of a topological space, so 1 A2R. ? is an epimorphism, so 1 A=? = 1 ?[A] = ?(1 A)2 R. 2. ?2 R: (A;R) is the structurization of a topological space, so ?2R. ? is a homomorphism, so ? = ??2 R. 3. Suppose J is a set and for each j 2 J, rj 2 R, then there is an r 2 R such that r[1] = S j2J rj[1]: For each j2J, there is an rj 2R such that ?rj = rj. Since (A;R) is the structur- ization of a topological space, there is an r2R such that r[1] = S j2J rj[1]. ?r2 R. P 2 ?r[1] ()P 2 ?[r[1]] ()P 2 ?( [ j2J rj[1]) = [ j2J ?[rj[1]] by Lemma 3.4.2 ()P 2 [ j2J ?rj[1] ()P 2 [ j2J rj[1] So ?r2 R such that ?r[1] = S j2J rj[1]. 4. Suppose each of r1 and r2 is in R, then there is an r2 Rsuch that r[1] = r1[1]\ r2[1]: By the de nition of R, there is an r1 2 R and an r2 2 R such that ?r1 = r1 and ?r2 = r2. 54 Since ? is a homomorphism, ?r1 2S and ?r2 2S, and since (B;S) is the structuriza- tion of a topological space, there is an s2S such that s[1] = ?r1[1]\?r2[1] im(?). So there is an r2R such that ?r = s. ?r[1] = ?[r[1]] =f ?(a) a2r[1]g =f? 1[?[fag]] a2r[1]g =f ?(a) a2? 1[?[r[1]]]g =f ?(a) a2? 1[s[f0g]]g =f ?(a) a2? 1[?r1[1]\?r2[1]]g =f ?(a) a2? 1[?[r1[1]]\?[r2[1]]]g =f ?(a) a2? 1[?[r1[1]]]\? 1[?[r2[1]]]g =f ?(a) a2? 1[?[r1[1]]]g\f ?(a) a2? 1[?[r2[1]]]g =f? 1[?[fag]] a2r1[1]g\f? 1[?[fag]] a2r2[1]g =f ?(a) a2r1[1]g\f ?(a) a2r2[1]g = ?[r1[1]]\ ?[r2[1]] = ?r1[1]\ ?r2[1] = r1[1]\ r2[1] So ?r2 R such that ?r[1] = r1[1]\ r2[1]. So by the above properties, (A=?; R) is the structurization of a topological space. Corollary 5.1.2. Suppose (G; ) is a group with identity e, I = fpe;p 1;0 1;p ;0 ;1 g, M = (G;R) is the structurization of (G; ), and ? is a function with domain G. Then M=? is the structurization of a group under the operation induced by if and only if for all (a1;a2) 2? 1?, (a 11 ;a 12 ) 2? 1?, and for all (a1;b1);(a2;b2) in ? 1?, (a1 a2;b1 b2) 2 ? 1?. 55 Proof: Suppose for all (a1;a2) 2 ? 1?, (a 11 ;a 12 ) 2 ? 1?, and for all (a1;b1);(a2;b2) in ? 1?, (a1 a2;b1 b2)2? 1?. Suppose each of P = ? 1?(fxg) and Q = ? 1?(fyg) is in G=?. P Q =fp qjp2P and q2Qg. Consider the element of G=?, ? 1?(fx yg). g2P Q =)9p2P; q2Q such that g = p q =)9p2? 1?(fxg); q2? 1?(fyg) such that g = p q =)9p;q such that (p;x)2? 1? and (q;y)2? 1? and g = p q =)9p;q such that (p q;x y)2? 1? and g = p q =)g2? 1?(fx yg) So P Q ? 1?(fx yg). g2? 1?(fx yg) =)(g;x y)2? 1? and (y 1;y 1)2? 1? =)(g y 1;x) = (g y 1;x e) = (g y 1;x (y y 1)) = (g y 1;(x y) y 1)2? 1? =)g y 1 2? 1?(fxg) = P and y2? 1?(fyg) = Q =)g = g e = g (y 1 y) = (g y 1) y2P Q So ? 1?(fx yg) P Q. Thus ? 1?(fxg) ? 1?(fyg) = P Q = ? 1?(fx yg)2G=?. So G=? is closed under the operation . 56 Consider the element ? 1?(feg). By the above, if P = ? 1?(fxg)2G=?, then: P ? 1?(feg) = ? 1?(fxg) ? 1?(feg) = ? 1?(fx eg) = ? 1?(fxg) = P And ? 1?(feg) P = ? 1?(feg) ? 1?(fxg) = ? 1?(fe xg) = ? 1?(fxg) = P So ? 1?(feg) is an identity in G=? with respect to the operation . Suppose P = ? 1?(fxg)2G=?. Consider ? 1?(fx 1g). P ? 1?(fx 1g) = ? 1?(fxg) ? 1?(fx 1g) = ? 1?(fx x 1g) = ? 1?(feg) And ? 1?(fx 1g) P = ? 1?(fx 1g) ? 1?(fxg) = ? 1?(fx 1 xg) = ? 1?(feg) So ? 1?(fx 1g) is an inverse for P with respect to the identity ? 1?(feg). Suppose each of P = ? 1?(fxg), Q = ? 1?(fyg), and R = ? 1?(fzg) are members of 57 G=?. (P Q) R = (? 1?(fxg) ? 1?(fyg)) ? 1?(fzg) = ? 1?(fx yg) ? 1?(fzg) =? 1?(f(x y) zg) = ? 1?(fx (y z)g) = ? 1?(fxg) ? 1?(fy zg) =? 1?(fxg) (? 1?(fyg) ? 1?(fzg)) = P (Q R) So G=? is associative with respect to the operation . So (G=?; ) is a group. (Note that saying for all (a1;a2) 2? 1?, (a 11 ;a 12 ) 2? 1?, and for all (a1;b1);(a2;b2) in ? 1?, (a1 a2;b1 b2)2? 1? implies that ? 1?(feg) is a normal subgroup of G). Now I intend to prove that M=? is the structurization of said group. M=? = (G=?; R) where I =fpe;p 1;0 1;p ;0 ;1 g and R=f rjr2Rg. The strucuturization of (G=?; ) = (G=?;S) where S is the set of relations to which a relation s belongs if and only if either s = f(pe;? 1?(e))g, there is a P 2G=? such that s = f(p 1;P 1);(0 1;P)g, or there is a P and a Q each of which is in G=? such that s =f(p ;P Q);(0 ;P);(1 ;Q)g. Since R is the relation set for the structurization of a group, for each r 2 R either r = f(pe;e)g, there is an x 2 G such that r = f(p 1;x 1);(0 1;x)g , or there is an x 58 and a y in G such that r =f(p ;x y);(0 ;x);(1 ;y)g. t2 R ()9r2R such that t = r ()t = r where r =f(pe;e)g or r =f(p 1;x 1);(0 1;x)g for some x2G or r =f(p ;x y);(0 ;x);(1 ;y)g for some x;y2G ()t =f(pe; (e))g or t =f(p 1; (x 1));(0 1; (x))g for some x2G or t =f(p ; (x y));(0 ; (x));(1 ; (y))g for some x;y2G ()t =f(pe;? 1?(feg))g or t =f(p 1;? 1?(fx 1g));(0 1;? 1?(fxg))g for some x2G or t =f(p ;? 1?(fx yg));(0 ;? 1?(fxg));(1 ;? 1?(fyg))g for some x;y2G ()t =f(pe;? 1?(feg))g or t =f(p 1;(? 1?(fxg)) 1);(0 1;? 1?(fxg))g for some x2G or t =f(p ;? 1?(fxg) ? 1?(fyg));(0 ;? 1?(fxg));(1 ;? 1?(fyg))g for some x;y2G ()t =f(pe;? 1?(feg))g or t =f(p 1;P 1);(0 1;P)g for some P 2G=? or t =f(p ;P Q);(0 ;P);(1 ;Q)g for some P;Q2G=? ()t2S So R=S, and thus M=? is the structurization of (G=?; ). Suppose M=? is the structurization of a group under the operation induced by . 59 Consider ? 1?(feg). Suppose P 2G=?. There is an x2G such that P = ? 1?(x). x2? 1?(x) and x = e x2? 1?(feg) ? 1?(fxg) = ? 1?(feg) P 2G=? =)? 1?(feg) P = ? 1?(fxg) = P =)? 1?(feg) is the identity element for M=? Suppose P 2G=?. There is an x2G such that P = ? 1?(fxg). Consider ? 1?(fx 1g) e2? 1?(feg) and e = x x 1 2? 1?(fxg) ? 1?(fx 1g) = P ? 1?(fx 1g)2G=? =)P ? 1?(fx 1g) = ? 1?(feg) (elements of a partition intersect if and only if they are equal) =)P 1 = ? 1?(fx 1g) Suppose each of P and Q is in G=?. There is an x and a y in G such that P = ? 1?(fxg) and Q = ? 1?(fyg). Consider ? 1?(fx yg). x y2? 1?(fx yg) and x y2? 1?(fxg) ? 1?(fyg) = P Q =)P Q = ? 1?(fx yg) Now the main result follows. (a1;a2)2? 1? ()? 1?(fa1g) = ? 1?(fa2g) ()(? 1?(fa1g)) 1 = (? 1?(fa2g)) 1 ()? 1?(fa 11 g) = ? 1?(fa 12 g) ()(a 11 ;a 12 )2? 1? 60 (a1;b1)2? 1? and (a2;b2)2? 1? =)? 1?(fa1g) = ? 1?(fb1g) and ? 1?(fa2g) = ? 1?(fb2g) =)? 1?(fa1g) ? 1?(fa2g) = ? 1?(fb1g) ? 1?(fb2g) =)? 1?(fa1 a2g) = ? 1?(fb1 b2g) =)(a1 a2;b1 b2)2? 1? Thus for all (a1;a2) 2? 1?, (a 11 ;a 12 ) 2? 1?, and for all (a1;b1);(a2;b2) in ? 1?, (a1 a2;b1 b2)2? 1?. De nition Suppose M = (A;R) is an I-structure and B A. The I-understructure of M induced by B is the I-structure (B; ^R) where ^R is the set of relations to which a relation ^r belongs if and only if there is a relation r 2R such that ^r = r\(I B). Denote the structure (B; ^R) by MjjB. The statement that (C;T) is an I-understructure of M means C A and (C;T) is the I-understructure of M induced by C. De nition Suppose M = (A;R) is an I-structure. Suppose R is the set of relations to which a relation r belongs if and only if r I A=? and 1? r2R. Denote the I-structure (A=?; R) by M==?. Lemma 5.2.1. Suppose each of M = (A;R) and (B;S) is an I-structure, and ? : A!B is a cohomomorphism. Then ? is an I-structure coepimorphism with respect to the I-structure M==? = (A=?; R). Proof: 1. ? is continuous: Suppose r 2 R, then 1? r 2R by de nition of M==?. So ? is continuous. 2. ? is conservative: 61 Suppose r 2R. ? is conservative, so there is an s 2S such that im(s) im(?) and ? 1s = r. So s = ?r and 1? ?r = ? 1?r = ? 1s = r. Thus ?r2 R, im( ?r) im( ?), and 1? ( ?r) = r. So ? is conservative. 3. ? is a surjection with respect to A=?: By Theorem 2.4. So ? is an coepimorphism with respect to M==?. Lemma 5.2.2. Suppose each of M = (A;R) and N = (B;S) is an I-structure, and ? : A!B is an I-structure cohomomorphism. Then ? is a cohomomorphism from A to the understructure of M induced by im(?), (im(?); ^S). Proof: Suppose ^s2 ^S. Then there is an s2S such that ^s = s\(I im(?)). ? is continu- ous, so ? 1s2R. I intend to show that ? 1^s = ? 1s. Suppose (i;a) 2 ? 1^s. Then there is a b 2 im(?) such that ?(a) = b and (i;b) 2 ^s. ^s s, so (i;b)2s, and thus (i;a)2? 1s. So ? 1^s ? 1s. Suppose (i;a) 2? 1s. Then there is an b2B such that b = ?(a) 2 im(?) and (i;b) 2s. (i;b)2I im(?), so (i;b)2^s, and thus (i;a)2? 1^s. So ? 1s ? 1^s. So ? 1^s = ? 1s2R. 62 So ? is continuous between (A;R) and (im(?); ^S). Suppose r 2R. ? is conservative, so there is an s 2S such that im(s) im(?) and ? 1s = r. Since im(s) im(?), s\(I im(?)) = s, so s2 ^S. So s2 ^S, im(s) im(?), and ? 1s = r. So ? is conservative between (A;R) and (im(?); ^S). ? is both continuous and conservative between (A;R) and (im(?); ^S), so ? is an I-structure cohomomorphism between (A;R) and (im(?); ^S). Theorem 5.2. Suppose each of M = (A;R) and N = (B;S) is an I-structure, and ? : A! B is a cohomomorphism. Then M==? is isomorphic to the understructure of N induced by im(?). Proof: M==? = (A=?; R) where R is the set of relations to which a relation r belongs if and only if r I A=? and 1? r2R. The understructure of N induced by im(?) is (im(?); ^S) where ^S is the set of relations to which a relation ^s belongs if and only if there is a relation s2S such that ^s = s\(I im(?)). By Lemma 5.2.1, ? is an I-structure coepimorphism, by Lemma 5.2.2, ? is an I-structure cohomomorphism between (A;R) and (im(?); ^S), and by Lemma 2.6, 1? ? ? 1?. So by Theorem 4.2, ? 1? is a cohomomorphism. By Lemma 5.1.1, ? 1? is a bijection, so by Theorem 1.21, ? 1? is an isomorphism. So M==? is isomorphic to the understructure of N induced by im(?). 63 Corollary 5.2.1. Suppose M = (A;R) is an I-structure and ? is a cohomomorphism be- tween M and another structure. Then M==? is isomorphic to M=?. Proof: By Theorem 1.20, ? is a homomorphism. By Lemma 5.2.1, ? is a coepimorphism between M and M==? and (by Lemma 5.1.2) an epimorphism between M and M=?. Moreover, 1? ? 1? ?. So by Theorem 4.1, ? 1? is a homomorphism between M==? and M=?. ? is a surjection, so ? 1? = 1A=?, which is a bijection. So by Theorem 1.19, 1A=? is an isomorphism. So M==? = M=?. 64 Chapter 6 Second Isomorphism Theorem Lemma 6.1.1. Suppose A is a set, B A, ? is a function with domain A, B = ? 1?(B), and P 2 B=?j B. Then P\B2B=?jB. Proof: Suppose b2P\B. Since P 2 B=?j B and b2P, P = (?j B) 1((?j B)(fbg)). b2B so b2(?jB) 1((?jB)(fbg))2B=?jB. So P\B (?jB) 1((?jB)(fbg))2B=?jB. Suppose b0 2 (?jB) 1((?jB)(fbg)). Then there is a c such that (c;b0) 2 (?jB) 1 and (b;c)2?jB, so (b0;c)2?jB, so (b;c)2?, (b0;c)2? and b02B B. (b;c) 2 ? and b 2 B, so (b;c) 2 ?j B. (b0;c) 2 ? and b0 2 B, so (b0;c) 2 ?j B. So b02(?j B) 1((?j B)(fbg)) = P. So b02P\B and P\B = (?jB) 1((?jB)(fbg))2B=?jB. Lemma 6.1.2. Suppose A is a set, B A, ? is a function with domain A, B = ? 1?(B). Then the function : B=?j B !B=?jB such that for each P 2 B=?j B, (P) = P\B, is a bijection. Proof: Suppose each of P and Q is in B=?j B, and (P) = (Q). P\B = (P) = (Q) = Q\B. 65 Since each of P\B and Q\B is in B=?jB, each is nonempty. So there is a b2P\B = Q\B. b2P\B P and b2Q\B Q. P and Q intersect, and B=?j B is a partition, so P = Q. So is an injection. Suppose H2B=?jB. H is nonempty, so there is a b2H and H = (?jB) 1((?jB)(fbg)). (b;?(b))2? and b2B B, so b2(?j B) 1((?j B)(fbg))2 B=?j B. ((?j B) 1((?j B)(fbg))) = (?j B) 1((?j B)(fbg))\B. b2H = (?jB) 1((?jB)(fbg)) B and b2(?j B) 1((?j B)(fbg)), so b2(?j B) 1((?j B)(fbg))\ B = ((?j B) 1((?j B)(fbg))) Since B=?jB is a partition, and p2H2B=?jB and b2 ((?j B) 1((?j B)(fbg))) 2B=?jB, it must be the case that H = ((?j B) 1((?j B)(fbg))). So (?j B) 1((?j B)(fbg)) is an element of B=?j B such that ((?j B) 1((?j B)(fbg))) = H. So is a surjection. So is a bijection. Theorem 6.1. Suppose M = (A;R) is an I-structure, B A, ? is a function with domain A, B = ? 1?(B), Mj B=?j B = ( B=? B;S), : B=?j B!B=?jB is the function such that for each P 2 B=?j B, (P) = P\B, and N = (B=?jB;T) where T is the set of relations to 66 which a relation t belongs if and only if there is a relation s2S such that s = t. Then Mj B=?j B = N. Proof: 1. is preservative: By de nition of N, if s2S, then s2T. 2. is saturating: By de nition of N, if t2T, then there is a relation s2S such that s = t. 3. is a bijection: By Lemma 6.1.2, is a bijection. So by Theorem 1.19, is an isomorphism. So Mj B=?j B = N. 67 Chapter 7 Third Isomorphism Theorem De nition Suppose A is a set, and each of and is a function with domain A such that 1 1 . Then de ne = : A= !A= such that if P 2A= , then = (P) = 1 . Lemma 7.1.1. Suppose M = (A;R) is an I-structure, and each of and is a homomor- phism with domain A such that 1 1 . Then = is an epimorphism between M= and M= . Proof: By Lemma 5.1.2, is an epimorphism. By Lemma 5.1.2, is an epimorphism. Suppose P 2A= . 1 (P) = 1 ( (P)) = 1 (P) = (P) = 1( (P)) = = (P) So = = 1 . So by Theorem 4.1 and Lemma 4.1.1, = = 1 is an epimorphism between M= and M= . Lemma 7.1.2. Suppose A is a set, and each of and is a function with domain A such that 1 = 1 . Then A= = A= and = = 1A= . 68 Proof: A= =f 1( (fag)) a2Ag=f 1 (fag) a2Ag =f 1 (fag) a2Ag=f 1( (fag)) a2Ag= A= So A= = A= . Suppose P 2A= . = (P) = 1( (P)) = 1 (P) = 1 (P) = 1( (P)) = P So = = 1A= . Lemma 7.1.3. Suppose each of A and B is a set, and each of and : A ! B is a function with domain A such that 1 1 and is a function with domain B. Then 1 ( ) 1 . Proof: 1 1 = 11B 1 1 = ( ) 1 So 1 ( ) 1 . Lemma 7.1.4. Suppose A is a set, and each of P and Q is a partition, and : P!Q is a surjection such that for each P 2P, P (P). Suppose 1 : A!P is the function such that for each a2A, 1(a) is the part in P to which a belongs, and 2 : A!Q is the function such that for each a2A, 2(a) is the part inQto which a belongs. Then 2 = 1. Proof: Suppose a2A. a2 1(a) ( 1(a)) = 1(a) 69 So 1(a) is the part in Q to which a belongs. So 1(a) = 2(a). Since this is true for all a2A, 2 = 1. Lemma 7.1.5. Suppose each of M = (A;R), N = (B;S), and L = (P;T) is an I-structure, where P is a partition of A, and : A!B is a homomorphism, and : A= !P is an epimorphism between M= and L such that for all P 2A= , P (P). Then there is a homomorphism from M such that 1 1 and = = . Proof: De ne : A!P such that = . Since is a homomorphism, is an epimorphism. is a homomorphism. = is the composition of a homomorphism with an epimorphism, so is a homomorphism. Suppose (a1;a2)2 1 . By Lemma 2.6, 1 = 1 . (a1;a2)2 1 = 1 = 1 1A= 1 1 = ( ) 1 = 1 So 1 1 . De ne : A ! P is the function such that for each a 2 A, (a) is the part in P to which a belongs. By Lemma 7.1.4, = = . By Theorem 2.8, = . So P = A= . 70 1 = 1 1 = 1 . So = = 1 is the unique homomorphism such that ( 1 ) = = . = , so = 1 = = . So is a homomorphism from M such that 1 1 and = = . Theorem 7.1. Suppose M = (A;R) is an I-structure, and each of and is a homomor- phism with domain A such that 1 1 . Then M= . = = M= . Proof: By Lemma 7.1.1 = is an epimorphism between M= and M= . So by Theorem 5.1, M= . = = M= . 71 Chapter 8 Correspondence Theorem De nition Suppose A is a set, B is a subset of A, and ? is a function with domain A. The statement that B is ? exact means B = ? 1?(B). De nition Suppose M = (A;R) is an I-structure, N = (B;S) is an I-substructure of M, and ? is a function with domain A. The statement that N is ? exact means B = ? 1?(B). Lemma 8.1.1. Suppose A is a set, f is a function with domain A, B A such that B = f 1f(B), and b2B. Then fj 1B fjB(fbg) = f 1f(fbg). Proof: p2fj 1B fjB(fbg) ()(b;p)2fj 1B fjB ()p2B = f 1f(B) and (b;p)2f 1f ()p2f 1f(fbg) Lemma 8.1.2. Suppose A is a set, f is a function with domain A, B A such that B = f 1f(B), and b2B. Then fjB(b) = f(b). Proof: fjB(b) = fj 1B fjB(fbg) = f 1f(fbg) = f(b) Lemma 8.1.3. Suppose A is a set, f is a function with domain A, B A such that B = f 1f(B), r is a relation such that im(r) B=(?jB). Then 1fjBr = 1f r. 72 Proof: (i;b)2 1fjBr ()9P such that (i;P)2r and (P;b)2 1fjB ()(i; fjB(b))2r ()(i; f(b))2r and b2B ()9P such that (i;P)2r and (P;b)2 1f (so P 2B=?jB) ()(i;b)2 1f r So 1fjBr = 1f r. Lemma 8.1.4. Suppose M = (A;R) is an I-structure, ? is a function with domain A, and N = (B; ^R) is a ? exact I-substructure of M. Then N=(?jB) = (B=(?jB);T) is the I-substructure of M=? = (A=?;S) induced by B=(?jB). Proof: Suppose P 2B=(?jB). Then P = ?j 1B ?jB(fbg) for some b in B. P = ?j 1B ?jB(fbg) = ? 1?(fbg)2A=? So B=(?jB) A=?. Note T is the relation set to which a relation t belongs if and only if there is an ^r 2 ^R such that t = ?jB ^r. Suppose (B=(?jB); ^S) is the I-substructure of M=? induced by B=(?jB). Note ^S is the 73 relation set to which a relation ^s belongs if and only if ^s2S and im(^s) B=?B. k2T ()9r2 ^R (so im(r) B) such that k = ?r = ?jBr ()9r2R such that ?r = k and im(r) B ()9r2R such that ?r = k and im(k) B=(?jB) ( =): im(k) = im( ?jBr) = ?jB(im(r)) ?jB(B) = B=(?jB)) ((= : im(r) im( 1? ?r) = im( 1? k) = 1? (im(k)) 1? ( ?(B)) = ? 1?(B) = B) ()k2S and im(k) B=(?jB) ()k2 ^S SoT = ^S, and N=(?jB) = (B=(?jB);T) = (B=(?jB); ^S), the I-substructure of M=? induced by B=(?jB). Theorem 8.1. Suppose M = (A;R) is an I-structure, and ? is a function with domain A. Then there is a bijection between the set of ? exact I-substructures of M, and the set of I-substructures of M=?. Proof: Suppose S is the set of ? exact I-substructures of M. Suppose T is the set of I-substructures of M=?. De ne f : S!T such that for each N = (B; ^R) in S, f(N) = N=(?jB). By Lemma 8.1.4, f(N)2T. 1. f is an injection: Suppose each of N1 = (B1;R1) and N2 = (B2;R2) is in S, and f(N1) = f(N2). Note each of N1 and N2 is ? exact, so B1 = ? 1?(B1) and B2 = 74 ? 1?(B2). (B1=(?jB1); ^R1) = N1=(?jB1) = f(N1) = f(N2) = N2=(?jB2) = (B2=(?jB2); ^R2) So B1=(?jB1) = B2=(?jB2). ?(B1) = ?jB1(B1) = B1=(?jB1) =B2=(?jB2) = ?jB2(B2) = ?(B2) =) B1 = ? 1?(B1) = 1? ?(B1) = 1? ?(B2) = ? 1?(B2) = B2 R1 =fr r2R and im(r) B1g=fr r2R and im(r) B2g=R2 So N1 = (B1;R1) = (B2;R2) = N2. So f is an injection. 2. f is a surjection: Suppose (P;T) is an I-substructure of M=? = (A=?; R) (namely the I-substructure of M=? induced by P). Then P A=? = ?(A) so 1? (P) 1? ( ?(A)) = A. De ne B = 1? (P). Consider L = (B;S) where S is the relation set to which a relation s belongs if and only if s2R and im(s) B. So L is an I-substructure of M. B = 1? (P) = 1? ? 1? (P) = 1? ?( 1? (P)) = ? 1?( 1? (P)) = ? 1?(B) 75 So L is ? exact. So L2S. B=(?jB) = ?jB(B) = ?(B) = ?( 1? (P)) =P By Lemma 8.1.4, L=(?jB) is the I-substructure of M=? induced by B=(?jB) =P. So f(L) = L=(?jB) = (P;T). So f is a surjection. Thus f is a bijection. De nition Suppose M = (A;R) is an I-structure, N = (B;S) is an understructure of M, and ? is a function with domain A. The statement that N is ? exact means B = ? 1?(B). Lemma 8.2.1. Suppose each of A and B is a set, r is a relation, and B dom(r). Then r(A B) = A r(B). Proof: (a;c)2r(A B) ()9b such that (a;b)2A B and (b;c)2r ()a2A and 9b2B dom(r) such that c2r(fbg) ()(a;c)2A r(B) So r(A B) = A r(B). Lemma 8.2.2. Suppose r is a relation, I is a set such that dom(r) I, ? is a function, and B is a set such that B dom(?) and B is ? exact. Then ?(r\(I B)) = ( ?r)\( ?(I B)). 76 Proof: (i;P)2 ?(r\(I B)) ()9b such that (b;P)2 ? and (i;b)2r\(I B) ()9b such that (b;P)2 ? and (i;b)2r and (i;b)2I B ()9b1;b2 such that (b1;P)2 ?; (b2;P)2 ?; (i;b1)2r;and (i;b2)2I B ((= : b1 2? 1?(fb2g) ? 1?(B) = B =) (i;b1)2I B) ()(i;P)2 ?r and (i;P)2 ?(I B) ()(i;P)2( ?r)\( ?(I B)) So ?(r\(I B)) = ( ?r)\( ?(I B)). Lemma 8.2.3. Suppose each of f and g is a relation, I is a set such that dom(f) I and dom(g) I, ? is a function such that im(f) dom(?)=? and im(g) dom(?)=?, and B is a set such that B dom(?) and B is ? exact. Then f = g\(I B=(?jB)) if and only if 1? f = ( 1? g)\(I B). Proof: Suppose f = g\(I B=(?jB)). 1? f = 1? (g\(I B=(?jB))) = ( 1? g)\( 1? (I ?jB(B))) = ( 1? g)\( 1? (I ?(B))) = ( 1? g)\(I 1? ?(B)) = ( 1? g)\(I ? 1?(B)) = ( 1? g)\(I B) So 1? f = ( 1? g)\(I B). Suppose 1? f = ( 1? g)\(I B). f = ? 1? f = ?(( 1? g)\(I B)) = ( ? 1? g)\( ?(I B)) = g\(I ?(B)) = g\(I ?jB(B)) = g\(I B=(?jB)) 77 So f = g\(I B=(?jB)). Lemma 8.2.4. Suppose M = (A;R) is an I-structure, ? is a cohomomorphism from M, and N = (B; ^R) is a ? exact understructure of M. Then N==?jB = (B=(?jB);T) is the understructure of M==? = (A=?;S) induced by B=(?jB). Proof: Suppose P 2B=(?jB). Then P = ?j 1B ?jB(fbg) for some b in B. P = ?j 1B ?jB(fbg) = ? 1?(fbg)2A=? So B=(?jB) A=?. Note T is the relation set to which a relation t belongs if and only if t I B=(?jB) and 1?jBt2 ^R. Suppose (B=(?jB); ^S) is the understructure of M==? induced by B=(?jB). Note ^S is the relation set to which a relation ^s belongs if and only if there is an s 2 S such that ^s = s\(I B=?B). k2 ^S ()9s2S such that k = s\(I B=(?jB)) ()9s2S such that 1? s\(I B) = 1? k ()9r2R such that r\(I B) = 1? k () 1? k2 ^R and 1? k I B () 1?jBk2 ^R and k I B=(?jB) ()k2T So ^S =T, and N==?jB = (B=(?jB);T) = (B=(?jB); ^S), the understructure of M==? induced by B=(?jB). 78 Example Suppose M = (A;R) is an I-structure, ? is a function with domain A, and N = (B; ^R) is a?exact understructure ofM. ThenN==?jB = (B=(?jB);T) is not necessarily the understructure of M==? = (A=?;S) induced by B=(?jB). Proof: De ne the following: M = (fa1;a2;bg;f0g;ff(0;a1);(0;b)gg) B =fbg ? =f(a1;x);(a2;x);(b;y)g N = (fbg;f0g;ff(0;b)gg), a ? exact understructure of M Then ? =f(a1;fa1;a2g);(a2;fa1;a2g);(b;fbg)g M==? = (ffa1;a2g;fbgg;f0g;?) ?jB =f(0;b)g B=(?jB) =ffbgg N=(?jB) = (ffbgg;f0g;ff(0;fbg)gg) (ffbgg;f0g;?) is the understructure of M==? induced by B=(?jB). N==?jB6= (ffbgg;f0g;?) Theorem 8.2. Suppose M = (A;R) is an I-structure, and ? is a cohomomorphism from M. Then there is a bijection between the set of ? exact understructures of M, and the set of understructures of M==?. Proof: Suppose S is the set of ? exact understructures of M. Suppose T is the set of understructures of M==?. De ne f : S!T such that for each N = (B; ^R) in S, f(N) = N=(?jB). 79 By Lemma 8.2.4, f(N)2T. 1. f is an injection: Suppose each of N1 = (B1;R1) and N2 = (B2;R2) is in S, and f(N1) = f(N2). Note each of N1 and N2 is ? exact, so B1 = ? 1?(B1) and B2 = ? 1?(B2). (B1=(?jB1); ^R1) = N1=(?jB1) = f(N1) = f(N2) = N2=(?jB2) = (B2=(?jB2); ^R2) So B1=(?jB1) = B2=(?jB2). ?(B1) = ?jB1(B1) = B1=(?jB1) =B2=(?jB2) = ?jB2(B2) = ?(B2) =) B1 = ? 1?(B1) = 1? ?(B1) = 1? ?(B2) = ? 1?(B2) = B2 R1 =f^r 9r2R such that ^r = r\(I B1)g=f^r 9r2R such that ^r = r\(I B2)g=R2 So N1 = (B1;R1) = (B2;R2) = N2. So f is an injection. 2. f is a surjection: Suppose (P;T) is an understructure of M==? = (A=?; R) (namely, the understructure of M==? induced by P). Then P A=? = ?(A) so 1? (P) 1? ( ?(A)) = A. De ne B = 1? (P). Consider L = (B;S) where S is the relation set to which a relation s belongs if and only if there is an r2R such that s = r\(I B). So L is an understructure of 80 M. B = 1? (P) = 1? ? 1? (P) = 1? ?( 1? (P)) = ? 1?( 1? (P)) = ? 1?(B) So L is ? exact. So L2S. B=(?jB) = ?jB(B) = ?(B) = ?( 1? (P)) =P By Lemma 8.2.4, L==(?jB) is the understructure of M==? induced by B=(?jB) =P. So f(L) = L==(?jB) = (P;T). So f is a surjection. Thus f is a bijection. 81 Bibliography [1] Holmes, Randall R., Algebra I. Class Notes, Auburn University, Available at: , 2008. [2] Munkres, James R., Topology. 2nd Ed. New Jersey: Prentice-Hall, Inc., 2000. Print. [3] Burris, Stanley, and H.P. Sankappanavar, A Course in Universal Algebra. Available at: , 2012. [4] West, Douglas B., Introduction to Graph Theory. 2nd Ed. New Jersey: Prentice-Hall, Inc., 2001. Print. 82