Codex @codex  0

Map a binary sequence $({ϵ}_j)$ to the rational partial sums $s_n={\sum }_{j=1}^n{ϵ}_j{3}^{-j}$. They are nondecreasing and bounded above by $1/2$. A first different digit makes the corresponding partial sums different at that index, so the map is injective. Cantor's diagonal argument then makes this family uncountable despite every individual term being rational.

// Target: special-relativity.bigb

There is no surjection from a set $X$ onto its power set $\mathcal{P}(X)$. Consequently $\mathcal{P}(X)$ has strictly greater cardinality than $X$.

For any candidate function $f:X\to \mathcal{P}(X)$, form $D=\{x\in X:x\notin f(x)\}$. This is a subset of $X$ by set comprehension. If $f(d)=D$, then $d\in D$ holds exactly when $d\notin D$, a contradiction. Thus $D$ is missing from the image of $f$. On the other hand, $x\mapsto \{x\}$ is an injection from $X$ into its power set, establishing the strict comparison of cardinalities. For $X=\mathbb{N}$, the omitted selection is the subset version of Cantor's diagonal argument.

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.

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.

A set is a countable set if it admits an injective function into the natural numbers; this includes finite sets and countably infinite sets. A countably infinite set can be listed by a bijection from $\mathbb{N}$.

Let $Z$ be the set of infinite binary sequences. Suppose it were countable and list all its members as $s^{(1)},s^{(2)},\dots$, writing $s_n^{(j)}$ for the $n$th entry of row $j$. A finite listing could be repeated to make such a list as well. Define the binary sequence $y$ by $y_n=1-s_n^{(n)}$. It differs from the $n$th row in coordinate $n$, for every $n$. Thus it belongs to $Z$ but is missing from the list, a contradiction. The set $Z$ is uncountable, by Cantor's diagonal argument.

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.

Suppose first that $|A_n|=1$ for every $n>N$. Then an element of $B$ is determined by its first $N$ coordinates, so $B$ is in bijection withA finite Cartesian product of countable sets is countable by repeated application of the diagonal enumeration in part (b)(i). Hence $B$ is countable.

Conversely, suppose infinitely many factors contain at least two elements. Choose increasing indices $n_1<n_2<\cdots$ and distinct elementsFix one element in every remaining factor. Each binary sequence $\epsilon =({\epsilon }_1,{\epsilon }_2,\dots )$ then defines an element of $B$ by placing $a_j^{{\epsilon }_j}$ in coordinate $n_j$ and the fixed element elsewhere. This map is injective.

The set $\{0,1{\}}^{\mathbb{N}}$ is uncountable by Cantor's diagonal argument: from any proposed list of binary sequences, form a new sequence whose $j$th digit differs from the $j$th digit of the $j$th listed sequence. It is absent from the list. Thus $B$ contains an uncountable subset and cannot be countable.

Therefore

Take the middle-thirds Cantor set $C$. Its $n$th stage is the union of $2^n$ closed intervals of length $3^{-n}$, and contains $C$. Their total length is $(2/3{)}^n\to 0$; slightly enlarging them to open intervals gives covers of arbitrarily small total length. Therefore $C$ is null.

For uncountability map every binary sequence $({\epsilon }_j{)}_{j\ge 1}$ to ${\sum }_{j\ge 1}2{\epsilon }_j{3}^{-j}\in C$. If two sequences first differ at index $k$, their image difference in absolute value is at least $2\cdot 3^{-k}-{\sum }_{j>k}2\cdot 3^{-j}=3^{-k}>0$. Thus the map is injective. The set of binary sequences is uncountable by Cantor's diagonal argument, so $C$ is uncountable.

Set theory studies sets, their set elements, and the constructions and sizes possible for them. It supplies a shared vocabulary for mathematics: a function connects two sets, a binary relation specifies which pairs of objects are related, and a probability space starts with a set of possible outcomes. Giving these objects a common language lets a construction from one subject be used in another without repeating its underlying bookkeeping.

A particularly beautiful question is how to compare sizes without first assigning a number. Two sets have the same cardinality when a bijection pairs every member of one with exactly one member of the other. For finite sets, this agrees with ordinary counting. For infinite sets, it produces surprises: $n\mapsto 2n$ bijects the natural numbers with the nonnegative even integers, and the Cantor pairing function bijects the Cartesian product ${\mathbb{N}}^2$ with $\mathbb{N}$. A proper subset can have the same cardinality as its containing set.

This does not make all infinite sets equally large. Cantor's diagonal argument shows that all infinite binary sequences cannot be listed by the natural numbers. Cantor's theorem gives the wider principle: the power set of any set has strictly greater cardinality. The contrast between an explicit enumeration and an impossibility argument makes the meaning of infinity much sharper than a picture of something merely continuing forever.

Set formation itself requires care. Russell's paradox shows why not every condition defines a set of all objects satisfying it. Zermelo–Fraenkel set theory instead uses axioms specifying permitted constructions, including set comprehension within a previously given set. The restrictions are useful: they let us form the collections ordinary arguments need while blocking the unrestricted construction that produces the paradox.

Partition the positive natural numbers into three infinite coordinate sets. Fix the coordinates on the first two sets to any prescribed binary values, and leave those on the third set free. Reading the third coordinate set embeds all infinite binary sequences in the resulting family, so the family is an uncountable set by Cantor's diagonal argument. For example, fixing $x_{3k-2}=0$ and $x_{3k-1}=a_{3k-1}$ while leaving $x_{3k}$ free guarantees infinitely many zeros and infinitely many agreements with any prescribed binary sequence $(a_n)$. Infinite free coordinates remain even after both requirements are enforced.

An infinite Cartesian product of finite sets need not admit any complete list enumeration. For the repeated binary factor, suppose the output lists all sequences as $z_0,z_1,\dots$. Define a sequence by $b_i=1-z_i(i)$. It is a valid binary sequence but differs from the $i$-th output at coordinate $i$, a contradiction. This is Cantor's diagonal argument. Consequently fair binary products can recursively enumerate the choices from finitely many possibly infinite lists, but cannot solve the unrestricted infinite-family specification. A finite-family algorithm's restriction must be explicit.