STEP-BY-STEP LESSON · §7.4
Cardinality with Applications to Computability
Understand equal cardinality through a bijection, including infinite sets.
Before you begin
One-to-One, Onto, and Inverse Functions
Injectivity means equal outputs can come only from equal inputs.
f(x_1)=f(x_2) ⇒ x_1=x_2
Surjectivity means each y∈Y has some x∈X with f(x)=y.
f(X)=Y
A function that is both injective and surjective is a bijection. Each y then has exactly one original x.
f⁻¹:Y→X
Symbols
- |A|
- cardinality of A
- ℤ⁺
- positive integers
- sᵢ(j)
- bit in position j of sequence i; both indices are positive integers
- d(i)
- bit obtained by flipping sᵢ(i)
Definitions and notation for this topic
Cardinality
|A|
For a finite set, its number of elements.
Here the vertical bars mean the size of a set.
For infinite sets, cardinality is compared using bijections; it is not a finite element count. See Cardinality and countability. For a number x, |x| is absolute value instead.
Separate glossary example
|{2,3,4}| = 3
Cardinality and countability
|A|=|B|
Sets A and B have the same cardinality when a bijection A→B exists. A countably infinite set has a bijection with the positive integers; here countable means finite or countably infinite.
An infinite set can match a proper subset by a bijection, unlike a finite set. Uncountable means no such finite or integer-indexed enumeration covers the set.
Separate glossary example
The positive even integers are countably infinite via n↦2n from ℤ⁺. The real numbers are uncountable.
Step by step
Step 1 / 6
Replace counting by matching
Sets have equal cardinality when a bijection pairs every element exactly once with no omissions.
|A|=|B|
This definition also works when ordinary counting would never finish.
Worked example
Why are there as many positive even integers as positive integers?
- Define f(n)=2n from ℤ⁺ to E={2,4,6,…}.
- If 2n=2m, dividing by 2 gives n=m, so f is injective.
- Every positive even e has form 2k for k∈ℤ⁺, so f(k)=e. This is surjectivity, hence a bijection.
Optional self-check
How can positive integers be matched with positive odd integers?
Show answer
f(n)=2n−1. Every positive odd integer has a unique form 2n−1 with n≥1.