Cardinality is the size of a set; two sets have the same cardinality when their members can be paired in a one-to-one correspondence, or bijection. A set is countable if it is finite or can be put in bijection with the natural numbers. Otherwise it is uncountable. In a market model, this distinction separates a list of possible scenarios from a space of complete paths that no natural-number-indexed list can exhaust.
For a finite set, cardinality is the familiar count of distinct members, written . For infinite sets, “both go on forever” does not settle whether they have the same size. Gowers's Cambridge introduction states the countability convention used here: finite sets count as countable. We write .
A larger horizon is not an infinite path
Imagine a synthetic market history with two permitted moves at each observation: down, encoded as 0, and up, encoded as 1. Every binary history is allowed. At a fixed horizon of observations, the sample space is
Three moves give paths; five give . These count ordered histories, not distinct terminal prices. Different histories may reach the same terminal price in a recombining tree. The counts also impose no probabilities or independence assumption: they just say which histories are permitted.
Now collect histories of every finite length, including the empty history of length zero:
This set is countably infinite. List strings first by length, then alphabetically within each length:
Each particular finite string appears at a finite position. This is a concrete instance of a countable union of finite sets being countable; CMU's notes, Proposition 4.12, give this construction for a finite alphabet.
An infinite path is a different object: it assigns a move to every positive integer observation time, without ending. The space
is uncountable. Here the exponent uses the positive integers as coordinate labels. A countable set of observation times does not make the set of all paths countable. Nor does taking the union of all finite histories produce those infinite paths: every member of that union still ends.
Original synthetic histories. The finite window illustrates a proof about every row of an alleged infinite list; six displayed rows alone cannot prove uncountability.
Suppose a list did contain every infinite binary path, and write for coordinate of row . Construct a path by
It differs from row 1 at coordinate 1, from row 2 at coordinate 2, and from every row at coordinate . Thus is an allowed infinite path missing from the proposed complete list. The contradiction is Cantor's diagonal argument, developed in the University of Illinois countability lecture.
Two coordinates can still be counted
Infinite sets can also be smaller than a picture suggests. The nonnegative even integers have the same cardinality as : pair with . Every even integer is reached exactly once, despite the evens being a strict subset.
Similarly, ordered pairs of nonnegative integers are countably infinite. Visit the grid by diagonals of constant , rather than trying to finish its infinite first row. One zero-based Cantor pairing convention is
The first diagonal receives label 0, the next labels 1–2, the next 3–5, and so on. At , five earlier diagonals contain pairs; the offset is 3, giving . Each diagonal occupies a consecutive block of labels, so every pair gets one label and every nonnegative label gets one pair. Coordinate order matters; Szudzik's paper, §1, discusses both swapped variants.
| Set | Size classification |
|---|---|
| Binary histories of one fixed finite length | Finite |
| All finite binary histories | Countably infinite |
| Ordered pairs of nonnegative integers | Countably infinite |
| All infinite binary paths | Uncountable |
| Real numbers in a nonempty open interval | Uncountable |
Size does not assign likelihood
Probability needs a law in addition to a set. A countably infinite space can give every member positive probability: on , masses sum to one. Equal positive masses would instead make the total diverge; equal zero masses would sum to zero. There is no uniform probability law on this countably infinite space.
For a continuous random variable with a density, each exact value has probability zero because its singleton integral is zero. For example, a synthetic P&L uniform on USD has but . Zero probability does not make USD 0 an excluded outcome. MIT's continuous-variable slides explain probabilities as density integrals. Countable additivity does not permit an uncountable sum of singleton probabilities to replace that integral.
Uncountability alone does not force zero point masses either. A model that puts half its probability at USD 0 and half on that uniform law still has an uncountable range, but .
Cardinality also does not measure computational cost. A finite scenario set can be too large to enumerate. The Counting and Combinatorics lesson develops finite counts through multiplication, permutations and combinations; its public page is a preview and the full lesson requires membership. A portfolio cardinality constraint counts positions held, a separate application of finite set size.
Sources
- Timothy Gowers, Cambridge, “Countable and uncountable sets”, definitions 1–4 and facts B–C: finite size, bijections, countable unions and uncountability of the reals.
- Anil Ada and Ariel Procaccia, CMU 15-251 Fall 2017 course notes, Chapter 4, especially Proposition 4.12 and Theorem 4.21: finite strings and infinite binary sequences.
- University of Illinois, CS 173, “Countability 3”, “Diagonalization”: why a list of infinite binary paths must omit a path.
- Matthew P. Szudzik, The Rosenberg-Strong Pairing Function, version 5 (2019), §1: zero-based Cantor pairing and coordinate-swapped conventions.
- MIT OpenCourseWare, 18.05 Spring 2022, “Variance; Continuous Random Variables”, slides on continuous variables, PDFs and CDFs: interval probabilities as integrals.