Transcript CS1231 - Lecture 09

Lecture 3 (part 3)
Functions – Cardinality
Reading: Epp Chp 7.6
1
Outline
1. Cardinal Numbers
2. Equality of Cardinal Numbers
3. Definition: Finite sets, Countably Infinite
sets, Uncountable sets.
4. Countable/Uncountable sets – theorems
5. Summary
2
1. Cardinal Numbers

Definition (Cardinal Number): Let S be
any set.
– Informally speaking, |S| denotes the
number of elements in the set S.
– Formally speaking, |S| is the cardinal
number of the set.
3
1. Cardinal Numbers

Examples:
– Cardinal Numbers of finite sets:
•
•
•
•
|{}| = 0
|{a}| = 1
|{{{a}}}}| = 1
|{a,b,c}| = 3
– We will deal with cardinal numbers of
infinite sets…
4
1. Cardinal Numbers

Note:
– When you think of the number of elements in the
set, you tend to think of ‘1,2,3,…’, and if you can’t
give a number, you just say ‘infinite’.
– DO NOT BRING this restricted idea of ‘number’ in
here.
– A Cardinal Number is a descriptive numerical
object, generalized to include ALL SORTS OF
SETS – FINITE OR INFINITE. In particular,
cardinals describe ‘how many elements’ in
INFINITE sets as well. As such it describes how
infinite the set is.
– So a ‘cardinal number’ is a more generalized
definition of a ‘number’ as you have been taught
in your previous math education.
5
2. Equality of Cardinal Numbers

Since cardinal numbers refer also
particularly to infinite sets, we must
define what it means for two sets (finite or
infinite) to have the same cardinal number
(hence same number of elements).
6
2. Equality of Cardinal Numbers

Definition (Equality of Cardinal numbers):
– Set A has-the-same-cardinality-as and B iff
there is a bijective function (1-1
correspondence) from A to B.
– We write |A| ; |B|.

NOTE: it makes no difference whether A
and B are finite or infinite,… our definition
requires you to find a bijective function!
7
2. Equality of Cardinal Numbers

Theorem:
– (; is reflexive): For all sets A, |A| ; |A|
– (; is symmetric): For all sets A, B,
if |A| ; |B|, then |B| ; |A|
– (; is transitive): For all sets A, B, C,
if |A| ; |B| and |B| ; |C|, then |A| ; |C|
8
2. Equality of Cardinal Numbers

Proof:
– (; is reflexive): For all sets A, |A| ; |A|
• Is there a bijective function from A to A?
• Yes, idA, the identity function on A is a
bijection from A to A.
– (; is symmetric): For all sets A, B,
if |A| ; |B|, then |B| ; |A|
• Assume that there is a bijection f from A to B.
• Then f-1 is a function from B to A, and is also a
bijection (proven in last lecture 9.4.2, 9.4.3).
• So there is a bijection from B to A, and so |B|
; |A|
9
2. Equality of Cardinal Numbers

Proof:
– (; is transitive): For all sets A, B, C,
if |A| ; |B| and |B| ; |C|, then |A| ; |C|
• Assume that |A| ; |B| and |B| ; |C|.
• Therefore there is a bijection f from A to B and
there is a bijection g from B to C.
• Therefore g o f is a bijection from A to C.
(Theorem 9.4.1 last lecture).
• Therefore |A| ; |C|
10
2. Equality of Cardinal Numbers

Definition:
– Since ; is an equivalence relation, we can
make the following definition:
– Sets A and B have the same cardinality iff
either A has-the-same-cardinality-as B or
B has-the-same-cardinality-as A.
– We can now write |A| = |B|
– There’s a slight subtle difference. The earlier definition ‘A has-thesame-cardinality-as B’ is a relation of the form A R B., of which we,
at that point in time, have not proven that R is an equivalence
relation.
11
3. Definition: Countability

Definition:
– A sets S is finite iff it is empty, or if there is
a natural number n such that S and
{1,2,…,n} have the same cardinality.
– A set is infinite iff it is not finite.
– A set S is countably infinite iff |S|;|Z+|.
– A set S is countable iff it is finite, or
countably infinite.
– A set is uncountable iff it is not countable.
12
3. Countability
finite
countable
infinite
Countably
infinite
uncountable
13
4 Countable/Uncountable sets
Theorem 4.1: Z is countable




Proof:
(By definition of ‘countable’), we need to show: |Z|;|Z+|
Which means (by definition of ‘;’), we need to show that
there exists a bijection from Z to Z+ (or vice versa, since
we know that if f is a bijection, then the inverse is also a
bijection).
Define f : Z+Z such that
n/2
if n is an even integer
f(n) =
-(n-1)/2
if n is an odd integer
6
3
4
2
2
1
1
0
3
-1
5
-2
7
-3
14
4 Countable/Uncountable sets
Theorem 4.1: Z is countable


