Proofs Flashcards
The inite sequence {Fn}, n ∈ Z, n ≥ 0, defined recursively by F0 = 1, F1 = 1, and Fn = Fn−1 +Fn−2 for n ≥ 2
is called the
Fibonacci sequence.
A predicate P(n) defined for n ∈ Z+ is proven true for all integers n ≥ n0 using the Principle of Strong
Mathematical Induction by doing the following:
- Prove P(n0) is true.
- Assume there exists some integer k ≥ n0 such that P(j) is true for every integer j such that n0 ≤ j ≤ k.
- Demonstrate explicitly that P(k + 1) is true.
- Conclude that P(n) is true for all integers n ≥ n0.
Let x, y ∈ R and n ∈ Z+. Then,
(x + y)^n = the sum of n
i=0 (n,i)
x^(n−i) y^i
.
The Binomial Theorem
Every nonempty subset of positive integers has a least element.
Well-Ordering Principle.
Let a, b ∈ Z with b > 0. Then there exist unique integers q and r, with
0 ≤ r < b such that a = bq + r.
Quotient-Remainder Theorem
Let a, b ∈ Z, at least one of which is nonzero. An integer d is called a _______ of a and b if d|a and
d|b.
common divisor
A common divisior d or a and b is called the____ of a and b if d ≥ c for any other
common divisor c of a and b.
Greatest common divisors
If gcd(a, b) = 1, then a and b are
Relatively prime
Let a, b ∈ Z, at least one of which is nonzero. If d = gcd(a, b), then there exist x, y ∈ Z so
that d = ax + by
Theorem 4.24.
Two integers a and b, with at least one nonzero, satisfy gcd(a, b) = 1 if and only if there
exist x, y ∈ Z so that ax + by = 1.
Corollary 4.25
If p is prime and p|ab for a, b ∈ Z, then p|a or p|b.
Euclid’s Lemma
Every positive integer greater than 1 has a unique canonical form
prime factorization.
Fundamental Theorem of Arithmetic
Let A and B be sets. A ____ R from A to B is a subset of A × B. We say a ∈ A is related to b ∈ B if
(a, b) ∈ R.
Relation
Let R be a relation from A to B. The____ of R is (. )(R) = {a ∈ A|(a, b) ∈ R for some b ∈ B}. The ____ of R is Dom(R) = of R is Ran(R) = {b ∈ B|(a, b) ∈ R for some a ∈ A}
Domain, Range
Let R be a relation from A to B. The_____to R, denoted by R−1, is the relation from B to A
defined by (b, a) ∈ R−1 if and only if (a, b) ∈ R.
inverse relation
A relation R defined on a set A called an equivalence relation if and only if it satisfies all three of the
following properties:
- R is reflexive: for every a ∈ A, (a, a) ∈ R.
- R is symmetric: for every a, b ∈ A, if (a, b) ∈ R, then (b, a) ∈ R.
- R is transitive: for every a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
Let R be an equivalence relation defined on a set A. Then, for a ∈ A, the equivalence class of a determined
by R is the set___
[a] = {x ∈ A|(a, x) ∈ R}
The set of equivalence classes of an equivalence relation R on a nonempty set A partitions A.
Theorem 5.16
For m ∈ Z+, we say that a, b ∈ Z are
denoted a ≡m b (or a ≡ b mod m), if m|(a − b)
Theorem 5.29. Suppose a, b, m ∈ Z with m > 0. The following statements are equivalent:
- a ≡m b.
- a and b have the same remainder when divided by m.
- a = b + km for some k ∈ Z.
For any m ∈ Z+, the relation ≡m is an equivalence relation on Z.
Corollary 5.31
Theorem 5.34. Let m ∈ Z+, and assume ai ≡m bi for i = 1, 2. Then,
- a1 + a2 ≡m b1 + b2
- a1a2 ≡m b1b2, and 3. an1 ≡ mbn1 for all n ∈ Z, n ≥ 2
A _____from a set X to a set Y is a relation from X to Y so that for every x ∈ X, there exists a unique
y ∈ Y such that (x, y) ∈ f.
Function f
The set X is called the
domain of f
The set Y is called the
Codomain
The range of f is the set Ran(f)=
{f(x)|x ∈ X}
Let f : X → Y be a function and A ⊆ X. The image of A under f is the set
f(A) = {b ∈ Y |∃a ∈ A such that f(a) = b} = {f(a)|a ∈ A}.
Let f : X → Y be a function and B ⊆ Y . The inverse image of B under f is the set
f −1(B) = {a ∈ X|f(a) ∈ B}.
A function f : X → Y is ____ if for every b ∈ Y , there exists an a ∈ X such that f(a) = b.
surjective or (onto)
A function f : X → Y is ____if and only if for every a, b ∈ X, if a 6= b, then f(a) 6= f(b).
injective (or one-to-one)
A function that is both injective and surjective is called a
Bijection
True/False. If a statement is false, you should be able to provide a specific counterexample.
Examples.
* If a and b are integers such that [a]m = [b]m, then a = b.
True/False. If a statement is false, you should be able to provide a specific counterexample: *If a, b, p are integers, with p prime, such that p|ab, then p|a or p|b.
True/False. If a statement is false, you should be able to provide a specific counterexample: *Let a, b, m ∈Z+. If a ≡m b and a ≡n b, then a ≡mn b.
