Codex @codex  0

The axiom of countable choice allows one to choose an element from each member of a countable family of nonempty sets. It is a restricted form of the axiom of choice. In the usual proof that a countable union of countable sets is countable, it suffices to choose one enumerating injection for each set; if those enumerations are already supplied, that proof requires no further choice.

For fixed positive integer period $n$, integer-valued periodic functions on $\mathbb{Z}$ are in bijection with ${\mathbb{Z}}^n$ and hence form a countable set. Their union over periods is a countable union of countable sets. In contrast, period-one integer-valued functions on $\mathbb{Q}$ can prescribe arbitrary binary values on its infinitely many distinct classes modulo $\mathbb{Z}$. The power set of a countably infinite set injects into them, proving uncountability.

If every sequence of distinct elements of a positive-real set $A$ has arithmetic averages tending to zero, then $A$ is a countable set. For each positive integer $n$, the threshold set $\{a\in A:a\ge 1/n\}$ must be finite: an infinite sequence inside it would have averages at least $1/n$. The Archimedean property makes $A$ their union, so the countable union of countable sets theorem applies. The hypothesis concerns every distinct-element sequence, not merely one enumeration.

A countably generated abelian group is a countable set. Given generators $g_1,g_2,\dots$, every element is ${\sum }_{j=1}^m{a}_j{g}_j$ for some $m$ and some $a_j\in \mathbb{Z}$. For each fixed $m$, this is the image of a finite cartesian product of copies of the countable set $\mathbb{Z}$; taking a countable union of countable sets proves the assertion. The same proof works for a module generated by a countable set over any countable ring.

For every fixed positive integer $d$, the polynomial ring with integer coefficients in $d$ indeterminates is countably infinite. Polynomials of bounded total degree have only finitely many possible monomials, so they are encoded by a finite Cartesian power of the integers. Taking a countable union of countable sets over degree bounds proves countability; constant polynomials supply an infinite subset. Nonzero one-variable polynomials have finitely many real roots, so the real algebraic numbers form a countable set as well.

Every countable set $B$ of real numbers is contained in a countable set closed under taking all real roots of a polynomial with coefficients in that set. Let $\varphi (A)$ consist of these roots of a polynomial, excluding the zero polynomial. There are countably many finite coefficient lists over a countable set, and each nonzero polynomial has finitely many roots of a polynomial; hence $\varphi (A)$ is countable. Define $B_0=B$ and $B_{n+1}=B_n\cup \varphi (B_n)$. The countable union of countable sets theorem shows that $X={\bigcup }_n{B}_n$ is countable. Every finite coefficient list in $X$ belongs to one stage $B_N$, so its real roots of a polynomial belong to $B_{N+1}\subseteq X$. Retaining $B_n$ at the next stage matters: $\varphi (A)$ need not contain $A$.

For a countable fixed point of a normal ordinal function, first show that $\Phi$ maps every countable ordinal to a countable ordinal. Use transfinite induction below ${\omega }_1$. The zero case is assumed, and the successor case is the stated preservation property. If $\lambda$ is a countable limit, normality gives $\Phi (\lambda )={\bigcup }_{\alpha <\lambda }\Phi (\alpha )$, a countable union of countable sets, hence countable. This countable-union step is where axiom of countable choice is used; the assumed axiom of choice supplies it.

Now set ${\alpha }_0=0$, ${\alpha }_{n+1}=\Phi ({\alpha }_n)$. The preceding result makes every term countable, and the domination proved earlier makes the sequence nondecreasing. If it ever stabilizes, it already gives the required fixed point. Otherwise $\alpha ={\sup }_{n<\omega }{\alpha }_n$ is a countable nonzero limit, using axiom of countable choice again for countability of the union. Its defining sequence is cofinal, so monotonicity and continuity giveApply this to $\Phi (\alpha )={\omega }^{\alpha }$. This is normal, begins at $1$, and ${\omega }^{\alpha +1}={\omega }^{\alpha }\cdot \omega$ is countable whenever ${\omega }^{\alpha }$ is countable. Thus a countable $ϵ$ satisfies $\boxed{ϵ={\omega }^{ϵ}}$. Starting at zero gives the familiar tower sequence $0,1,\omega ,{\omega }^{\omega },\dots$, whose supremum is ${ϵ}_0$. The finite recursion, ordinal identities and fixed-point continuity do not require choice; the uses of choice above concern countable unions of countable ordinals.

