Discrete Mathematics· Note 04
Cardinality
Jan. 28
Cardinal Numbers
Definition:
Define a relation between sets as follows:
is “(cardinal-)equivalent” to (denoted ) whenever there exists a bijection .
Define
Let . because no bijection exists (there are too many elements in .)
It’s easy to see that two finite sets are equivalent iff they have the same number of elements.
A cardinal number is an equivalence class of this relation.
Finite cardinal numbers: 0,1,2,3,4,5,6…
For infinite sets, things are a bit different.
Cardinality of Infinite Sets
Bounded Intervals
What other sets are in the equivalence class of ?
Is there a bijection ? Yes there is: .
Therefore, , meaning that they are in the same equivalence class, and therefore have the same cardinality.
Graphically, we connect the left endpoints and the right endpoints with segments that meet at point . Drawing any segment from to some point on , associate with bijection.
Expanding on this, we can see that all bounded intervals are equivalent.
(We’ll see later about intervals in the form )
Unbounded intervals
. Easy to see that is a bijection.
. is a bijection.
What about the infinite sets and ? Does there exist a bijection ?
Yes:
Is there a bijection ?
Think of as the set of all passengers in “infinitely many busses carrying infinite passengers each.”
E.g., passenger 83 on bus 24 is pair (83,24)
Yes: We can see it by writing out in an infinite 2D array.
Then we can define a bijection by following a diagonal traversal of the array.
Feb. 4
However…