Home > Preview
The flashcards below were created by user
nisab44
on FreezingBlue Flashcards.

Inductive
A set S (subset of) natural numbers is called INDUCTIVE if 1. there is a minimal k (element of) natural numbers s.t. k (element of) S. 2. If n (element of) S, then n+1 (element of) S.

Greatest Common Divisor
Let a,b (element of) natural numbers. The GREATEST COMMON DIVISOR, denoted gcd(a,b) is the unique natural number d s.t. 1. d (divides) a and d (divides) b. 2. If e (divides) a and e (divides) b => e (divides) d

Relatively Prime
If gcd(a,b) = 1, then a and b are said to be RELATIVELY PRIME.

Least Common Multiple
The LEAST COMMON MULTIPLE of a,b denoted lcm(a,b) is the unique natural number s.t. 1. a (divides) lcm(a,b) and b (divides) lcm(a,b). 2. If M is any natural number s.t. a (divides) M and b (divides) M => lcm(a,b) (divides) M.

Explain direct proofs
 Say P => Q
 1. BackwardForward method: consider what will make Q to be true. What has to be established to show Q?
 2. Backward: Assume Q is true.
 3. Forward: Assume P is true.
 4. Hopefully, the logically chains meet

Explain proof by contrapositive
 Given P => Q, prove ~Q => ~P instead
 1. Indirectly proves P => Q
 2. ~Q => ~P is proven directly
 3. Replaces one conditional with another

Explain proof by contradiction
 Want to prove a proposition that is always false.
 Assume P (and) ~Q => derive R (and) ~R
 P=>P2=>P3=>...=>R
 ~Q=>Q1=>Q2=>...~R
 Two things to word with: P and ~Q

Explain proof by induction
 Given a propositional function
 P_{n} with domain natural numbers,
 1. Verify base case: P(1) must be true
 2. Assume P(n) is true.
 Derive P(n+1) is true

How to prove an "EitherOr" statement

How to prove an object is unique
 1. Start with two of them
 2. Either derive a contradiction or show two objects are equal

How to prove a set is empty

Helpful hints for: If X is a set with [X] = n, then [P] = 2^{n}
 Assume Induction Hypothesis
 Let [X] = n+1 and X={x_{1},x_{2},...x_{n}}U{x_{n+1}}
 Let Y = {x_{1},x_{2},...x_{n}}
 By IH, [P(Y)] = 2^{n}

Fundamental Theorem of Arithmetic
Let n (element of) natural numbers..., then n is a product of prime numbers. There exist primes p_{1}...p_{m} and exponents e_{1}...e_{m} s.t. n=_{}p1^{e1}p2^{e2}...pm^{em}

Euclid's Lemma: if p is a prime and p (divides) ab, then p (divides) a or p (divides) b
 If P then Q or R. P => Q v R
 Assume ~Q. Q is false; prove P => R
 Assume P (~divides) a
 gcd(p,a)=1 => there exist integers s,t (element of) integers s.t. 1=as+pt
 Multiply equation by b...

There are infinitely many prime numbers
 Assume otherwise
 Let N equal p1, p2,...pn+1
 If N has a prime factor N is prime itself...but it's not
 There's at least one pi s.t. pi (divides) N
 End up with pi (divides) 1 => contradiction 1 isn't divisible by primes

Prove Sqrt(2) is irrational
 Assume it is rational
 Sqrt(2) = a/b, assuming that a and b have no common factors other than 1
 Square both sides
 2b^{2}=a^{2}
 Even, odd, both have factors of 2 => contradiction