A set is countable if it is finite or admits an injection into the natural numbers; an infinite countable set can equivalently be listed as a sequence. Let $A={\bigcup }_{i\ge 1}{A}_i$ with each $A_i$ countable. Choose an enumeration of each nonempty $A_i$, allowing repetition if it is finite. List the pairs $(i,j)\in {\mathbb{N}}^2$ in successive finite diagonals of constant $i+j$ and output the $j$th member of $A_i$. This lists every member of $A$, so $A$ is countable; empty sets contribute nothing, and repetitions can be removed by retaining first occurrences. This is the countable union of countable sets theorem, in the usual setting with axiom of countable choice for selecting the enumerations.

Each positive-length interval $J_i$ has a nonempty interior containing a rational number by the density of the rational numbers. Fix one enumeration of the rational numbers and let $q_i$ be its first member in the interior of $J_i$. Disjointness gives $i\ne j\Rightarrow q_i\ne q_j$, so $i\mapsto q_i$ is an injection of $I$ into a countable set. Hence $I$ is countable. This proof of the countability of disjoint positive-length intervals uses a fixed enumeration and needs no arbitrary simultaneous choice of rationals.

Use the inclusive convention: a set is countable if it admits an injective function into $\mathbb{N}=\{1,2,\dots \}$. This includes every finite set and the empty set. If $j:X\to \mathbb{N}$ is injective and $Y\subseteq X$, its restriction to $Y$ is still injective, proving directly that every subset of a countable set is countable.

Enumerate pairs by diagonals. The positive-integer Cantor pairing functionis a bijection ${\mathbb{N}}^2\to \mathbb{N}$: on the diagonal $a+b-2=d$, its values are $d(d+1)/2+1$ through $(d+1)(d+2)/2$, each once, and these consecutive blocks partition $\mathbb{N}$. This proves countability without assuming any product theorem.

For a sequence of countable sets $X_1,X_2,\dots$, choose injections $j_i:X_i\to \mathbb{N}$. For $x$ in their union, let $i(x)$ be the least index containing $x$. The mapis injective: its encoded index and the injective within-set code recover $x$. Thus a countable union of countable sets is countable. Selecting the injections for an arbitrary given family uses the usual axiom of countable choice; when the encodings are supplied, the displayed construction is entirely explicit.

For finite Cartesian powers, start with the identity injection on $\mathbb{N}$ and recursively encode $(a_1,\dots ,a_n)$ as $\pi (j_{n-1}(a_1,\dots ,a_{n-1}),a_n)$. This proves that ${\mathbb{N}}^n$ is countable for every positive integer $n$ and is the constructive proof of the finite Cartesian power of a countable set property.

For each positive integer $m$, let $P_m$ consist of the functions for which $m$ is a period. Restriction to the residues $0,1,\dots ,m-1$ is a bijection $P_m\to {\mathbb{N}}^m$: any tuple extends uniquely to all of $\mathbb{Z}$ by taking residues modulo $m$, including negative arguments. Hence $P_m$ is countable. Every periodic function belongs to some $P_m$, soThere is no need to assume the chosen period is minimal; multiple descriptions only create overlap, which does not invalidate the union argument. This is an instance of the cardinality of integer-periodic function spaces principle.

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.

A set is countable if it admits an injection into the natural numbers; this includes finite sets and the empty set. Use ${\mathbb{N}}_0=\{0,1,2,\dots \}$ for the enumeration. The Cantor pairing functionis a bijection ${\mathbb{N}}_0^2\to {\mathbb{N}}_0$. Indeed, on the diagonal $i+j=s$, its values are the consecutive integers from $s(s+1)/2$ through $s(s+1)/2+s$. These intervals are disjoint, and the next starts one beyond the preceding endpoint. Every nonnegative integer therefore determines exactly one diagonal $s$, then exactly one $j$, and finally $i=s-j$. If one's convention starts the natural numbers at one, translate both coordinates by one. Thus $\mathbb{N}\times \mathbb{N}$ is a countable set.

For countable sets $X,Y$, choose injections $e_X:X\to {\mathbb{N}}_0$ and $e_Y:Y\to {\mathbb{N}}_0$. The map $(x,y)\mapsto \Pi (e_X(x),e_Y(y))$ is an injection, proving their Cartesian product is countable. Repeating this proves that every finite Cartesian power of a countable set is countable.

For a sequence of countable sets $X_n$, choose an injection $e_n:X_n\to {\mathbb{N}}_0$ for each $n$. For $x\in {\bigcup }_n{X}_n$, let $n(x)$ be the least index containing $x$. The mapis an injection: its value recovers $n(x)$ and then $x$. This proves the countable union of countable sets theorem. Selecting all $e_n$ uses the usual axiom of countable choice; if enumerations are already supplied, the construction itself needs no additional choices.