Define f : Z+Z such that
n/2
if n is an even integer
f(n) =
-(n-1)/2
if n is an odd integer
Is f injective? (Prove using the definition)
– Assume f(a)=f(b) = kZ
• Case 1: k1
– Then f(a)=a/2 and f(b)=b/2.
– Since f(a)=f(b), so a/2=b/2. Meaning that a=b.
• Case 2: k<1
– Then f(a)=-(a-1)/2 and f(b)=-(b-1)/2.
– Since f(a)=f(b), so -(a-1)/2=-(b-1)/2. Meaning that a=b.
– In either case, a=b
15
4 Countable/Uncountable sets
Theorem 4.1: Z is countable


Define f : Z+Z such that
n/2
if n is an even integer
f(n) =
-(n-1)/2
if n is an odd integer
Is f surjective? (Prove using the definition)
– Pick any kZ. Is there a f(?)=k
• Case 1: k1
– Then f(2k)=k
• Case 2: k<1
– Then f(-2k+1)=k
– In either case, we can find an element in the domain that
maps to the codomain.
16
4 Countable/Uncountable sets
Theorem 4.1: Z is countable









We have proven that f is a bijection.
Let’s pause for a moment to consider this propositoin
that we have just proven.
Z is infinite.
Z+ is infinite.
Which is more infinite?
Most would answer intuitively that Z contains more
elements than Z+.
But your intuition must be in subjection to logic.
And logic tells you that they both contain the same
amount of elements: |Z|;|Z+|
(We can also write: |Z| = |Z+| )
17
4 Countable/Uncountable sets
Theorem 4.2: The set of all even integers (denoted
as 2Z) is countable.








Proof:
(By definition of ‘countable’), we need to show: |2Z|;|Z+|
Which means (by definition of ‘;’), we need to show that
there exists a bijection from 2Z to Z+ (or vice versa).
Define f : Z2Z such that f(n) = 2n
Now, f is a bijection from Z to 2Z.
Which means that |2Z|;|Z|
But we have also shown that |Z|;|Z+|.
So |2Z|;|Z+| (Since ; is transitive)
3
6
2
4
1
2
0
0
-1
-2
-2
-4
-3
-6
18
4 Countable/Uncountable sets
Theorem 4.3: Q+ is countable!





“Wait a minute!!!” (some of you might say…)
“You mean that Q+ contains the same amount of
elements as Z+ ???”
“The set of rationals and the set of integers contain the
same number of elements?”
“It seems obvious that rationals out-number the integers
right?”
WRONG!!!
19
4 Countable/Uncountable sets
Theorem 4.3: Q+ is countable!



Proof:
(By definition of ‘countable’), we need to show: |Q+|;|Z+|
We will give a bijection from Z+ to Q+.
1/1
1/2
1/3
1/4
1/5
1/6
2/1
2/2
2/3
2/4
2/5
2/6
f(1) = 1/1
f(2) = 1/2
3/1
3/2
3/3
3/4
3/5
3/6
f(3) = 2/1
4/1
4/2
4/3
4/4
4/5
4/6
f(4) = 3/1
5/1
5/2
5/3
5/4
5/5
5/6
6/1
6/2
6/3
6/4
6/5
6/6
20
4 Countable/Uncountable sets
Theorem 4.3: Q+ is countable!



Proof:
(By definition of ‘countable’), we need to show: |Q+|;|Z+|
We will give a bijection from Z+ to Q+.
1/1
1/2
1/3
1/4
1/5
1/6
2/1
2/2
2/3
2/4
2/5
3/1
3/2
3/3
3/4
4/1
4/2
4/3
4/4
5/1
5/2
5/3
5/4
2/6
f(1) = 1/1
f(2) = 1/2
f(8) = 3/2
f(9) = 4/1
3/5
3/6
f(3) = 2/1
f(10) = 5/1
4/5
4/6
f(4) = 3/1
5/5
5/6
f(5) = 1/3
f(6) = 1/4
6/1
6/2
6/3
6/4
6/5
6/6
f(7) = 2/3
21
4 Countable/Uncountable sets
Theorem 4.3: Q+ is countable!



