Homework 1 (a) • Let A and B be nonempty sets, and let f:A→B be a function. • Suppose f is injective, prove that f has a left inverse • Since f is injective, ∀b∈im(f),∃!a∈A s.t. f(a)=b • Define g:B→A in the following way ○ Choose a_0∈A ○ If b∈im(f) § Choose a∈A s.t. f(a)=b § Define g(b)=a ○ If b∉im(f) § Define g(b)=a_0 • Check that g is a left inverse ○ If a∈A, (g∘f)(a)=g(f(a))=a ○ Thus, g∘f=id_A Example of The Euclidean Algorithm • Let a=97, b=20 • Use the Euclidean Algorithm to find (a,b) ○ 97=20×4+17 ○ 20=17×1+3 ○ 17=3×5+2 ○ 3=2×1+1 ○ Therefore (a,b)=1 • And then find x,y∈Z s.t. (a,b)=ax+by ○ (a,b)=1 ○ =3−2×1 ○ =3−(17−3×5)×1 ○ =3×6−17×1 ○ =(20−17×1)×6−17 ○ =20×6−17×7 ○ =20×6−(97−20×4)×7 ○ =97×(−7)+20×34 ○ We can take x=−7, y=34 Equivalence Class • Let X be a set, and let ~ be an equivalence relation on X • If x∈X, then the equivalence class represented by x is the set • [x]={x′∈X│x~x′ }⊆X Proposition 8 • Statement ○ Let X be a set with equivalence relationship ~ ○ If x,x^′∈X, then [x] and [x′] are either equal or disjoint • Proof ○ Suppose ∃y∈[x]∩[x^′ ] ○ It suffices to show if z∈X, then xz⟺x^′z ○ xz⇒x^′z § Suppose x~z § ⇒z~x (Symmetry) § ⇒z~y (Transitivity) § ⇒y~z (Symmetry) § ⇒x^′~z (Transitivity) ○ xz⇐x^′z § Suppose x′~z § ⇒z~x′ (Symmetry) § ⇒z~y (Transitivity) § ⇒y~z (Symmetry) § ⇒x~z (Transitivity) Integers Modulo n • Let n∈Z( 0) • The relation on Z given by a~b⟺n|(a−b) is an equivalence relation • The set of equivalence classes under ~ is denoted as Z\nZ • We call this set integers modulo n (or integers mod n) • We can check that there are n elements in Z\nZ • Use a ̅ to denote the equivalence class in Z\nZ • Then Z\nZ={0 ̅,1 ̅,2 ̅,…,(n−1) ̅ } Group • Definition ○ If G is a set equipped with a binary operation § G×G→G § (g,h↦g⋅h ○ that satisfy § Associativity: ∀g,h,k∈G, g⋅(hk)=(g⋅h⋅k § Identity: ∃1∈G s.t. ∀g∈G,1⋅g=g⋅1=g § Inverses: ∀g∈G, ∃g^(−1)∈G s.t. gg(−1)=g(−1) g=1 ○ Then we say G is a group under this operation • Z,Q,R,ℂ are groups with operation + ○ If a,b∈Z, then a+b∈Z (Similarly for Q,R,ℂ) ○ + is certainly associative in all 4 sets ○ 0 is the identity in each case ○ If a∈Z (or QRℂ), then the inverse of a is −a
