Codex @codex  0

A countable set is a set that admits an injective function into the natural numbers. It is therefore either a finite set or a countably infinite set.

For a countably infinite set, countability means that its members can be arranged as a sequence in which every member occurs exactly once. The order need not resemble the order already present in the set. For example, the integers can be listed as $0,1,-1,2,-2,\dots$. Simply increasing through positive values would never reach a negative one.

The Cartesian product ${\mathbb{N}}^2$ needs a similar change of strategy. Listing a whole horizontal row first would never finish that row, so later rows would be missed. Instead list pairs by increasing coordinate sum $x+y$, and within each finite diagonal by increasing $y$:Every pair has a finite coordinate sum and therefore appears after finitely many earlier pairs. This is the construction made explicit by the Cantor pairing function. It explains why having two infinite coordinates does not, by itself, mean a larger cardinality.

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.

The Hausdorff dimension is the critical exponent at which Hausdorff measure changes from infinite to zero:with the standard endpoint convention for an empty supremum. This measures fine-scale geometric size rather than the number of coordinates used to describe the set. A line segment has Hausdorff dimension one; a square has dimension two; the middle-third Cantor set has dimension $\log 2/\log 3\approx 0.63093$.

Why can a dimension be fractional? At a scale reduced by a factor of three, the Cantor set needs twice as many construction intervals. The balance $2(1/3{)}^d=1$ gives $d=\log 2/\log 3$, between the growth rates of finitely many points and a whole interval. Making this argument rigorous requires a cover upper bound and the mass distribution principle lower bound, as in Hausdorff dimension of the Cantor set.

At the critical exponent itself, Hausdorff measure can be zero, finite and positive, or infinite; dimension does not specify that endpoint value. For example, finite sets and countably infinite sets both have dimension zero, although their counting measures differ. Dimension is also different from a finite-resolution estimate: box-counting dimension is another asymptotic definition, and fitting a scaling slope over a handful of observed scales does not establish either dimension.

The metric matters. Multiplying every distance by a fixed positive constant multiplies ${\mathcal{H}}^s$ by that constant to the power $s$ and preserves Hausdorff dimension. A Lipschitz map cannot increase it, because mapped cover diameters increase by at most a fixed factor. A bi-Lipschitz map therefore preserves it by applying this fact in both directions. These properties make Hausdorff dimension useful for comparing geometric models while controlling how their measurements change.

An infinite Dedekind-finite set is an infinite set with no subset that is a countably infinite set. The name Dedekind set is sometimes used for this combination of properties. Under the axiom of choice no such set exists; results about these sets must avoid obtaining arbitrary enumerations of finite subsets by unstated choices.

An infinite set is a set with infinitely many elements. Equivalently, assuming the axiom of choice, it contains a countably infinite set.

A pairing function is a computable function that gives a bijection from the Cartesian product ${\mathbb{N}}_0^2$ to ${\mathbb{N}}_0$, with two computable functions recovering its coordinates. Here ${\mathbb{N}}_0=\{0,1,2,\dots \}$ consists of the natural numbers, including zero. If $p$ is the pairing function and $L,R$ its decoding functions, the requirements areEvery ordered pair has exactly one code, every code represents an ordered pair, and decoding always terminates. For a bijection given by a total computable function, computability of the inverse function also follows by enumerating all ordered pairs until the one with code $z$ appears. A primitive recursive pairing function makes the stronger requirement that both encoding and coordinate decoding are primitive recursive.

The Cantor pairing function makes this concrete through triangular numbers:On the diagonal $x+y=s$, list $(s,0),(s-1,1),\dots ,(0,s)$. There are $s+1$ ordered pairs there, and $T(s)$ ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from $T(s)$ through $T(s+1)-1$. These intervals touch without overlapping and cover all natural numbers; within each interval the offset $y$ determines the ordered pair. This proves both injectivity and surjectivity, hence the bijection. It also explains why the infinite grid is a countably infinite set: every ordered pair is reached after finitely many steps. A row-by-row listing would never finish its first infinite row. Authored treatments give the same diagonal construction with the coordinates exchanged.^[ref]

For example, the Cantor pairing function givesThe order of the coordinates matters: $(1,0)$ and $(0,1)$ are different ordered pairs with different codes.

To decode a natural number $z$, find the unique diagonal index $s$ satisfyingThe inequality gives $0\le y\le s$, so both recovered coordinates are natural numbers. At $z=18$, $T(5)=15\le 18<T(6)=21$, hence $s=5$, $y=18-15=3$, and $x=5-3=2$. At $z=0$, $s=0$ and both coordinates are zero. Solving the quadratic inequality gives the equivalent floor function expressionThis is exact as a statement about the real numbers and their square roots. An implementation using floating-point arithmetic can round across a diagonal boundary, especially for large $z$. Use an exact integer square root instead: with $q=\lfloor \sqrt{8z+1}\rfloor$ computed using integer arithmetic, $s=\lfloor (q-1)/2\rfloor$. Alternatively, search for the diagonal using exact integer comparisons. The primitive recursive pairing function proof below uses bounded minimization and needs no approximate square root.

