Abstract Algebra 1

Let A and B be sets. The set A x B = {(a,b) | a A and b B} is the cartesian product of A and B.

A function f mapping X onto Y is a relation between X and Y with the property that each x X appears as the first member of exactly one ordered pair (x,y) in f. Such a function is also called a map of mapping of X into Y. We write f:X->Y and express (x,y) f by f(x)=y. The domain of f is the set X and the set Y is the codomain of f. The range of f is f[X] = {f(x) | x X}.

A function f:X->Y is one to one if f(x1)=f(x2) only when x1=x2. The function f is onto Y if the range of f is Y. The function f is bijective if it is one to one and onto.

Two sets X and Y have the same cardinality if there exists a one-to-one function mapping X onto Y, that is, if there exists a one-to-one correspondence between X and Y.

For each n N, let An be the set given by An = {p/q | where p,q N are in lowest terms with p + q = n}. Each An is finite and every rational number appears in exactly one of these sets. A countable union of finite sets is countable.

A partition of a set S is a collection of nonempty subsets of S such that every element of S is in exactly one of the subsets. The subsets are the cells of the partition.

• An equivalence relation R on a set S is one that satisfies these three properties for all x, y, z S.
• 1. (Reflexive) xRx.
• 2. (Symmetric) If xRy, then yRx.
• 3. (Transitive) If xRy and yRz, then xRz.

Let n Z+. The equivalence relation on Z+ corresponding to the partition of Z+ into residue classes modulo n is congruence modulo n. It is denoted a =n b or a = b (mod 4), read "a is congruent to b modulo n."

We must show that the different cells = {x S | x ~ a} for a S do give a partition of S, so that every element of S is in some cell and so that if a , then = . Let a S. Then a by the reflexive condition, so a is in at least one cell. Suppose now that a were in a cell also. We need to show that = as sets; this will show that a cannot be in more than one cell. There is a standard way to show that two sets are the same: Show that each set is a subset of the other. We show that . Let x . Then x ~ a. But a , so a ~ b. Then, by the transitive condition, x ~ b, so x . Thus . Now we show that . Let y B. Then y ~ b. But a , so a ~ b and by symmetry b ~ a. Then by transitivity y ~ a, so y . Hence also, so = and our proof is complete.