Introduction • Course Plan ○ Frist 2/3 - Groups (“Sets with a multiplication rule”) ○ Last 1/3 - Rings (“Set with notions of addition and multiplication”) • Office Hours ○ Tuesdays 2:30 p.m. - 4:00 p.m. ○ Wednesdays 12:30 p.m. - 2:00 p.m. Notations • “□(≔)” means “equals, by definition” • Z≔{0,±1,±2,±3,…} the set of integers • Q≔{a/b│a,b∈Zb≠0} • R≔ the set of all real numbers • ℂ≔{a+bi│a,b∈Ri^2=−1} • Z(≥0)≔{a∈Za≥0} • S∖{x}≔{s∈S│s≠x} • Denote a function f from a set A to set B by f:A→B • Denote the image of f by im(f)≔{b∈B│∃a∈A s.t. f(a)=b} Injective, Surjective and Bijective • Definition ○ Let f:A→B be a function, then ○ f is injective if ∀a,a^′∈A, a≠a^′, f(a)≠f(a′) ○ f is surjective if ∀b∈B, ∃a∈A s.t. f(a)=b (i.e. im(f)=B) ○ f is bijective if f is both injective and surjective. • Example 1 ○ For f:Z→Z, f(a)=2a ○ f is injective § Let a,a^′∈Z § Suppose f(a)=f(a′) § ⇒2a=2a^′ § ⇒2a−2a^′=0 § ⇒2(a−a^′ )=0 § ⇒a−a^′=0 § ⇒a=a^′ § Therefore f is injective ○ f is not surjective § Because the image of f does not contain any odd integers § im(f)={even integer} • Example 2 ○ Let f:Q→Q is given by f(a)=2a ○ f is injective § By the same proof as before ○ f is surjective § Let b∈Q, then b/2∈Q § And f(b/2)=2(b/2)=b∈Q § Therefore f is surjective ○ f is bijective § Since f is both injective and surjective. Divides • Definition ○ If x,y∈Z, and x≠0 ○ We say x divides y and write x|y, if ∃q∈Z s.t. xq=y • Examples ○ ∀x∈Z\{0}, x|0, since x⋅0=0 ○ ∀x∈Z, 1|x, since 1⋅x=x ○ ∀x∈Z, −1|x, since (−1)⋅(−x)=x Equivalence Relations • Product of Two Sets ○ If A and B are sets, then the product of A and B is ○ A×B≔{(a,b)│a∈A, b∈B} • Relations ○ A relation on a set A is a subset R of A×A ○ We write a~a′ if (a,a^′ )∈R • Equivalence Relations ○ A equivalence relation is a relation R on A such that R is ○ Reflexive § if a∈A, a~a § i.e. (a,a)∈R ○ Symmetric § if a~a′, then a^′~a § i.e. (a,a′)∈R⇒(a′,a)∈R ○ Transitive § if a~a^′, a′~a′′, then a~a′′ § i.e. if (a,a′)∈R and (a′,a′′ )∈R, then (a,a^′′ )∈R • Example 1 ○ Let R be a relation on set A such that R≔{(a,a)│a∈A} ○ Then R is an equivalence relation (a~a′⟺a=a′) ○ Reflexive § If a∈A,(a,a)∈R ○ Symmetric § If a~a′,a=a^′ § Thus a^′=a, hence a^′~a ○ Transitive § If aa′,a′a′′ then a=a′ and a=a′′ § Thus a=a^′′, hence a~a^′′ • Example 2 ○ Let n be a positive integer ○ Then R≔{(a,b)∈ZZn|(a−b) } is an equivalence relation ○ Reflexive § Recall that n|0 § Thus, n|(a−a), ∀a∈Z § It follows that a~a,∀a∈Z ○ Symmetric § Let a,b∈Z, and suppose n|(a−b) (i.e. a~b) § Choose q∈Z s.t. nq=a−b § Then n(−q)=−(a−b)=b−a § Thus, n|(b−a), and so b~a ○ Transitive § Suppose a,b,c∈Z, and we have a~b, b~c § Then n|(a−b) and n|(b−c) § Choose q,q^′∈Z s.t. nq=a−b, nq^′=b−c § Then n(q+q^′ )=(a−b)+(b−c)=a−c § Thus, n|(a−c), and so a~c
