CHAPTER 0 JOSEPH A. GALLIAN Flashcards
Well ordering property
Every nonempty subset of positive integers contains a smallest number
Division
t|s (t is a divisor of an integer s)
read t divides s st s=tu
Division algorithm
Let a and b be integer with b>0. Then there exists unique integers q and r with the property that a=bq+r, where 0<r<b
proof: Consider set S={a-bk|k is an integer and a-bk>0}
If i 0 ∈S, then b divides a and we get q=a/b and r=0
If 0∉S and since S is not empty [a>0, a-b.0∈S; if a<0, a-b.2a=a(1-2b)]
We apply Well-order property, S has a smallest number say r=a-bq
Then a=bq+r and r>0
GCD
If GCD(a,b)=1 then a aand b are relative primes
GCD as linear combination
GCD(a,b)=as+bt
Euclid’s lemma
p|ab implies p|a or p|b only if p is prime
LCM
Modular arithmetic
a=qn+r (q is quotient, r is the remainder, n is a number a div by)
a mod n=r
Complex number Property
Complex number Property
First Principle of Mathematical Induction
Let S be a set of integers containing a. Suppose S has the property that whenever some integer n ≥ a belongs to S, then the integer n + 1 also belongs to S. Then, S contains every integer greater than or equal to a.
Second Principle of Mathematical Induction
Let S be a set of integers containing a. Suppose S has the property that n belongs to S whenever every integer less than n and greater than or equal to a belongs to S. Then, S contains every integer greater than or equal to a.
Equivalence relation
- (a,a) ∈ R for all a∈S
- (a,b)∈R imples (b,a)∈R
- (a,b)∈R and (b,c)∈R imply (a,c)∈R
EXAMPLE 15 Let S be the set of all triangles in a plane. If a, b ∈ S, define a ~ b if a and b are similar—that is, if a and b have corresponding angles that are the same. Then ~ is an equivalence relation on S.
EXAMPLE 16 Let S be the set of all polynomials with real coefficients. If f, g ∈ S, define f ~ g if f’ = g’, where f’ is the derivative of f. Then ~ is an equivalence relation on S. Since two polynomials with equal derivatives differ by a constant, we see that for any f in S, [f] = {f + c | c is real}.
EXAMPLE 17 Let S be the set of integers and let n be a positive integer. If a, b ∈ S, define a ≡ b if a mod n = b mod n (that is, if a - b is divisible by n). Then ≡ is an equivalence relation on S and [a] = {a + kn | k ∈ S}. Since this particular relation is important in abstract algebra, we will take the trouble to verify that it is indeed an equivalence relation. Certainly, a - a is divisible by n, so that a ≡ a for all a in S. Next, assume that a ≡ b, say, a - b = rn. Then, b - a = (−r)n, and therefore b ≡ a. Finally, assume that a ≡ b and b ≡ c, say, a - b = rn and b - c = sn. Then, we have a - c = (a - b) + (b - c) = rn + sn = (r + s)n, so that a ≡ c.
EXAMPLE 18 Let ≡ be as in Example 17 and let n = 7. Then we have 16 ≡ 2; 9 ≡ −5; and 24 ≡ 3. Also, [1] = {. . . , −20, −13, −6, 1, 8, 15, . . .} and [4] = {. . . , −17, −10, −3, 4, 11, 18, . . .}.
Partition
The equivalence classes partition
The equivalence classes of an equivalence relation on a set S form a partition of S.
Conversely, if you have a partition of S, you can define an equivalence relation where two elements are related if they’re in the same part.
The equivalence classes partition proof
PROOF Let ~ be an equivalence relation on a set S. For any a ∈ S, the reflexive property shows that a ∈ [a]. So, [a] is nonempty and the union of all equivalence classes is S. Now, suppose that [a] and [b] are distinct equivalence classes. We must show that [a] ∩ [b] = ∅. On the contrary, assume c ∈ [a] ∩ [b]. We will show that [a] ⊆ [b]. To this end, let x ∈ [a]. We then have c ~ a, c ~ b, and x ~ a. By the symmetric property, we also have a ~ c. Thus, by transitivity, x ~ c, and by transitivity again, x ~ b. This proves [a] ⊆ [b]. Analogously, [b] ⊆ [a]. Thus, [a] = [b], in contradiction to our assumption that [a] and [b] are distinct equivalence classes.
Mapping
φ: A →B
Composite of functions
Let φ: A → B and ψ: B → C. The composition ψφ is the mapping from A to C defined by (ψφ)(a) = ψ(φ(a)) for all a in A.
One to one
A function φ from a set A is called one-to-one if for every a₁, a₂∈A, φ(a₁) = φ(a₂) implies a₁ = a₂.
Alternatively, φ is one-to-one if a₁ ≠ a₂ implies φ(a₁) ≠ φ(a₂). That is, different elements of A map to different elements of B.
Onto Functions
A function φ from a set A to a set B is said to be onto B if each element of B is the image of at least one element of A. In symbols, φ: A → B is onto if for each b in B there is at least one a in A such that φ(a) = b. See Figure 0.
