Bijections and Cardinality
CS 2800: Discrete Structures, Spring 2015
Sid Chaudhuri
Recap: Left and Right Inverses
● A function is injective (one-to-one) if it has a left
inverse
– g : B → A is a left inverse of f : A → B if
g ( f (a) ) = a for all a ∈ A
● A function is surjective (onto) if it has a right
inverse
– h : B → A is a right inverse of f : A → B if
f ( h (b) ) = b for all b ∈ B
Thought for the Day #1
Is a left inverse injective or surjective? Why?
Is a right inverse injective or surjective? Why?
(Hint: how is f related to its left/right inverse?)
Sur/injectivity of left/right inverses
● The left inverse is always surjective!
– … since f is its right inverse
● The right inverse is always injective!
– … since f is its left inverse
Factoid for the Day #1
If a function has both a left inverse and a right
inverse, then the two inverses are identical, and this
common inverse is unique
(Prove!)
This is called the two-sided inverse, or usually just the
inverse f –1 of the function f
http://www.cs.cornell.edu/courses/cs2800/2015sp/handouts/jonpak_function_notes.pdf
Bijection and two-sided inverse
● A function f is bijective if it has a two-sided
inverse
● Proof (⇒): If it is bijective, it has a left inverse
(since injective) and a right inverse (since
surjective), which must be one and the same by
the previous factoid
● Proof (⇐): If it has a two-sided inverse, it is both
injective (since there is a left inverse) and
surjective (since there is a right inverse). Hence it
is bijective.
Inverse of a function
● The inverse of a bijective function f : A → B is the
unique function f ‑1: B → A such that for any
a ∈ A, f ‑1(f(a)) = a and for any b ∈ B, f(f ‑1(b)) = b
● A function is bijective if it has an inverse function
f(a)
a f ‑1(a) b = f(a)
f
A B
f ‑1
Following Ernie Croot's slides
Inverse of a function
● If f is not a bijection, it cannot have an inverse
function
f
x x
1 1 ?
y y
2 2
z z
3 3
w w
Onto, not one-to-one
f -1(2) = ?
Following Ernie Croot's slides
Inverse of a function
● If f is not a bijection, it cannot have an inverse
function
f
1 1 x
x
2 2
y y
3 3
z ? z
4 4
One-to-one, not onto
f -1(4) = ?
Following Ernie Croot's slides
How can we count elements in a set?
How can we count elements in a set?
● Easy for finite sets – just count the elements!
● Does it even make sense to ask about the number
of elements in an infinite set?
● Is it meaningful to say one infinite set is larger
than another?
– Are the natural numbers larger than
● the even numbers?
● the rational numbers?
● the real numbers?
Following Ernie Croot's slides
Cardinality and Bijections
● If A and B are finite sets, clearly they have the
same number of elements if there is a bijection
between them
e.g. | {x, y, z} | = | {1, 2, 3} | = 3
x 1
y 2
z 3
Following Ernie Croot's slides
Cardinality and Bijections
● Definition: Set A has the same cardinality as set
B, denoted |A| = |B|, if there is a bijection from A
to B
– For finite sets, cardinality is the number of elements
– There is a bijection from n-element set A to
{1, 2, 3, …, n }
Following Ernie Croot's slides
Cardinality and Bijections
● Natural numbers and even numbers have the
same cardinality
0 1 2 3 4 ...
2 4 6 8 10 ...
Sets having the same cardinality as the natural numbers (or
some subset of the natural numbers) are called countable sets
Following Ernie Croot's slides
Cardinality and Bijections
● Natural numbers and rational numbers have the
same cardinality!
0 1 4 5
1 1 1 1 ⋯
1 2 3 4
Illustrating proof 2
2 2
6
2
only for positive 1 2 3
rationals here, can 3 7
be easily extended 3 3 3
to all rationals 1 2 3
8
4 ⋱
1
⋮
Cardinality and Bijections
● The natural numbers and real numbers do not
have the same cardinality
x1 0.000000000…
x2 0.103040501…
x3 0.987654321…
x4 0.012121212…
x5 ⁞
Cardinality and Bijections
● The natural numbers and real numbers do not
have the same cardinality
Consider the number
x1 0.000000000… y = 0 . b1 b2 b3...
x2 0.103040501… 1 if the ith decimal
place of xi is zero
x3 0.987654321… bi =
0 if it is non-zero
x4 0.012121212…
x5 ⁞ y cannot be equal to any xi – it
difers by one digit from each one!
There are many infinities
Thought for the Day #2
Do the real interval [0, 1] and the unit square
[0, 1] x [0, 1] have the same cardinality?
0,1 1,1
0 1
0,0 1,0
Comparing Cardinalities
● Definition: If there is an injective function from
set A to set B, we say |A| ≤ |B|
2 4 6 8 ...
0 1 2 3 4 5 6 7 8 9 ...
|Evens| ≤ |N|
Following Ernie Croot's slides
Comparing Cardinalities
● Definition: If there is an injective function from set
A to set B, but not from B to A, we say |A| < |B|
● Cantor–Schröder–Bernstein theorem: If |A| ≤ |B| and
|B| ≤ |A|, then |A| = |B|
– Exercise: prove this!
– i.e. show that there is a bijection from A to B if there
are injective functions from A to B and from B to A
– (it's not easy!)
Following Ernie Croot's slides
