Difficult Definitions

Question 1

Name the three things we NTS to prove that equivalence classes imply a partition.

Answer 1

1. EC’s are non-empty
2. ∀x∈A is in some EC
3. x is not in two distinct EC’s

Question 2

State the theorem for equivalence classes imply a partition

Answer 2

P = { [a] | a∈A}

Question 3

Define an equivalence class.

Answer 3

For an ER, an equivalence class is a set 
[a] = { x∈A | xRa }

Question 4

MI1 formal logic

Answer 4

P(1) ∧ ∀k [P(k) => P(k+1)] => P(n)

Question 5

Define a partition.

Answer 5

A partition P of a set S is a collection of non-empty subsets of S ∋

1. A,B∈P => A∩B = ∅
2. If x∈S, then ∃ A∈P ∋ x∈S

Question 6

Define the phi function.

Answer 6

Φ(n) = | { x∈ℤ+ | gcd(x,n) = 1, 1 ≤ x ≤ n } |