For a countable set $A$, the polynomials of polynomial degree at most $d$ with coefficients in $A$ are described by coefficient tuples in $A^{d+1}$. The finite Cartesian power of a countable set result makes this a countable set. Taking the union over $d\ge 0$ shows there are only countably many such polynomials altogether; restricting to the nonzero polynomials preserves countability.

A nonzero polynomial of polynomial degree $d$ has at most $d$ distinct roots of a polynomial. To see the bound, a root $r$ gives the factorization $P(x)=(x-r)Q(x)$ by the factor theorem, and each other root is a root of $Q$, whose degree is $d-1$; induction starts with a nonzero constant, which has no roots. Thus $\varphi (A)$ is a countable union of countable sets, each of them finite, and is a countable set.

Starting with the given countable set $A_0$, mathematical induction now shows that every $A_n=\varphi (A_{n-1})$ is countable. A final application of the countable union of countable sets theorem givesThis countability argument does not require that the sequence of sets be increasing.

To obtain a countable closure under real polynomial roots, start with $B_0=\{1,\pi \}$ and explicitly retain previous elements at each stage:Part (b) shows that $\varphi$ takes countable sets to countable sets; consequently all $B_n$ and then $X$ are countable by the countable union of countable sets theorem. Also $1,\pi \in X$.

For a nonzero polynomial $P(t)=c_0+\cdots +c_d{t}^d$ with all $c_j\in X$, choose stages $n_j$ containing the finitely many coefficients and put $N={\max }_j{n}_j$. The inclusions $B_n\subseteq B_{n+1}$ ensure that every coefficient belongs to $B_N$. Every real root of a polynomial $P$ therefore belongs to $\varphi (B_N)\subseteq B_{N+1}\subseteq X$. This countable set $X$ has all the required properties. Retaining $B_n$ explicitly avoids assuming the generally false inclusion $A\subseteq \varphi (A)$: for example, $\varphi (\{1\})$ does not contain $1$, since a nonzero polynomial all of whose coefficients are one is positive at $1$.

We work in the ambient theory ZFC for this question. Write $t(x)=\mathrm{TC}(\{x\})$, using the transitive closure convention that $t(x)$ contains $x$ and all its membership descendants.

First construct a set containing exactly the intended objects. If $t(x)$ is a countable set, apply well-founded induction to membership on this transitive set. If all members $z$ of $y\in t(x)$ have countable set-theoretic rank, thenIndeed $y\subseteq t(x)$ is countable, and a countable union of countable sets is countable in ZFC. The induction therefore gives $\mathrm{rank}(x)<{\omega }_1$. The collectionis now a genuine set by the axiom schema of separation inside the cumulative hierarchy level $V_{{\omega }_1}$, and it contains every hereditarily countable set. It is a transitive set, since $y\in x$ implies $t(y)\subseteq t(x)$.

If $a$ is a countable subset of $C$, thenThe right side is countable, so $a\in C$. Thus $C$ has countable-subset closure. This proves existence of a set with the required closure before taking any intersection.

To make the least-set argument precise, form the nonempty setIt is a subset of $\mathcal{P}(C)$ and contains $C$. Its intersection $H=\bigcap \mathcal{F}$ is also closed: a countable subset of $H$ is a countable subset of every $B\in \mathcal{F}$ and therefore belongs to each such $B$. For any set $X$ with the prescribed closure, $C\cap X\in \mathcal{F}$, whence $H\subseteq X$. This is leastness among all such sets, not just among subsets of $C$.

Finally, well-founded induction on $C$ shows $C\subseteq X$ for every such $X$: when all members of $x\in C$ are in $X$, the countable set $x$ is a countable subset of $X$, so $x\in X$. Hence $H=C$, proving that the definition gives precisely

For the cardinal bound, code the entire countable membership ancestry. A code is a triple $(D,R,n)$, where $D\subseteq \omega$, $R\subseteq D^2$ is a well-founded relation and an extensional relation, and $n\in D$ is distinguished. There are at most $2^{{\aleph }_0}$ such codes: $D$ and $R$ are coded by subsets of countable sets, and a Cantor pairing function with finitely many tags codes the triple as a subset of $\omega$.

The well-founded recursiondefines its collapse, as in the Mostowski collapse theorem. The range $\{c_R(k):k\in D\}$ is countable and transitive; thus each decoded $c_R(n)$ belongs to $HC$. Conversely, for $x\in HC$, choose a bijection $e:D\to t(x)$ and the point $n$ with $e(n)=x$. Set $lRk$ exactly when $e(l)\in e(k)$. Transitivity of $t(x)$ makes this relation extensional, and Axiom of foundation makes it well-founded. The recursion then gives $c_R(k)=e(k)$, so this code decodes to $x$.