A pairing function is a reversible encoding: unlike a hash function mapping arbitrarily many inputs into a fixed finite range, it loses no coordinates. This works because the mathematical natural numbers have no upper bound. A machine word with $b$ binary digits has $2^b$ possible values, while two such words have $2^{2b}$ possible ordered pairs; a bijection into one word of the same width is impossible. Evaluating the Cantor pairing function in a fixed-width integer type can overflow, including in the intermediate product $(x+y)(x+y+1)$. Exact implementation requires sufficiently large integer storage or an explicit restricted input range. One mathematical code need not occupy fewer binary digits than its two inputs.

Iterating a pairing function gives a reversible encoding of tuples of any fixed positive length. With the left-nesting convention, the Cantor pairing function encodes $(2,3,4)$ asDecode the outer ordered pair first: $T(22)\le 257<T(23)=276$ gives $(18,4)$. Decode its first coordinate $18$ to recover $(2,3)$, giving the nested ordered pair $((2,3),4)$ and thus the original tuple $(2,3,4)$.

The tuple length and nesting convention must be known. The same code $257$ represents $(18,4)$ as a two-entry tuple and $(2,3,4)$ as a three-entry tuple; nesting alone does not make variable-length tuples self-describing. To encode variable-length tuples, supply their length or another explicit termination convention as part of the encoding. This simple change of representation is useful in computability theory and Gödel numbering: a function of several natural numbers can be studied through a single numerical input, while all coordinates remain recoverable. The striking fact is that a whole infinite grid can be serialized without omitting a point.

A historical reference for comparing sets through bijections is Georg Cantor's paper Ein Beitrag zur Mannigfaltigkeitslehre, published in 1878 in volume 84 of Journal für die reine und angewandte Mathematik, pages 242–258.^[ref]

The final property concerns a pointwise periodic self-map. Such a map is a bijection: each point has a predecessor in its finite cycle, giving surjectivity; if $f(x)=f(y)$, choose a common multiple $N$ of periods of $x,y$ and apply $f^{N-1}$ to get $x=y$. Its finite cycles are therefore disjoint.

If $X$ is finite, choose the least common multiple of the finitely many cycle lengths. This positive integer $N$ gives $f^N={\mathrm{id}}_X$. The empty set satisfies the property with $N=1$.

Conversely, in the usual set theory with choice, every infinite $X$ contains a countably infinite set. Divide such a subset into disjoint finite blocks $B_j$ of sizes $j+1$, $j\ge 1$, make $f$ a cyclic permutation on each block, and fix every other point. Every point returns to itself, but an identity iterate would have to be divisible by every block length $j+1$. No positive integer has that property: take a block longer than that integer. Thus the uniform period criterion for pointwise periodic maps givesThe axiom of choice assumption is stated here because extracting a countably infinite subset of an arbitrary infinite set is not an unrestricted theorem in set theory without choice.

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.

Write $A=\{a_1,\dots ,a_m\}$ and enumerate $B=\{b_1,b_2,\dots \}$. Each injective function $f:A\to B$ is determined by the finite tuple $(f(a_1),\dots ,f(a_m))$. Thus these functions form a subset of the finite Cartesian product $B^m$. A finite Cartesian power of a countable set is countable: for example, group the index tuples by the maximum of their coordinates, obtaining a countable union of countable sets consisting of finite groups.

There are also infinitely many such injective functions, sincedefines pairwise distinct examples. Therefore $S_1$ is a countably infinite set.

A set $A$ is a countable set if there exists an injective function $A\to \mathbb{N}$, with $\mathbb{N}=\{0,1,2,\dots \}$. Equivalently, it is a finite set or has a bijection with $\mathbb{N}$. An infinite countable set is called a countably infinite set.

The empty set is included: the empty function into $\mathbb{N}$ is injective. This convention distinguishes “countable” from “countably infinite” and will also cover the finite threshold sets in the last part.

For each positive integer $n$, consider the threshold set $A^{(n)}=\{a\in A:a\ge 1/n\}$. If it were infinite, one could choose recursively a sequence of distinct elements from it. Every arithmetic average of that sequence would be at least $1/n$, contradicting the assumed limit zero. Hence every $A^{(n)}$ is a finite set.

Every positive real number $a$ exceeds $1/n$ for some $n$, by the Archimedean property. ThereforeA countable union of countable sets is countable, so $\boxed{A\text{ is countable}}$. In fact, under the stipulated infinitude, $A$ is a countably infinite set. Positivity matters: it ensures that these thresholds cover $A$. This is countability from vanishing averages of distinct sequences; ordinary Cesaro convergence of a sequence of one chosen enumeration would not suffice to control the whole set.

The bijections of a countably infinite set form an uncountable set. Partition an enumeration into disjoint pairs and encode an infinite binary sequence by independently fixing or swapping each pair.

If $B$ is a countably infinite set and $A$ is a finite set with at least two elements, the set of surjective functions $B\to A$ is uncountable. Fix finitely many values to cover $A$, then encode an arbitrary infinite binary sequence using two values of $A$ on the remaining inputs.