Definitions pt 2

Question 1

MI1 formal logic

Answer 1

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

Question 2

What is the structure for mathematical induction?

Answer 2

P(n) is a property.
1. Show P(1) is true
2. Assume P(k) is true for some k∈ℤ+
3. Show P(k+1) is true
Conclusion:
P(n) is true for ∀n∈ℤ+

Question 3

Define: least element

Answer 3

A set S⊂ℝ has a least element if

∃ x∈S ∋ x ≤ y for ∀y∈S

Question 4

What is the formal logic for a direct proof?

Answer 4

P => Q
-or-
P₁ ∧ P₂ ∧ … ∧ Pk => Q

Question 5

What is the formal logic for contraposition?

Answer 5

~Q => ~P

if ~Q=true, show ~P=true

Question 6

What is the formal logic for a contradiction?

Answer 6

P ∧ ~Q => something false

Question 7

Define: well-ordered

Answer 7

A set S is well-ordered if
∀ Y⊆S, Y has a least element, Y≠∅.
(It’s well-ordered if ∀ subsets have a least element, but don’t worry about the empty set)

Question 8

Is ℤ+ well-ordered?

Answer 8

Yes. Any subset will have a least element.

Question 9

Is ℤ well-ordered?

Answer 9

No. It extends to -∞ and therefore does not have a least element.

Question 10

Is ℕ well-ordered?

Answer 10

Yes. Any subset will have a least element.

Question 11

State the FTA

Answer 11

The fundamental theorem of arithmetic:

All ℤ+ > 1 are either prime or a product of primes with unique factorization, up to the order of the factors.

Question 12

State Euclid’s lemma

Answer 12

Let p be prime and p|ab.

Then p|a or p|b or both.

Question 13

State the Binomial Thm

Answer 13

Let a,b∈ℝ and n∈ℤ+. Then,
(a+b)^n =
∑(k=0, n) [n choose k] a^(n-k) ∗ b^k

Question 14

Define: [n choose k]

Answer 14

[n choose k] =
n!
(n-k)! k!

Question 15

[n choose k] +

[n choose k-1] = ?

Answer 15

n+1 / k

Question 16

State Fermat’s Little Thm

Answer 16

Let p be prime. Then for ∀a∈ℤ+
a^p ≡ a mod p
and, in particular, if gcd(a,p) = 1, then
a^(p-1) ≡ 1 mod p

Question 17

What does Fermat’s Little Thm imply about 2^p?

Answer 17

p | 2^p - 2

Question 18

Define the phi function.

Answer 18

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

Question 19

If p is prime, Φ(p) =

Answer 19

Φ(p) = p-1

Question 20

If p ≠ q are primes, Φ(pq) =

Answer 20

Φ(pq) = Φ(p) ∗ Φ(q)

Question 21

Let p be prime, then Φ(p^n) =

Answer 21

Φ(p^n) = p^(n-1) ∗ Φ(p)

Question 22

State Euler’s Thm

Answer 22

Let gcd(a,n) = 1. Then, 
a^Φ(n) ≡ 1 mod n

Question 23

Rearrange p | 2^p - 2 to be Fermat’s Little Thm

Answer 23

p | 2^p - 2
=> 2^p ≡ 2 mod p
=> 2^(p-1) ≡ 1 mod p

Question 24

State inclusion/exclusion for two sets A, B

Answer 24

|A∪B| = |A| + |B| - |A∩B|

Question 25

Define: gcd

Answer 25

``` Let a,b∈ℤ. Then the gcd(a,b) is some k∈ℤ+ ∋ 1. k | a 2. k | b 3. if k' | a and k' | b, then k' | k ```

Question 26

State the division algorithm.

Answer 26

Let a,b∈ℤ+ with a ≥ b. Then ∃ q,r∈ℤ ∋ a = bq + r w/ 0 ≤ r ≤ b

Question 27

Define a relation.

Answer 27

Let A,B be sets. | A relation R from A to B is a subset of A×B.

Question 28

Define R^(-1)

Answer 28

A relation R^(-1) is an inverse relation to R if | R^(-1) = { (b,a) | (a,b) ∈ R }

Question 29

Define reflexive

Answer 29

A relation R is reflexive if for ∀a∈A, (a,a)∈R

Question 30

Define symmetry

Answer 30

A relation R is symmetric if whenever (a,b)∈R, we have (b,a)∈R

Question 31

Define transitive

Answer 31

A relation R is transitive if (a,b)∈R and (b,c)∈R implies (a,c)∈R

Question 32

Define an equivalence relation

Answer 32

A relation R on A that is reflexive, symmetric, and transitive.

Question 33

Define an equivalence class.

Answer 33

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

Question 34

Define a partition.

Answer 34

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 35

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

Answer 35

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

Question 36

State the theorem for equivalence classes imply a partition

Answer 36

P = { [a] | a∈A}

Question 37

What is Φpq(n) where p,q are primes and pq|n?

Answer 37

Φpq(n) = (1 - 1/p)(1 - 1/q)