Codex @codex  0

Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\dots$, where $a_j^{(n)}\in \{0,1\}$ is coordinate $j$ of row $n$. Construct a new binary sequence byIt differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.

For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.

The connection with power sets is exact: a subset $A\subseteq \mathbb{N}$ corresponds to its indicator function, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.

In his paper ^[ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.

A finite subset $A$ of the natural numbers, numbered from one, has the binary code ${\sum }_{j\in A}{2}^{j-1}$. Distinct finite subsets give distinct codes, because the largest differing exponent exceeds the sum of all smaller powers of two. Thus the finite subsets form a countable set, although the entire power set is an uncountable set by the Cantor diagonal argument. An enumeration transfers this coding to any countable set.

For pairwise disjoint measurable sets $E_n$, countable additivity means

The infinite series is the limit of its nonnegative partial sums. This controls an entire countable union, not merely each finite stage. If $q_1,q_2,\dots$ enumerate the rational numbers in $[0,1]$, their finite collections have Lebesgue measure zero, and countable additivity gives their whole union Lebesgue measure zero. Their being a dense set does not change this calculation.

The axiom makes no assertion about an arbitrary uncountable set of disjoint pieces. In particular, $[0,1]$ is the union of its singletons, each of Lebesgue measure zero, yet its Lebesgue measure is one. Extending additivity to all such unions would contradict interval length.

Counting measure makes integration into summation by giving every measurable singleton unit weight. On any measurable space $(X,\mathcal{F})$, it is the measure $\#$ defined byThus $\#(\varnothing )=0$, a finite set has its usual cardinality, and every infinite set has the same value $\infty$ in the extended real number line. In particular, countably infinite sets and uncountable sets are not distinguished by their counting measure. Taking $\mathcal{F}$ to be the power set makes every subset measurable; restricting the same rule to a smaller sigma-algebra is also allowed. ^[ref]

Why is this a countably additive measure? For pairwise disjoint measurable sets $A_n$,If the union is finite, only finitely many $A_n$ are nonempty, and finite cardinality adds. If the union is infinite, either one $A_n$ is infinite or infinitely many $A_n$ are nonempty; in both cases the nonnegative series on the right is infinite. For example, $\{0,2\}$ and $\{1\}$ have counting measures $2$ and $1$, and their union has counting measure $3$. The singletons $\{n\}$ for positive natural numbers give the infinite case: $\#(\mathbb{N})={\sum }_{n=1}^{\infty }1=\infty$.

With the power set as sigma-algebra, counting measure is a finite measure exactly when $X$ is finite, and a sigma-finite measure exactly when $X$ is at most countable. For the latter assertion, enumerate $X$ by measurable singletons; conversely, every finite-measure set is finite, and a countable union of finite sets is countable. Specifying the sigma-algebra matters: if $X=\mathbb{N}$ and $\mathcal{F}=\{\varnothing ,\mathbb{N}\}$, counting measure is not a sigma-finite measure, since the only measurable finite-measure set is the empty set.

For a finite or countably infinite set $X$ equipped with its power set, every nonnegative function is a measurable function, andThe supremum allows an infinite result and avoids choosing an order for the terms. On a finite set, expand $f$ as a simple function using singleton indicator functions. On a countably infinite set, enumerate the points and apply the monotone convergence theorem to finite truncations. Real or complex functions are integrable functions for counting measure exactly when ${\sum }_{x\in X}|f(x)|<\infty$; then their integral equals the absolutely convergent sum. This is the discrete counterpart of Lebesgue integration, developed further in series as a Lebesgue integral against counting measure. ^[ref]

For example, $f(n)=2^{-n}$ on the positive natural numbers has counting measure integral one, by the geometric series. The alternating harmonic series has a finite ordered sum but is not the integral of an integrable function for counting measure: its positive and negative parts both have infinite sums. Absolute convergence is what makes the finite integral independent of enumeration. In particular, the Lp spaces for counting measure on $\mathbb{N}$ are the l-p sequence spaces, with their sums replacing continuous integrals.

Compare three measures on the same Borel sigma-algebra of the real numbers: counting measure $\#$, Dirac measure ${\delta }_1$, and Lebesgue measure $\lambda$.The rational numbers in the last row form a countably infinite set; their Lebesgue measure is zero by countable additivity applied to singletons, even though they are dense in the interval.

These are different answers to different questions: counting measure asks how many points occur, Dirac measure asks whether the selected point occurs, and Lebesgue measure asks how much length occurs. A null set therefore depends on its measure. For counting measure, the only null set is the empty set, so equality almost everywhere is equality everywhere. For ${\delta }_1$, a measurable set is a null set exactly when it misses $1$; for Lebesgue measure, even the infinite set $\mathbb{Q}\cap [0,2]$ is a null set. Integrating an indicator function recovers each table entry through $\int 1_{A}d\mu =\mu (A)$. This lets the same Lebesgue integral framework handle point counts, point evaluation, and geometric length.

A finitely supported permutation fixes every element outside some finite subset. The finitely supported permutations of $\mathbb{N}$ are the union of the finite symmetric groups acting on $\{1,\dots ,k\}$, and hence form a countable set. All permutations of $\mathbb{N}$ form an uncountable set: independently swapping or fixing each pair $(2j-1,2j)$ injects the power set of $\mathbb{N}$ into this larger set.

Foundations of mathematics asks what our objects mean, what we assume about them, and why an argument establishes its conclusion. Set theory gives a common language for collections and functions; mathematical logic makes the structure of statements and deductions precise. A mathematical definition fixes a meaning, an axiom supplies an assumption, and a mathematical proof explains what follows. Separating these roles makes results reusable: once the group axioms are enough for a conclusion, that conclusion applies to every group, regardless of how its members are represented.

The assumptions can change the answer to a familiar calculation. Over the real numbers, $x^2=x$ factors as $x(x-1)=0$, so $x$ is zero or one. The same reasoning holds in any integral domain, because a product can be zero only when a factor is zero. In the ring of integers modulo six, however, $3^2\equiv 3$ and $4^2\equiv 4(\mathrm{mod}6)$: there are four solutions, represented by $0,1,3,4$. The extra solutions are idempotents, and the failed step involves zero divisors. Writing the domain is part of explaining the answer.

This precision also reveals surprising possibilities. A two-dimensional grid of natural numbers is a countable set, while all infinite binary sequences form an uncountable set. The Cantor pairing function supplies a complete enumeration of the first; Cantor's diagonal argument defeats every proposed enumeration of the second. Both arguments are short, yet distinguish two sizes of infinity. The subject's appeal is this ability to turn a vague question into one whose assumptions, construction, and limits can all be inspected.

Lebesgue measure on the real numbers extends interval length: $\lambda ([a,b])=b-a$ for $a\le b$. Its restriction to the Borel sigma-algebra is the unique translation-invariant sigma-finite measure on that sigma-algebra normalized by $\lambda ((0,1])=1$. The full Lebesgue measure is the completion of a measure of this restriction; its domain is the Lebesgue measurable sets. Translation invariance follows by comparing a translated Borel measure on half-open intervals and applying the uniqueness theorem for measures. For the construction and interval properties, see MIT lecture 8.

Every singleton has Lebesgue measure zero: $\{x\}\subseteq [x-\epsilon ,x+\epsilon ]$ gives $0\le \lambda (\{x\})\le 2\epsilon$ for every $\epsilon >0$. Enumerating the countable set $\mathbb{Q}\cap [0,1]$ and applying countable additivity yieldsThus a dense set can be a null set, and a union of null sets indexed by an uncountable set can have positive Lebesgue measure. The distinction explains both the Dirichlet function example and why almost everywhere is weaker than everywhere.

A parabola parametrized by $(t,t^2)$ is in bijection with $\mathbb{R}$ and is an uncountable set. Every affine line meets it in at most two points. A countable family of affine lines could therefore cover only countably many points of this parabola, and cannot cover the plane. More generally, an uncountable curve with finite intersection with every permitted member obstructs a countable covering by those members.

Number the natural numbers from one. If the power set could be enumerated as $A_1,A_2,\dots$, form $D=\{j:j\notin A_j\}$. For each $j$, membership of $j$ in $D$ is opposite to its membership in $A_j$, so $D\ne A_j$. This contradicts completeness of the enumeration. Thus the Cantor diagonal argument proves that the power set is an uncountable set.

For a finite subset $A$, define $b(A)={\sum }_{j\in A}{2}^{j-1}$. This is a nonnegative integer and the map is injective: if two finite subsets differ, let $k$ be their largest differing element. Its contribution $2^{k-1}$ exceeds the sum $1+2+\cdots +2^{k-2}$ of all smaller possible contributions, so their codes differ. There are infinitely many singleton subsets. Hence the countability of finite subsets of a countable set here is countable infinitude.

To treat all bijections, associate to every subset $A\subseteq \mathbb{N}$ the permutation that swaps $2j-1$ and $2j$ when $j\in A$, and fixes both when $j\notin A$. These disjoint pair swaps define a bijection of $\mathbb{N}$. Different subsets give different permutations, so the map from the power set into $X$ is injective. Therefore $X$ is an uncountable set.

Every finitely supported permutation fixes all elements above some $k$. A bijection fixing that tail must permute $\{1,\dots ,k\}$: it cannot send a smaller element into the fixed tail without violating injectivity. There are exactly $k!$ such permutations. Thusis a countable union of finite sets. Enumerate first by $k$, then by one of the finitely many permutations at that $k$; duplicates can be omitted. Infinitely many distinct pair swaps belong to $Y$, so $Y$ is countably infinite. The full family is uncountable, while the finitely supported family is countably infinite.

A countable set is one admitting an injection into $\mathbb{N}$; this includes finite sets and the empty set. An infinite countable set can equivalently be listed in a sequence indexed by $\mathbb{N}$.

For a countable union of countable sets $A={\bigcup }_{i\ge 1}{A}_i$, choose an injection $e_i:A_i\to \mathbb{N}$ for each nonempty $A_i$. Assign $x\in A$ the pair $(i,e_i(x))$, where $i$ is the least index with $x\in A_i$. This is an injection into ${\mathbb{N}}^2$. The pairs are countable by diagonal enumeration; explicitly, with natural numbers starting at one, the Cantor pairing functionmaps them bijectively to $\mathbb{N}$. Composing the two maps proves that the union is countable. Empty members contribute no elements.

To prove uncountability of the power set $\mathcal{P}(\mathbb{N})$, suppose all subsets could be listed as $A_1,A_2,\dots$. DefineFor every $n$, $D$ differs from $A_n$ on whether it contains $n$. Thus $D$ is missing from the supposedly exhaustive list. This Cantor diagonal argument proves $\mathcal{P}(\mathbb{N})$ is uncountable.

For increasing functions in the question's non-strict sense, encode every subset $A\subseteq \mathbb{N}$ bywhere the value at zero is only a convenient auxiliary convention. ThenEach $f_A$ is even strictly increasing, hence is a nondecreasing function as required, and its successive differences recover $A$ uniquely. This is an injection from the uncountable power set into the requested collection. Therefore the increasing functions $\mathbb{N}\to \mathbb{N}$ form an uncountable set.

For a decreasing function in the question's sense, $f$ is a nonincreasing function with positive integer values. Each strict decrease lowers its value by at least one, so there can be at most $f(1)-1$ strict decreases. There is consequently a final drop, after which the function is constant. Every such function is determined by a finite initial list whose final value repeats forever. The set of all these lists is contained ina countable union of countable sets, hence countable by the result just proved. Thus the decreasing functions $\mathbb{N}\to \mathbb{N}$ form a countable set. These contrasting cardinalities of monotone natural-number functions come from the absence of an upper bound for increasing values and the finite number of drops available to decreasing natural-number values. If the natural numbers include zero, the same proof uses the bound $f(1)$ instead.

Suppose all infinite binary sequences could be listed as ${ϵ}^{(1)},{ϵ}^{(2)},\dots$, where ${ϵ}^{(j)}=({ϵ}_1^{(j)},{ϵ}_2^{(j)},\dots )$. Define another binary sequence by $d_j=1-{ϵ}_j^{(j)}$. It differs from the $j$th listed sequence at its $j$th entry, so it is absent from the list. This contradiction is Cantor's diagonal argument, proving thatTo transfer this result to $[0,1]$, map a binary sequence toThis lies in $[0,1]$ because ${\sum }_{j\ge 1}2/3^j=1$. If two sequences first differ at index $j$, with ${ϵ}_j=1$ and ${\eta }_j=0$, thenThus $f$ is an injection, avoiding the ambiguous expansions that would arise from unrestricted binary digits in base two. An injection from an uncountable set into $[0,1]$ proves that $\boxed{[0,1]\text{ is uncountable}}$.

For $\Sigma (\mathbb{Z})$, a nondecreasing sequence bounded above can take only finitely many integer values, all lying between its first term and an integer upper bound. Every strict increase raises its value by at least one, so only finitely many strict increases occur. It is therefore eventually constant. Every such sequence has the formfor some finite list of integers. The set of finite integer lists is a countable set: at stage $j$, list the tuples of length at most $j$ whose entries have absolute value at most $j$, omitting earlier duplicates. Each stage is finite and every finite tuple occurs at some stage. Constant sequences give an injection of $\mathbb{Z}$ into the collection, soThis is the discrete-order phenomenon that bounded nondecreasing integer sequences are eventually constant.

For $\Sigma (\mathbb{Q})$, use a different encoding, into rational partial sums:Each $s_n$ is a rational number, the sequence is nondecreasing, and $s_n\le 1/2$. If two binary inputs first differ at $j$, their $j$th partial sums differ by $3^{-j}$, so their output sequences differ. This defines an injection of the uncountable binary-sequence set into $\Sigma (\mathbb{Q})$. Thus bounded nondecreasing rational sequences are uncountable. Finally, every such rational sequence is also an admissible real sequence, so inclusion into $\Sigma (\mathbb{R})$ is injective. ConsequentlyBoundedness and monotonicity force eventual constancy for integer values, but not for rational or real values; countability of the set of possible individual terms does not imply countability of all infinite sequences of those terms.

Use the parabola obstruction to countable line coverings. The curveis in bijection with the real line and hence is an uncountable set. A vertical line meets $\mathcal{P}$ in one point. A nonvertical line $y=ax+b$ meets it only where $t^2-at-b=0$, so it meets $\mathcal{P}$ in at most two points.

If countably many lines covered the plane, their intersections with $\mathcal{P}$ would cover $\mathcal{P}$. That would express $\mathcal{P}$ as a countable union of countable sets, indeed of sets with at most two elements, contradicting its uncountability. Therefore no countable collection of lines covers the plane.

For the cardinality of integer-periodic function spaces, fix a positive period $n$ first. A periodic function $\mathbb{Z}\to \mathbb{Z}$ with that period is completely and uniquely determined by its $n$ values at $0,\dots ,n-1$, so this class is in bijection with ${\mathbb{Z}}^n$. The integers are a countable set, and repeated pairing shows that a finite Cartesian product of countable sets is countable. Taking the union over positive $n$ and using the countable union of countable sets proves that the integer-domain periodic functions form a countable set.

For the rational domain, even period one leaves infinitely many independent choices. Let $q_k=1/(k+2)$ for $k\in {\mathbb{N}}_0$; these are distinct members of $\mathbb{Q}\cap [0,1)$. For every subset $A\subseteq {\mathbb{N}}_0$, defineThe fractional part is unchanged by adding one, so $f_A$ is an integer-valued periodic function on $\mathbb{Q}$. Distinct subsets give distinct functions because $f_A(q_k)$ records whether $k\in A$. Thus the uncountable power set of ${\mathbb{N}}_0$ injects into these functions. The rational-domain periodic functions form an uncountable set. The difference is that $\mathbb{Z}$ has only finitely many residue classes modulo a fixed integer period, whereas $\mathbb{Q}$ has infinitely many.

Use uncountability by interleaving prescribed binary coordinates. For each arbitrary binary sequence $b=(b_k{)}_{k\ge 1}$, define another binary sequence byThere are infinitely many zero coordinates, namely $3k-2$, so $x\in X$. There are also infinitely many coordinates agreeing with the prescribed binary expansion, namely $3k-1$, so $x\in Y$. The coordinates $3k$ recover $b$, making this map an injection of the uncountable set of all binary sequences into $Y$. If $Y$ were a countable set, composing with an injection into $\mathbb{N}$ would make all binary sequences countable, contrary to part (i). Therefore $\boxed{Y\text{ is uncountable}.}$ The construction works for every prescribed binary sequence $(a_n)$; no special distribution property of the digits of $\sqrt{2}$ is needed.

Suppose $f:S\to \mathcal{P}(S)$ were a surjective function. Form the subsetSince $D$ belongs to the power set, surjectivity would give $D=f(d)$ for some $d\in S$. But then $d\in D$ holds if and only if $d\notin f(d)=D$, a contradiction. Thus no such function is surjective, and in particular there is no bijection from $S$ to its power set. This is Cantor theorem; the argument also applies when $S$ is empty.

For infinite binary sequences, use the bijectionwith $\mathcal{P}(\mathbb{N})$, taking $\mathbb{N}=\{1,2,\dots \}$. Conversely, a subset determines its sequence of membership indicators. The power set is infinite, since it contains all singletons, and Cantor theorem rules out a bijection with $\mathbb{N}$. Hence it is an uncountable set, as is the set of infinite binary sequences. Equivalently, a proposed enumeration $(x_n^{(j)}{)}_{n\ge 1}$ is defeated by the sequence $y_j=1-x_j^{(j)}$, which differs from its $j$th listed sequence at position $j$. This is the Cantor diagonal argument.

Partition the enumeration of $B$ into the pairs $\{b_{2j-1},b_{2j}\}$, for $j\ge 1$. An infinite binary sequence $x$ determines a bijection $h_x:B\to B$: leave the $j$th pair fixed when $x_j=0$, and interchange its two elements when $x_j=1$. Each element stays in its own pair, so this function is a bijection, indeed its own inverse.

Different binary sequences give different bijections, since a changed bit changes the action on the corresponding pair. We have therefore embedded an uncountable set into $S_3$. Hence $S_3$ is uncountable, proving uncountability of permutations of a countably infinite set.

Again let $A=\{a_1,\dots ,a_m\}$ with $m>1$, and enumerate $B=\{b_1,b_2,\dots \}$. For each infinite binary sequence $x=(x_j{)}_{j\ge 1}$, define a function $g_x$ byThe first $m$ values make every $g_x$ a surjective function, while the remaining values recover $x$ uniquely. Hence $x\mapsto g_x$ is an injective function from the uncountable set of binary sequences into $S_2$. This proves $S_2$ is an uncountable set, an instance of uncountability of surjections onto a nontrivial finite set.

False. Take $x=\mathcal{P}(\omega )$, the power set of the first infinite ordinal $\omega$. Every subset of $\omega$ has rank at most $\omega$, and an infinite cofinal subset has rank exactly $\omega$, sowhich is a countable ordinal. But Cantor theorem shows that $\mathcal{P}(\omega )$ is an uncountable set.

Suppose all functions $\mathbb{N}\to \mathbb{N}$ could be listed as $f_1,f_2,\dots$. DefineThen $g$ differs from $f_n$ at $n$ for every $n$, so it is absent from the list. This Cantor's diagonal argument proves that ${\mathbb{N}}^{\mathbb{N}}$ is an uncountable set.

There are uncountably many physically distinct one-qubit unitaries. Part (ii) would require an orthogonal program state for every one, whereas a $K$-qubit register has dimension only $2^K$. This contradiction is the no-programming theorem, so no deterministic gate satisfying (PROG) exists.