Definitions pt 2 Flashcards
MI1 formal logic
P(1) ∧ ∀k [P(k) => P(k+1)] => P(n)
What is the structure for mathematical induction?
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∈ℤ+
Define: least element
A set S⊂ℝ has a least element if
∃ x∈S ∋ x ≤ y for ∀y∈S
What is the formal logic for a direct proof?
P => Q
-or-
P₁ ∧ P₂ ∧ … ∧ Pk => Q
What is the formal logic for contraposition?
~Q => ~P
if ~Q=true, show ~P=true
What is the formal logic for a contradiction?
P ∧ ~Q => something false
Define: well-ordered
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)
Is ℤ+ well-ordered?
Yes. Any subset will have a least element.
Is ℤ well-ordered?
No. It extends to -∞ and therefore does not have a least element.
Is ℕ well-ordered?
Yes. Any subset will have a least element.
State the FTA
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.
State Euclid’s lemma
Let p be prime and p|ab.
Then p|a or p|b or both.
State the Binomial Thm
Let a,b∈ℝ and n∈ℤ+. Then,
(a+b)^n =
∑(k=0, n) [n choose k] a^(n-k) ∗ b^k
Define: [n choose k]
[n choose k] =
n!
(n-k)! k!
[n choose k] +
[n choose k-1] = ?
n+1 / k
State Fermat’s Little Thm
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
What does Fermat’s Little Thm imply about 2^p?
p | 2^p - 2
Define the phi function.
Φ(n) = | { x∈ℤ+ | gcd(x,n) = 1, 1 ≤ x ≤ n } |
If p is prime, Φ(p) =
Φ(p) = p-1
If p ≠ q are primes, Φ(pq) =
Φ(pq) = Φ(p) ∗ Φ(q)
Let p be prime, then Φ(p^n) =
Φ(p^n) = p^(n-1) ∗ Φ(p)
State Euler’s Thm
Let gcd(a,n) = 1. Then, a^Φ(n) ≡ 1 mod n
Rearrange p | 2^p - 2 to be Fermat’s Little Thm
p | 2^p - 2
=> 2^p ≡ 2 mod p
=> 2^(p-1) ≡ 1 mod p
State inclusion/exclusion for two sets A, B
|A∪B| = |A| + |B| - |A∩B|
Define: gcd
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
State the division algorithm.
Let a,b∈ℤ+ with a ≥ b.
Then ∃ q,r∈ℤ ∋ a = bq + r
w/ 0 ≤ r ≤ b
Define a relation.
Let A,B be sets.
A relation R from A to B is a subset of A×B.
Define R^(-1)
A relation R^(-1) is an inverse relation to R if
R^(-1) = { (b,a) | (a,b) ∈ R }
Define reflexive
A relation R is reflexive if for ∀a∈A, (a,a)∈R
Define symmetry
A relation R is symmetric if whenever (a,b)∈R, we have (b,a)∈R
Define transitive
A relation R is transitive if (a,b)∈R and (b,c)∈R implies (a,c)∈R
Define an equivalence relation
A relation R on A that is reflexive, symmetric, and transitive.
Define an equivalence class.
For an ER, an equivalence class is a set
[a] = { x∈A | xRa }Define a partition.
A partition P of a set S is a collection of non-empty subsets of S ∋
- A,B∈P => A∩B = ∅
- If x∈S, then ∃ A∈P ∋ x∈S
Name the three things we NTS to prove that equivalence classes imply a partition.
- EC’s are non-empty
- ∀x∈A is in some EC
- x is not in two distinct EC’s
State the theorem for equivalence classes imply a partition
P = { [a] | a∈A}
What is Φpq(n) where p,q are primes and pq|n?
Φpq(n) = (1 - 1/p)(1 - 1/q)
