Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 38 · Cardinality

Cardinal Arithmetic

Define addition, multiplication and exponentiation of cardinals using disjoint unions, products and function sets, and test them with Python.

Once sizes are defined by bijections, we can do arithmetic with them. Cardinal arithmetic is not a new set of rules: it takes the counting rules from finite sets and turns them into definitions that also work for infinite sets.

This is the moment where infinity starts to look strange: with infinite cardinals, ℵ₀ + ℵ₀ = ℵ₀, and ℵ₀ · ℵ₀ = ℵ₀. By the end you will see why these are not mistakes.

The three operations

Let κ = |A| and λ = |B|. (The Greek letters kappa and lambda are the usual names for cardinals.)

Operation Definition Finite check
Sum κ + λ the size of a disjoint union of A and B 3 + 2 = 5
Product κ · λ the size of A × B 3 · 2 = 6
Power λ^κ the number of functions from A to B 2³ = 8

Pay attention to the order in the power: λ^κ counts functions from a set of size κ into a set of size λ. There are λ choices of output for each of the κ inputs, so for finite sets this is λ · λ ··· λ (κ times).

If A and B overlap, first replace them by disjoint copies, for example A × {0} and B × {1}. This is why the definition says "disjoint": the sum must not depend on accidental overlap.

The definitions agree with school arithmetic

For finite sets, all three definitions give ordinary numbers. Here the function count is the key check.

Python Count functions to check exponentiation

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.

Laws you can rely on

Cardinal arithmetic obeys the familiar laws, for all cardinals κ, λ, μ:

  • κ + λ = λ + κ and κ · λ = λ · κ (commutative)
  • (κ + λ) + μ = κ + (λ + μ) and the same for products (associative)
  • κ · (λ + μ) = κ · λ + κ · μ (distributive)
  • κ^(λ + μ) = κ^λ · κ^μ, (κ^λ)^μ = κ^(λ · μ) and (κ · λ)^μ = κ^μ · λ^μ

Each law is proved by writing down a bijection. For example, (κ^λ)^μ = κ^(λ·μ) says that a function which, given y in B, returns a function A → C, is the same data as a function that takes a pair. Programmers call this currying.

Python Currying: a bijection behind (κ^λ)^μ = κ^(λ·μ)

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 infinite case: a first look

The definitions apply to any sets. Take ℵ₀ = |ℕ|.

ℵ₀ + 1 = ℵ₀. Add a new element * to ℕ. Send * to 0 and each n to n + 1. This is a bijection from {*} ∪ ℕ onto ℕ.

ℵ₀ + ℵ₀ = ℵ₀. Take two copies of ℕ, say ℕ × {0} and ℕ × {1}. Send (n, 0) to 2n and (n, 1) to 2n + 1. That interleaves the two copies and covers every natural number exactly once.

ℵ₀ · ℵ₀ = ℵ₀. This one, the matching of ℕ × ℕ with ℕ, is the subject of the rationals lesson.

2^ℵ₀ > ℵ₀. The power 2^ℵ₀ counts functions ℕ → {0, 1}, which are the same as subsets of ℕ. Cantor's theorem, in power sets, shows this cardinal is strictly bigger than ℵ₀.

Python Interleave two copies of the naturals

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.

Subtraction and division are not defined for infinite cardinals. From ℵ₀ + 1 = ℵ₀ + 2 you cannot cancel ℵ₀ to conclude 1 = 2. Only addition, multiplication and powers are available.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How is the cardinal sum κ + λ defined?

    Sum uses a disjoint union. The Cartesian product defines multiplication and function sets define powers.
  2. 2. How many functions are there from a 4-element set into a 3-element set?

    Each of the 4 inputs has 3 possible outputs, so there are 3^4 = 81 functions.
  3. 3. Why can't we cancel ℵ₀ in the equation ℵ₀ + 1 = ℵ₀ + 2?

    Both sides equal ℵ₀, but that does not mean 1 = 2. Subtraction is not defined for infinite cardinals.
  4. 4. What does currying show about cardinal exponentiation?

    A function of two arguments is equivalent to a function returning a function, which is the law (κ^λ)^μ = κ^(λ·μ) up to naming.

Summary

  • Cardinal sum uses a disjoint union, product uses the Cartesian product, and power counts functions.
  • For finite sets these match ordinary arithmetic; the laws (commutative, associative, distributive, exponent rules) hold in general.
  • Each law is a bijection; currying is the bijection behind (κ^λ)^μ = κ^(λ·μ).
  • Infinite cardinals absorb: ℵ₀ + 1 = ℵ₀, ℵ₀ + ℵ₀ = ℵ₀. Cancellation is not allowed.

Next: Countable Sets