Chapter 6 Flashcards Preview

MAT 1362 > Chapter 6 > Flashcards

Flashcards in Chapter 6 Deck (26)
Loading flashcards...
1

relation [definition / notation]

A relation on a set A is a subset of A × A.

If R ⊆ A × A is a relation on A, we usually write xRy to indicate that (x, y) ∈ R and we say that x is related to y by the relation R.

So xRy ⇐⇒ (x, y) ∈ R.

We often use other symbols instead of R, such as ∼, ≈, ≡, , ≥, ≺, ≻, etc.

2

four examples of relations [info]

  1. equality (=)
  2. less than (
  3. less than or equal to (≤)
  4.  divides (i.e. a divides b).

3

3 properties of equivalence relations [definition]

A relation ∼ on a set A is an equivalence relation if:

  1. a ∼ a for all a ∈ A (reflexivity)
     
  2. if a ∼ b, then b ∼ a (symmetry)
     
  3. if  f a ∼ b and b ∼ c, then a ∼ c (transitivity)

4

If ∼ is an equivalence relation on A, then the equivalence class of a ∈ A is... [definition / notation]

[a] := {b ∈ A : b ∼ a}

 (note: sometimes, when we wish to emphasize the particular equivalence relation (for instance, when we are working with more than one), we write [a]∼ instead of [a])

5

Suppose ∼ is an equivalence relation on a set A, and a, b ∈ A; then...

  1. a ∈ ...
     
  2.  a ∼ b ⇐⇒ ...

[proposition]

  1. a ∈ [a]
     
  2.  a ∼ b ⇐⇒ [a] = [b]

6

representative of equivalence class
[definition / notation / explanation]

  • we say that a is a representative of the equivalence class [a]
     
  • representatives of a given equivalence class are not unique in general
     
  • b is a representative of the equivalence class [a] if and only if a ∼ b (which is equivalent to b ∈ [a])

7

Suppose ∼ is an equivalence relation on a set A. Then, for all a, b ∈ A, we have...

[a] = ?

or

[a]∩[b] = ?

[proposition]

[a] = [b]

or

[a]∩[b] = ∅

8

partition [definition]

A partition of a set A is a set Π, whose elements are nonempty subsets of A such that...

  • P1, P2 ∈ Π, P1 ≠ P2 ⇒ P1 ∩ P2 = ∅
     
  • every a ∈ A belongs to some P ∈ Π

9

Suppose ∼ is an equivalence relation on A. Then the set Π of equivalence classes of ∼ is a _________ of A.

Suppose Π is a _________ of A. Then the relation ∼ defined by
a ∼ b ⇔ a and b lie in the same ____________.

[proposition]

Suppose ∼ is an equivalence relation on A. Then the set Π of equivalence classes of ∼ is a partition of A.

Suppose Π is a partition of A. Then the relation ∼ defined by
a ∼ b ⇔ a and b lie in the same element of Π .

10

absolute value of an interger [definition / notation]

The absolute value of an integer x is defined to be

 

11

the division algorithm [theorem]

Suppose n ∈ N. For every m ∈ Z, there exist a unique q, r ∈ Z such that...

  • m = qn + r
     
  • 0 ≤ r ≤ n − 1

The integer q is called the quotient and r is called the remainder upon division of m by n.

12

modulus [definition / notation / explanation]

For a fixed n ∈ N, we define a relation ≡ on Z by

x ≡ y ⇔ x − y is divisible by n .

The natural number n is called the modulus.

(note: when we wish to make the modulus explicit, we write
x ≡ y mod n)

 

13

If x ≡ y mod n, we say that x and y are __________ modulo n or _________ modulo n. [terminology]

If x ≡ y mod n, we say that x and y are equivalent modulo n or congruent modulo n.

(or sometimes simply equivalent/congruent mod n)

14

fix a modulus n ∈ N (2 points) [proposition]

  1. equivalence modulo n (i.e. ≡) is an equivalence relation
     
  2. the equivalence relation ≡ has exactly n distinct equivalence classes, namely [0], [1], . . . , [n − 1]

15

Fix a modulus n ∈ N. If a ≡ a′ and b ≡ b′ , then

a + b ≡ ?

and 

ab ≡ ?

 

a + b ≡ a′ + b'

ab ≡ a'b'

 

16

addition ⊕ and multiplication ⊙ on Zn are defined as...
[definition / formula]

[a] ⊕ [b] = [a + b]

[a] ⊙ [b] = [ab]

17

Fix an integer n ≥ 2. Addition and multiplication in Zn are ___________, ___________, and ____________. Also, the set Zn has a ________identity (0), a ______________ identity(1) and ________ inverses (the additive inverse of (a) being ____.) [completion]

Fix an integer n ≥ 2. Addition and multiplication in Zn are commutative, associative, and distributive. Also, the set Zn has an additive identity [0], a multiplicative identity [1], and additive inverses (the additive inverse of [a] being [−a]). In other words, Axioms 1.1–1.4 hold with Z replaced everywhere by Zn.

18

An integer n ≥ 2 is prime if it is divisible only by __ and __. [definition]

An integer n ≥ 2 is prime if it is divisible only by ±1 and ±n.

19

If an integer n ≥ 2 is not prime, it is _________. [definition]

If an integer n ≥ 2 is not prime, it is composite.

20

explanation of factors / factorization [definition]

If n = q1q2 · · · qk for some q1, q2, . . . , qk ∈ Z, then

the q1, q2, . . . , qk are called factors of n,

and the expression n = q1q2 · · · qk is called a factorization of n.

21

Suppose m, n ∈ Z; then

gcd(m,n) divides both _ and _ .

[proposition]

gcd(m,n) divides both m and n

22

Suppose m, n ∈ Z; 

then if m and n are not ____ zero,

gcd(m,n) > _ .

[proposition]

Suppose m, n ∈ Z; 

then if m and n are not both zero,

gcd(m,n) > 0.

23

Suppose m, n ∈ Z; then

every interger that divides both m and n also divides ________ .

[proposition]

Suppose m, n ∈ Z; then

every interger that divides both m and n also divides gcd(m, n) .

[proposition]

24

for all k, m, n ∈ Z, we have

gcd(km, kn) = ?

[proposition]

for all k, m, n ∈ Z, we have

gcd(km, kn) = |k|gcd(m,n)

 

25

Euclid's lemma [proposition]

Suppose p is a prime and m, n ∈ N.

If p|mn, then p|m or p|n

26

Suppose k ∈ N, p is a prime, and m1, . . . , mk ∈ N.

If p|m1m· · · mk,

then ___ for some _____ .

[corollary]

Suppose k ∈ N, p is a prime, and m1, . . . , mk ∈ N.

If p|m1m2 · · · mk,

then p|mi for some 1 ≤ i ≤ k.