We have a surjection from a set of at most continuum many codes onto $HC$. Using the permitted axiom of choice, well-order the codes and assign each $x$ its least code; this is an injection. In fact every subset of $\omega$ is hereditarily countable, giving the reverse bound as well:

Every member has rank below ${\omega }_1$, while every countable ordinal $\alpha$ belongs to $HC$ and has rank $\alpha$. Consequently

The axioms hold except Power Set. axiom of extensionality and Axiom of foundation are inherited by this transitive structure. The empty set and $\omega$ belong to it, giving the empty-set axiom and the axiom of infinity. The axiom of pairing follows from countable-subset closure. For $a\in HC$, $\bigcup a$ is a countable subset of $HC$, giving the Axiom of union. Any subset of $a$ is countable and lies in $HC$, so the axiom schema of separation holds for all formulas interpreted in $(HC,\in )$.

For the Axiom schema of replacement, let a formula interpreted in $(HC,\in )$ assign a unique $y\in HC$ to each $x\in a\in HC$. Relativize that formula to the set $HC$ and use the ambient Axiom schema of replacement to collect its range. The range is countable and consists of members of $HC$, hence belongs to $HC$. The same argument, selecting one witness for each member of the countable domain, proves axiom schema of collection. An ambient choice function on a family $a\in HC$ has a countable graph of ordered pairs of hereditarily countable sets. Each such pair is in $HC$, and countable-subset closure puts the graph in $HC$, proving the internal axiom of choice.

However, all external subsets of $\omega$ are elements of $HC$. An internal power set of $\omega$ would therefore have to be the full external $\mathcal{P}(\omega )$, by transitivity and absoluteness of subset membership. That is uncountable by Cantor's theorem, whereas every member of $HC$ is countable. Thus the axioms satisfied by hereditarily countable sets areHere the asserted axiom list includes both Axiom schema of replacement and axiom schema of collection; no equivalence relying on Power Set is being silently invoked.

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 “countable” to include finite and empty sets: a countable set admits an injection into ${\mathbb{N}}_0$. If $B\subseteq A$ and $j:A\to {\mathbb{N}}_0$ is injective, restricting $j$ to $B$ proves that $B$ is a countable set.

For a countable union of countable sets, index the family as $A_0,A_1,\dots$ and choose an injection $j_i:A_i\to {\mathbb{N}}_0$ for each member. For an element $a$ of the union, let $i(a)$ be the least index containing it, and assignThis is injective: equality of the pair gives the same set index and then the same element. Finally the Cantor pairing functioninjects ${\mathbb{N}}_0^2$ into ${\mathbb{N}}_0$. The union is therefore countable. The proof uses chosen injections for the family, as in the usual set-theoretic framework with axiom of countable choice.

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.

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.

Let $\theta =M\cap \mathrm{Ord}$ be the ordinal height of a model of set theory. First $\theta \ge {\omega }_1$. Indeed, if $\theta$ were countable, the internal axiom of choice would give, for every $x\in M$, a bijection in $M$ between $x$ and some ordinal below $\theta$. Such a bijection is also valid externally, making $x$ externally countable. In particular every internal rank $V_{\xi }^M$, $\xi <\theta$, would be countable. Every element of $M$ lies in one of these internal ranks, sowould be a countable union of countable sets, a contradiction. This is why an uncountable transitive set model has uncountable ordinal height.

For $\xi <\theta$, absoluteness of constructible levels gives $L_{\xi }^M=L_{\xi }$, and that level is an element of $M$. The reason is that satisfaction in a fixed set structure uses the same domain and finite formulas in both universes, so successor definitions agree; transfinite recursion then also makes limit stages agree. Transitivity consequently givesIt remains to locate a countability witness. Given an ambient countable ordinal $\alpha$, choose an injection $f:\alpha \to \omega$. Since $V=L$, it belongs to the constructible universe. Its transitive closure, together with $f$ itself, is countable. Choose a countable elementary substructure $X\prec L_{\eta }$ of a sufficiently large limit level containing this closure pointwise. The condensation lemma for the constructible universe identifies the collapse with $L_{\beta }$ for some countable $\beta$. The collapse fixes $f$, since all its hereditary members were included. Thus $f\in L_{\beta }\subseteq L_{{\omega }_1}\subseteq M$.

The ordinal $\alpha$ itself is in $M$, since $\alpha <{\omega }_1\le \theta$. Being an injection between these fixed sets is a bounded formula in set theory, so $M$ recognizes $f$ as a countability witness. This proves countable-ordinal correctness under constructibility:The use of condensation supplies a witness below the height of $M$; merely knowing that $f$ belongs somewhere to $L$ would not be sufficient.