Proof:
(By definition of ‘countable’), we need to show: |Q+|;|Z+|
We will give a bijection from Z+ to Q+.
1/1
1/2
1/3
1/4
1/5
1/6
2/1
2/2
2/3
2/4
2/5
3/1
3/2
3/3
3/4
4/1
4/2
4/3
4/4
5/1
5/2
5/3
5/4
2/6
f(1) = 1/1
f(2) = 1/2
f(8) = 3/2
f(9) = 4/1
3/5
3/6
f(3) = 2/1
f(10) = 5/1
4/5
4/6
f(4) = 3/1
f(11) = 1/5
5/5
5/6
f(5) = 1/3
f(6) = 1/4
6/1
6/2
6/3
6/4
6/5
6/6
f(7) = 2/3
22
4 Countable/Uncountable sets
Theorem 4.3: Q+ is countable!


Now, if we carry on, then
– Every element in Z+ will map to some rational
– An element in Z+ will be mapped to only one rational.
Therefore, f is a function.
1/1
1/2
1/3
1/4
1/5
1/6
2/1
2/2
2/3
2/4
2/5
3/1
3/2
3/3
3/4
4/1
4/2
4/3
4/4
5/1
5/2
5/3
5/4
2/6
f(1) = 1/1
f(2) = 1/2
f(8) = 3/2
f(9) = 4/1
3/5
3/6
f(3) = 2/1
f(10) = 5/1
4/5
4/6
f(4) = 3/1
f(11) = 1/5
5/5
5/6
f(5) = 1/3
f(6) = 1/4
6/1
6/2
6/3
6/4
6/5
6/6
f(7) = 2/3
23
4 Countable/Uncountable sets
Theorem 4.3: Q+ is countable!

Also note that
– Every element in Q+ appears in this 2D grid and will be associated with some Z+
as we go down the grid in a zig-zag manner (f is surjective).
– An element in Q+ will only be associated with only one element in Z+ (f injective).

Therefore, f is a bijection from Z+ to Q+.
1/1
1/2
1/3
1/4
1/5
1/6
2/1
2/2
2/3
2/4
2/5
3/1
3/2
3/3
3/4
4/1
4/2
4/3
4/4
5/1
5/2
5/3
5/4
2/6
f(1) = 1/1
f(2) = 1/2
f(8) = 3/2
f(9) = 4/1
3/5
3/6
f(3) = 2/1
f(10) = 5/1
4/5
4/6
f(4) = 3/1
f(11) = 1/5
5/5
5/6
f(5) = 1/3
f(6) = 1/4
6/1
6/2
6/3
6/4
6/5
6/6
f(7) = 2/3
24
4 Countable/Uncountable sets





Q: What do we know so far?
A: |2Z|;|Z|;|Z+|;|Q+|
So far, all the infinite sets seem to be
countable ( ‘equally infinite’ with each
other).
Q: Is there some infinite set which is
‘more infinite’ (contains more elements)
than another infinite set???
A: Yes!
25
4 Countable/Uncountable sets
Theorem 4.4: The set {xR | 0<x<1} is uncountable.




‘Countable’ means ‘THERE EXISTS a bijection to Z+.’
‘Not countable’ will then mean:
‘NOT (THERE EXISTS a bijection to Z+).’
Proof is essentially by contradiction, and it uses a
technique called diagonalization.
By contradiction:
– Assume there exists a bijection from Z+ to {xR | 0<x<1}.
– …
– Something contradictory arises.
26
4 Countable/Uncountable sets
Theorem 4.4: The set {xR | 0<x<1} is uncountable.


A: “Since you are insistent that there is a bijection… ok…, give
me an example of a bijection… I’ll show you that it is
contradictory.”
B: “Ok… here is my bijection from Z+ to {xR | 0<x<1}.”
f
1
0 . a11 a12 a13 a14 a15 … a1n …
2
0 . a21 a22 a23 a24 a25 … a2n …
3
0 . a31 a32 a33 a34 a35 … a3n …
4
0 . a41 a42 a43 a44 a45 … a4n …
5
0 . a51 a52 a53 a54 a55 … a5n …
6
0 . a61 a62 a63 a64 a65 … a6n …
7
0 . a71 a72 a73 a74 a75 … a7n …
27
4 Countable/Uncountable sets
Theorem 4.4: The set {xR | 0<x<1} is uncountable.


A: “Now I’ll show you what’s so contradictory…”
We construct a new number d = 0.d1d2d3 …dn… such that
dn =
f
1
0 . a11 a12 a13 a14 a15 … a1n …
2
0 . a21 a22 a23 a24 a25 … a2n …
3
0 . a31 a32 a33 a34 a35 … a3n …
4
0 . a41 a42 a43 a44 a45 … a4n …
5
0 . a51 a52 a53 a54 a55 … a5n …
6
0 . a61 a62 a63 a64 a65 … a6n …
7
0 . a71 a72 a73 a74 a75 … a7n …
1 if ann 1
2 if ann = 1
Observe that for each
integer n, d differs in
the nth decimal
position from the nth
real number in the list.
So d is NOT in the list!
But d is supposed to
be in the list! (^)
28
4 Countable/Uncountable sets
Theorem 4.4: The set {xR | 0<x<1} is uncountable.

