Transcript reviewfortest2

Review for Test 2
Scheduled for Wednesday, April 2
Covers 1.8, 2.4, 3.1, 3.2, 3.3, and 3.4
Formal Framework for Induction
You are asked to prove some statement X for all n  S.
The set S is some well-ordered subset of the integers of
the form {b, b + 1, b + 2, … } where b is an integer.
The statement X is always some predicate involving n,
such as 1 + 2 + … + n = n(n + 1) / 2.
1st step: Introduce your predicate.
[ex: Let P(n) denote 1 + 2 + … + n = n(n + 1) / 2.]
Now you desire to prove n  S P(n). And the principle of
mathematical induction tells you that you can do this by
showing both P(b) and also n  S [P(n)  P(n + 1)].
2nd step: Prove base case [Prove P(b)]
3rd step: Prove inductive case [n  S [P(n)  P(n + 1)]]
(a) Set up for universal generalization [Let n  S]
(b) Assume the hypothesis [Assume P(n)]
(c) Show the consequent [Show P(n + 1)]
(d) Now by the principle of mathematical induction you
have proved the desired result.
Know recursive definitions. If I give you a recursive
definition of a sequence or a set, you should be able to
write out the initial terms of the sequence, or tell me what
the set is equal to.
Ex: -1  S.
x + y  S whenever x  S and y  S.
Identify the set S. Answer S = { x  Z | x < 0 }. Or S = Z-.
Be able to prove this if asked to. [Structural Induction].
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Know the definition of a map and a function
Be able to determine if a map is a function
Determine the domain, codomain, and range of a function
Determine if a function is one-to-one and/or onto
What is the significance of a one-to-one correspondence
Inverse functions (construct them, when do they exist)
Know how to compose two functions (when can you do it)
What does it mean for a to divide b
Be familiar with division theorems
What is a prime number; What is a composite number
Fundamental Theorem of Arithmetic (know how to factor)
There are infinitely many primes (could you prove this)
The Division Algorithm
gcd, lcm, how to exploit the prime factorizations to get them
Modular arithmetic, congruences
• Proof strategies, working backwards, etc. The goal is
that you can prove complex statements.
• When can you use a counter-example
• Sequences and Summations
– Know summation notation; evaluate sums
– Know sequence notation; given a sequence definition, produce
terms of the sequence
– Work with summation notation
– What is the definition of a sequence
– How are sequences used in cardinality/countability proofs
– What does it mean for two sets to have the same cardinality
– What does it mean for a set to be countable or uncountable
– How to prove a set is countable
– How to prove a set is uncountable
– Note the following theorem that we never introduced, but some
of you used it intuitively:
• If f: S  T is onto, then |S|  |T|
Diagonalization
• We used the technique of diagonalization to prove that the
set of real numbers is uncountable.
• Use this technique to prove that P(N) is uncountable!
• Why can’t we use diagonalization to show N is uncountable?
• Clearly we can’t because N is countable
• We can enumerate N or construct a one-to-one
correspondence between N and Z.
• Note that the definition of a countable set is that it is finite or
can be put in one-to-one correspondence with Z.
• Actually
all we need to do is put it in one-to-one
correspondence with another set we know to be countable.