Set Sizes

2026-11-18 · abstract-algebra

notes / Discrete Structures

Discrete Structures


Best Resource: Topology, University of Toronto


Finite and Infinite Sets

Size of a set: The size of a set can be defined in many ways. The most common would be the number of elements in the set

A={a1,a2,a3,a4,…,an}|A|=n

Finite Set → n<∞ Infinite Set → n=∞

Countable Sets

Motivation

In many areas of math we deal with a lot of infinite, and it becomes important to know when some are larger than others

Countably infinite sets are "small", and in fact are the "smallest infinite sets". They become convenient because you can list their elements, and thus use them for inductive proofs.

Counting

With finite sets we take counting for granted: we say that there are 3 birds, or 7 elements etc. But in math counting is defined as a process of comparing sets.

Say you have a hats, and b people. You start placing your hats on the people, and thus you can compare if you have more hats, or more people.

Set Size: Given two sets A and B we say that |A|≤|B| if there exists an injection (one-to-one) f:A→B or equivalently if there exists a surjection (onto) g:B→A if there is an injection from A to B but NO surjection from B to A then we can say |A|<|B|

Now what would could we say if there were both injections as well as surjections from A→B ?

Canter−Schröder−Bernstein Theorem: Given sets A and B; |A|=|B| if and only if there exists a bijection (one-to-one and onto) h:A→B

Proving this uses a very useful Proof Techniques called the "back-and-forth argument"

Countability

Countable Sets: A set A is said to be countably infinite if |A|=|ℕ| and countable if |A|≤ℕ Note: ϕ is countable because the empty function f:ϕ→ℕ is an injection

The intuition behind this should be that if you can list ALL the elements of A in a list as shown then A is countably infinite

a1,a2,a3,…

then you can construct the bijection f(n)=an making |A|=|ℕ|

Some Results on Countable Sets

Question

Property 1: Let A be a countably infinite set and B be an infinite subset of A. Then B is countable.Proof: Let f:ℕ→A be the bijection proving A is countable. Prove that: there exists a bijection g:ℕ→B

Let k1=min{k∈ℕ:f(k)∈B}=min(f−1(B)) That is, k1 is the smallest number that got mapped into B by the bijection f:ℕ→A as B⊆A

Proof by induction:

base case: define g(n) such that g(1)=f(k1)

inductive step (strong induction): assume we have defined g(1),g(2),g(3),…,g(n). Then let

kn+1=min{k∈ℕ:f(k)∈B−{g(1),g(2),…,g(n)}}

we can then define g(n+1)=f(kn+1) and continue like this by induction to map all elements in B.

Property 2: Let A and B be countable sets, then A×B is also countable

We can see this from an image proving ℕ×ℕ is countable

or more rigorously let f:ℕ×ℕ→ℕ be f(n,m)=2n3m which is injective by the uniqueness of prime decompositions

Question

Property 3: A countable union of countable sets is countable. i.e. if Ai,i∈ℕ are countable sets then ⋃i∈ℕAi is countablelet fn:ℕ→An be a bijection witnessing that An is countable, and define g:ℕ→⋃n∈ℕAn by g(n,i)=fn(i)

Uncountable Sets

another good resource: JL Martin

Cantor's Diagonalization Proof: (0,1)⊆ℝ is uncountable

This is a proof by contradiction

let us assume that (0,1) is countably infinite. And every x∈(0,1) can be represented as 0.a1a2a3a4a5a6…

let us list the real numbers as x=f(n)=0.x1nx2nx3nx4nx5nx6n…

this gives us a table like

we can now construct a number y=0.y1y2y3y4y5… that can not be on our list, which will contradict the assumption that f(n) is a bijection

let yk=(xkk+1)mod10

now y can not be the first number as y1≠x11 or the second number and so on, essentially y can not be in the table we constructed, thus f(n) can not be a bijection and (0,1) is uncountable

From this we can prove that ℝ is uncountable

ℝ is uncountable: we need a bijection h:(0,1)→ℝ. f(x)=π(x−12) is a bijection from (0,1)→(−π2,π2) and g(x)=tanx is a bijection from (−π2,π2)→ℝ. Thus h(x)=gof(x) is our required bijection.

h(x)=tanπ(x−12)

is the required bijection

Power Set Theorem: |S|<|𝒫(S)|

Prove that f:A→𝒫(A) can NOT be surjective define a set D={x∈A:x∉f(x)}

assume f is surjective now D∈𝒫(A)∴range of f contains D so let a∈A:f(a)=D.

|ℕ|<|𝒫(ℕ)|<|𝒫(𝒫ℕ))|… there are infinitely many sizes of infinity

linked from