Diagonalization
Diagonalization Arguments: Overview
- When do 2 sets have the same number of elements
- Some examples:
- Positives and Negatives
- Positives and Naturals
- Positives and Integers
- Positives and Rationals
- The examples lead up to our goal:
When are 2 sets the same size
- Are these sets the same size: {a,b,c} and {x, y, z}
- How do you know?
- Both have 3 elements
- And these sets:
- {a, b, c, d, e, f, g, h, i, j, k, l, m, n}
- {A, B, C, D, E, F, G, H, I, J, K, L, M, N}
- How do you know?
- Did you count them?
- Perhaps, but not necessarily
- Two sets have the same size if they
- Have the same number of elements (ie count them), or
- There is a one-to-one, onto correspondence between the elements
Infinite Sets
- How can we compare the sizes of infinite sets?
- Count them?
- Show that they are 1:1, onto
- Let's look at some examples
Example Infinite Sets
- Positives and Negatives:
- Positives and Naturals:
- p = ?
- p = n + 1
- n = ?
- n = p - 1
Positives and Integers
- Positives and Integers: could these sets have the same size?
- What correspondence could we use?
- i = (p+1)/2 if p is odd
- i = -p/2 if p is even
- p = 2i-1 if i is positive
- p = -2i if i is negative
- Hmmm?
- Thus, these sets are the same size!
- Hmmm?? Remember our definition of same size
Positives and Rationals
- Positives and Rationals: Are these sets the same size?
- Is there a correspondence?
- Put solution on board ...
- Hmmm? We ignore some subtle points
- Thus, these sets are the same size!
Positives and Reals
- Positives and Reals (between 0.0 and 1.0):
- Could these sets be the same size?
- We will prove that they ARE NOT!
- We will use proof by contradiction
Proof by Contradiction
- Assume opposite of what you want to prove
- Prove that the assumption leads to a contradiction
- Conclude that the assumption is false
- Thus, the opposite of the assumption must be true
- Thus, what you wanted to prove must be true
Proof by Contradiction: Example
- To Prove: The set of integers does not contain a largest element
- Assume that the set of integers does contain a largest element
- Let p be that largest element
- Let q = p + 1
- But q is an integer
- Both p and 1 are integers, and the set of integers
is closed under addition
- Remember the concept of sets being closed under an operation
- But, q is greater than p (Definition of greater, wave hands)
- Thus q is greater than the largest element, a contradiction
- Thus the assumption (there is a largest) was false
- Conclusion: the set of integers does not contain a largest element
Positives and Reals
- Positives and Reals (between 0.0 and 1.0):
- Could these sets be the same size?
- We will prove that they ARE NOT
- Proof by contradiction
- Assume they are the same size, and find a contradiction
- Assume they are the same size means assume that they are 1:1, onto
- If they are 1:1, onto, then they can be listed 1, 2, 3, ...
- This will lead to a contradiction
Positives and Reals Are NOT the Same Size
- Assume they are 1:1, onto and thus a list of reals exists
- Every real must be on this list
- Let Li be the list element at position i,
- For some real r, let rj be the digit at position j
- Thus, Lij is digit j of the real at position i
- Now form real x as follows:
- Digit j of real x is 1 + Ljj
- That is, digit j of x is 1 + digit j of the real at position j
- Now, since the list contains all reals, then it must contain x
- Assume that x occurs at position k (ie x=Lk)
- Then Lk1 is the first digit of x, and
Lk2 is the second digit of x
- What is digit k of x????
- By definition of the list, it's Lkk (since x is at position k)
- But by definition of x, it's 1 + Lkk
- Thus, Lkk = 1 + Lkk!
- This is a contradiction, and so the two sets are NOT 1:1, onto
Let's Repeat the Proof
- Start with a list of all reals
- Define real x: digit k of x is 1 + Lkk
- x is a real, and so it must appear in the list.
- Assume it appears at position k (ie x = Lk)
- What is digit k of x: Lkk, of course
- But, digit k of x is defined to be 1 + Lkk
- Lkk = 1 + Lkk is a contradiction, so conclude the list does not exist
- Notice the two ways of looking at Lkk
- If we look at x as member k of the list,
we get digit k to be Lkk
- If we look at x as defined, we get digit k to be 1 + Lkk
Diagonalization: The Significance
- First, this is an interesting result!
- Second, we will use the same technique later
- We will use it to prove that there are non-computable sets