Why can no scheme assign a distinct finite identifier to every infinite stream of events a system could emit?

## What countable means, precisely The whole argument rests on one definition. Two sets have the **same size** when a bijection between them exists — a pairing that leaves nothing spare on either side. A set is **countable** when such a pairing exists with the positive integers, which is the same as saying its elements can be laid out in one endless list `x1, x2, x3, ...` where every element appears at some finite position. That definition is more generous than intuition expects, and several sets that feel far too big are countable: - The integers, negatives included: list them `0, 1, -1, 2, -2, ...`. - Every **finite string** over a finite alphabet: order by length first, then alphabetically within each length. Each length holds finitely many strings, so every string appears at a finite position. - Therefore every **finite artifact** a system can hold — every log file, every configuration, every identifier scheme's output, every finite program text — is countable, because each one is a finite string over a finite alphabet. That last point is what makes identifier schemes work at all: handing out distinct finite identifiers *is* building such a list. ## The diagonal argument Now take the set of **infinite** streams over even a two-symbol alphabet — an endless sequence of events where each step is one of two kinds. Suppose someone claims a numbering of all of them: `stream(1), stream(2), stream(3), ...`. Build a new stream `d` by walking down the diagonal of that list and disagreeing at every step: let `d`'s n-th symbol be the opposite of `stream(n)`'s n-th symbol. - `d` is a legitimate infinite stream over the same alphabet — every position has a defined symbol. - `d` differs from `stream(1)` at position 1, from `stream(2)` at position 2, and in general from `stream(n)` at position n. - So `d` is not `stream(n)` for any n, and the numbering was not complete. Nothing about the numbering was assumed, so **no** numbering is complete: the streams are **uncountable**. They cannot be paired with the positive integers, and so cannot be paired with any set of finite identifiers either. ## Why this is structural and not a budget problem The usual objection is that a longer identifier would fix it. It would not, and stating why is the point of the question: - Identifiers of some fixed maximum length form a finite set; identifiers of any finite length form a countable one. Neither reaches an uncountable set. - Nothing here is about machine word sizes, storage, or how long the system runs. The argument is about the sets, so faster hardware and bigger addresses move nothing. - It also does not depend on the alphabet: two symbols per step already suffice, so a richer event vocabulary cannot rescue the scheme. ## What an engineer actually takes away 1. **Identify finite artifacts, not behaviours.** A trace you have recorded is finite and can be named. "Every possible behaviour of this system, forever" is a different kind of object and cannot be enumerated. 2. **Any finite identifier over an unbounded input domain is many-to-one.** That is a counting fact rather than a flaw in a particular scheme, and it is why a fixed-width identifier over an open-ended input space can only ever be distinct in practice, never distinct by construction. 3. **Continuous quantities carry the same warning.** Anything modelled as an arbitrary real value — an exact instant, an exact ratio — sits in an uncountable set, which is one reason such values are always stored as a finite approximation with a stated precision rather than as themselves. ## The refinement worth knowing Here is the fact that separates a recited proof from an understood one. Every stream a **program** can produce is itself named by that program's finite text, and finite texts are countable. So the streams your systems will ever generate form a countable set; the uncountably many others are exactly those with no finite description at all. The impossibility is therefore not an obstacle to any identifier scheme you were actually going to build — it is a statement about what "every possible stream" quietly asks for. Interviewers like that turn because it shows you can tell the mathematical claim apart from its engineering reach, rather than treating an uncountability result as a warning about running out of identifiers.