A: “However you order the reals between 0 and 1, I can always
construct a real, which is not in your list. i.e. you will always
miss out some real number in your function”
f
1
0 . a11 a12 a13 a14 a15 … a1n …
2
0 . a21 a22 a23 a24 a25 … a2n …
3
0 . a31 a32 a33 a34 a35 … a3n …
4
0 . a41 a42 a43 a44 a45 … a4n …
5
0 . a51 a52 a53 a54 a55 … a5n …
6
0 . a61 a62 a63 a64 a65 … a6n …
7
0 . a71 a72 a73 a74 a75 … a7n …
So any function
from you propose
from Z+ to {xR |
0<x<1} can never be
a bijection!
So {xR | 0x1} is
uncountable.
29
4 Countable/Uncountable sets
Theorem 4.5: The set {xR | 0<x<1} has the same
cardinality as R.

Informal proof:
domain: {xR | 0<x<1}
1/4
f
-5 -4 -3 -2 -1
3/4
f
1/2
0
1
2
codomain
R
3
4
5
30
4 Countable/Uncountable sets
Theorem 4.6: Any subset of any countable set is countable.



Translate the statement:
If B
A and A is countable, then B is also countable.
NOTE: DO NOT think of finite sets. A and B can be
infinite sets.
Proof:
– Assume: B A and A is countable
– Either B is finite or B is infinite
• Case 1: If is B finite, then B is countable (by definition of
‘countable’).
• Case 2: If is B infinite, …
There is a bijection from Z+ to B.
B is countable
– In either case, B is countable.
31
4 Countable/Uncountable sets
Theorem 4.6: Any subset of any countable set is countable.
Z+
a1
a2
a3
a4
a5
a6
1
2
3
4
5
6
A

f
Z+
a2 = b1
a5 = b2
1
2
3
4
5
6
B
g
32
4 Countable/Uncountable sets
Theorem 4.6: Any subset of any countable set is countable.

Proof (Continued):
– Since A is countable, we have a bijection f : Z+A
(Let’s say that f(1) = a1; f(2) = a2 ; f(3) = a3 …)
– Define a function g : Z+B inductively as follows:
• Search through each element of A sequentially (Since A is
countable) until an element of B is found. This must happen
since (1) B A and (2) B is infinite, so B)
Call This element g(1).
• For each integer k  2, suppose g(k-1) has been defined,
meaning that we have
g(1) = b1; g(2) = b2 ; g(3) = b3 … g(k-1) = bk-1 = ai .
Starting with ai+1 search sequentially from ai+1, ai+2, ai+3,… until
another element of is found B. Call this element g(k).
This must happen since B is infinite and {g(1),g(2),g(3) ,…,g(k-1)}
is finite.
33
4 Countable/Uncountable sets
Theorem 4.6: Any subset of any countable set is countable.
Z+
a1
a2
a3
a4
a5
a6
1
2
3
4
5
6
g is 1-1 since we only took
out distinct elements.
A

f
Z+
a2 = b1
a5 = b2
1
2
3
4
5
6
B
g
g is onto, since (1) Each
search for g(k) continues
from where the previous one
left off, so every element of A
is reached, and since (2) all
elements in B are
somewhere in A, so all
elements of B will be
eventually found.
So is g a bijection.
34
4 Countable/Uncountable sets
Theorem 4.7: R is uncountable.
(Weaker version of theorem 4.5)
Proof:
 Thm 4.6: If B A and A is countable, then B is also countable.
 Contrapositive: if B is uncountable then … if B A then A is
uncountable.




Choose B = {xR | 0<x<1} and A = R.
We know that B is uncountable (thm 4.4).
We also know that B A.
Therefore A (which is R) is uncountable.
35
5. Summary

What do we know so far?
1. |2Z| ; |Z| ; |Z+| ; |Q+|
2. |{xR | 0<x<1}| ; |R|

Definition (Cantor):
– |Z+| = 0
– |R| = c
The symbol ‘’ is pronounced ‘aleph’ (the first letter of the
Hebrew alphabet). We have shown that 0  c.



(FACT) It can be proven that 0 is the first (i.e. the
‘least’/‘smallest’) infinite cardinal.
(Definition) We let 1 be the least cardinal which is greater
than 0 (the next biggest one after 0)
(Unknown): Is 1 = c ??? (Cantor’s Continuum Hypothesis). 36

End of Lecture
37