Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 37 ยท Getting Started

Sets, Functions and Countability

Review sets, functions, injective and surjective maps, then learn countable and uncountable sets, including Cantor's diagonal argument.

Analysis is written in the language of sets and functions. This lesson reviews the notation you will meet in every later chapter and then tackles one of the first deep ideas: some infinite sets are larger than others. By the end you will know why the natural numbers and the rational numbers are the "same size", while the real numbers are strictly bigger.

Sets

A set is a collection of objects, called elements. We write x โˆˆ A if x is an element of A.

Notation Meaning
A โІ B every element of A is in B (subset)
A โˆช B elements in A or B (union)
A โˆฉ B elements in both (intersection)
A \ B elements of A not in B (difference)
โˆ… the empty set

Standard number sets: โ„• = {1, 2, 3, ...}, โ„ค the integers, โ„š the rationals (fractions p/q), โ„ the real numbers.

To prove A = B, show A โІ B and B โІ A. To prove A โІ B, take an arbitrary x โˆˆ A and show x โˆˆ B.

Example (De Morgan). A \ (B โˆช C) = (A \ B) โˆฉ (A \ C). If x is in the left side, x โˆˆ A and x is in neither B nor C, so x โˆˆ A \ B and x โˆˆ A \ C. Reversing the reasoning gives the other inclusion.

Python Check set identities on examples

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Functions

A function f: A โ†’ B assigns to each a โˆˆ A exactly one f(a) โˆˆ B. A is the domain, B the codomain, and f(A) = {f(a) : a โˆˆ A} the range (image).

  • f is injective (one-to-one) if f(a) = f(a') implies a = a'.
  • f is surjective (onto) if every b โˆˆ B equals f(a) for some a.
  • f is bijective if it is both; then it has an inverse function.

For example, f(x) = xยฒ on โ„ is neither: f(2) = f(-2) and no input gives -1. Restricted to [0, โˆž) โ†’ [0, โˆž) it is bijective with inverse โˆš.

Same size for infinite sets

For finite sets, "same size" means a bijection exists. We use the same definition for infinite sets. A set is countable if it is finite or can be put in bijection with โ„•. Infinite countable sets are called countably infinite.

Surprisingly, โ„ค is countably infinite: list it as 0, 1, -1, 2, -2, 3, -3, .... The bijection sends n to n/2 if n is even and to -(n-1)/2 if odd (taking โ„• to start at 0 here).

The rationals are countable

Arrange positive fractions p/q in a grid with p across and q down, then walk the diagonals, skipping fractions already seen (like 2/2 = 1/1). Every positive rational appears at a finite position, so โ„šโบ is countable. Interleave with negatives and 0 to get all of โ„š.

Python List rationals along diagonals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The reals are uncountable

Theorem (Cantor). The interval (0, 1) is not countable.

Proof by the diagonal argument. Suppose a list xโ‚, xโ‚‚, xโ‚ƒ, ... contained every number in (0, 1). Write each in decimal, x_n = 0.d_{n1} d_{n2} d_{n3}..., avoiding endings of all 9s. Build a new number y = 0.eโ‚ eโ‚‚ eโ‚ƒ... where e_n = 5 if d_{nn} โ‰  5 and e_n = 6 if d_{nn} = 5. Then y differs from x_n in the nth digit, so y is not on the list, yet y โˆˆ (0, 1). Contradiction. โˆŽ

We chose digits 5 and 6 so that y has no 9s and no ambiguity with alternative decimal expansions.

Python The diagonal construction on a finite list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A finite list proves nothing by itself; the point is that the same recipe works on any infinite list, so no list can be complete.

flowchart TD
  N["โ„• (countable)"] --> Z["โ„ค (countable)"]
  Z --> Q["โ„š (countable)"]
  Q --> R["โ„ (uncountable)"]

Each set contains the previous, but a bijection with โ„• exists only up to โ„š.

A consequence: since โ„š is countable and โ„ is not, most real numbers are irrational.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which function is injective?

    If 2x + 1 = 2y + 1 then x = y. The other three send different inputs to the same output.
  2. 2. Which set is NOT countable?

    Cantor's diagonal argument shows (0, 1) cannot be listed. โ„ค, โ„š and โ„• can.
  3. 3. To prove A = B you should

    Set equality means mutual inclusion.
  4. 4. Why does the diagonal number use digits 5 and 6 rather than any digit?

    Some numbers have two decimal expansions (like 0.5 and 0.4999...). Avoiding 0 and 9 prevents that ambiguity.

Summary

  • To compare infinite sets, use bijections.
  • โ„•, โ„ค and โ„š are countable; โ„ is uncountable (Cantor's diagonal argument).
  • Injective, surjective and bijective describe how a function covers its codomain.
  • Prove set equality by two inclusions.

Next: Induction and Inequalities