1 Introduction↩︎

In 1874, Georg Cantor [1] published the first proof that there is no one-to-one correspondence between the set of all real numbers (which is uncountable) and the set of all natural numbers (which is countable). In 1891, Cantor simplified his proof using the well-known diagonal argument, which has since found important applications in both set theory and computability theory [2].

In the 1930s, several independent attempts were made to formalize the notion of computability: Kurt Gödel’s partial recursive functions [3], Alonzo Church’s lambda calculus [4], and Turing’s formal model, later known as Turing machines [5]. Church and Turing proved that these three notions of computable functions coincide and proposed the well-known conjecture called the Church–Turing thesis: a function is computable if it is Turing computable [6]. Other formal attempts to characterize computability, including Kleene’s recursion theory [7] and von Neumann’s random-access stored-programs (RASP) models, have further strengthened this view. Since we cannot exhaust all possible computing models, the Church–Turing thesis—though enjoying near-universal acceptance—cannot be formally proved.

Nine decades have passed, yet it remains puzzling that the deep connection between countability and computability has not been fully investigated. To facilitate the presentation of our investigation, we first review some key concepts. Following Cantor, a set \(S\) is countable if either \(S\) is finite or there exists a bijection \(f:{\cal N}\mapsto S\), where \({\cal N}\) is the set of natural numbers [1]. From now on, we refer to any such bijection \(f:{\cal N}\mapsto S\) as a counting bijection of \(S\). We say \(S\) is countably infinite if it admits a counting bijection. A set \(S\) is enumerable if it is either finite or admits a computable counting bijection. Finally, \(S\) is increasingly countable if \(S\subseteq {\cal N}\) and it admits an increasing counting bijection \(f\) (i.e., \(f(x) > f(y)\) whenever \(x>y\)).

Our investigation of the connection between countability and computability has focused on three main topics:

1. Our initial investigation shows that a formal language \(L\) is recognizable if and only if \(L\) is enumerable, and that \(L\) is decidable if and only if \(L\) is increasingly countable and computable [8]. This provides an alternative method for determining whether a formal language is recognizable or decidable.

2. We introduce the concept of a proximal order which requires that the number of distinct elements lying between any two elements (when placed according to the order) be finite. A counting order is a proximal well order. We prove that a set \(S\) is countable if and only if \(S\) admits a counting order. Given a counting order \(\succeq\), one can design a procedure deleteMin\((S, \succeq)\) that removes the minimal element from \(S\). We show that \(S\) is countable if and only if such a deleteMin exists, and that \(S\) is enumerable if and only if deleteMin\((S, \succeq)\) is an algorithm. This yields a necessary and sufficient criterion for countability.

3. Definability in first-order arithmetic has greater expressivity power than Turing machines. We prove that a set \(S\) of natural numbers is increasingly countable if and only if \(S\) is definable in first-order arithmetic. This result has a significant consequence: the standard proof that every subset of \({\cal N}\) is countable is incorrect. Although this claim is widely accepted in logic and mathematics, the existing proof shows a stronger claim that every subset of \({\cal N}\) is increasingly countable. By our result, this would imply that every subset of \({\cal N}\) is definable in first-order arithmetic—a contradiction to Tarski’s undefinability theorem, which states that the set \(T\) of true sentences in the standard model of first-order arithmetic is not definable in first-order arithmetic.

This article is a substantial revision of [9]. The next three sections address the three topics outlined above, respectively. The common theme running through these topics is the relationship between countability and computability. The first topic illustrates how the computability of a set relates to the properties of its counting bijections. The second topic offers a procedural respective on countable sets. The final topic goes beyond Turing computability and demonstrates how the definability of a set in logic relates to increasing counting bijections.

2 Equivalence of Recognizable and Enumerable↩︎

The main part of this section appears in the textbook [8] and is used here as background material for the entire article. We assume familiarity with the basic concepts of theory of computation [2], [8].

Given a Turing machine \(M\), the language \(L(M)\) recognized by \(M\) is said to be recognizable. A set is computable iff it is recognizable. If \(M\) halts on every input, then \(L(M)\) is decidable and \(M\) is a decider. A function \(f:{\cal N}\mapsto{\cal N}\), where \({\cal N}\) denotes the set of natural numbers, is computable if it can be computed by a Turing machine \(M\). The machine \(M\) is said to be an algorithm if \(M\) halts on every input; in this case, \(f\) is total computable (i.e., both total and computable).

We will need a computing model called enumerator, which is a variant of Turing machine. Informally, an enumerator is a Turing machine \(M\) equipped with an attached printer [2]. The machine \(M\) uses the printer as an output device to print strings. The set \(E(M)\) of printed strings is the language enumerated by \(M\). The following result is known for enumerators [2], [8]:

For decidable languages, the following result is known [2], [8].

By Cantor’s definition, a set \(S\) is countable if either \(S\) is finite or there exists a bijection \(f: {\cal N}\mapsto S\). In the infinite case, we say \(f\) is a counting bijection of \(S\).

By this definition, \(S\) is countable if \(S\) is enumerable. The inverse is not always true unless \(S\) is finite or \(S\) has a computable counting bijection.

.Since \(S\) is unenumerable, \(S\) cannot be finite. If \(S\) has any counting bijection, then it must be uncomputable. This is true for every bijection \(g:{\cal N}\mapsto S\), if \(g\) exists. \(\square\)

The following two propositions show that a formal language is enumerable iff it is recognizable [8].

.Suppose \(L\) is recognizable. The case when \(L\) is finite is trivial. If \(L\) is infinite, by Theorem 1\((b)\), we have an enumerator \(M\) such that \(L = E(M)\) and every printed string by \(M\) is unique, then \(E(M)\) is countable because the order in which the strings are printed by \(M\) defines a computable bijection \(f: {\cal N}\mapsto E(M)\). That is, for \(n\in {\cal N}\), we compute \(f(n)\) by algorithm \(A(n)\) as follows:

Algorithm \(A(n)\): Let \(c:= 0\) and simulate \(M\). When a string \(x\) is printed by \(M\), check if \(c=n\). If yes, return \(x\); otherwise \(c:= c+1\) and continue the simulation.

Algorithm \(A\) will terminate because \(E(M)\) is infinite and \(c\), which records the number of printed strings by \(M\), will reach \(n\) eventually. \(A(n)\) can be modified as \(B(w)\) to compute \(f^{-1}(w)\) for \(w\in E(M)\): Instead of checking \(c=n\), check if \(x=w\) and, if yes, return \(c\). Since both \(f\) and \(f^{-1}\) are total functions, \(f\) is a bijection. Algorithm \(A(n)\) is the evidence that \(f\) is computable. \(\square\)

.The case when formal language \(L\) is finite is trivial. If \(L\) is enumerable, then there exists a computable bijection \(f: {\cal N}\mapsto L\), Thus, we may use \(f\) to design an enumerator \(M\) that prints strings \(f(0)\), \(f(1)\), \(f(2)\), and so on. It is evident that \(E(M) = L\). By Theorem 1\((a)\), \(L\) is recognizable. \(\square\)

The following theorem combines the above two propositions into one and extends the result from formal languages to general sets [8].

.Let \(S\) be any set. The case when \(S\) is finite is trivial.

If \(S\) is enumerable, then there exists a computable counting bijection \(f:{\cal N}\mapsto S\). Then \(S = \{ f(n) \mid n\in{\cal N}\}\) because \(f\) is a bijection. \(S\) is computable because \(f(n)\) is computable.

When \(S\) is unenumerable, there are two cases to consider: \(S\) can be represented by a formal language or not. If yes, then \(S\) is unrecognizable by Proposition 5, thus uncomputable. If not, then \(S\) cannot be recognized by any Turing machine, thus uncomputable. \(\square\)

The above result is useful when we want to show some sets are countable. For instance, if we know a set is recognizable, then this set is enumerable, hence countable. If a set is unrecognizable, then it is unenumerable. It is known that the collection of recognizable sets is closed under intersection (i.e., the intersection of any two recognizable sets is recognizable). It implies that the intersection of two enumerable sets is enumerable, thus countable.

We say a counting bijection \(f: {\cal N}\mapsto X\) is increasing if \(f(n) < f(n+1)\) for every \(n\in{\cal N}\), where \(<\) is a well order of \(X\). The following theorem is important about countable sets [8].

.For (1), by Theorem 2, \(X\) is decidable iff the elements of \(X\) can be enumerated in increasing order. This enumeration defines an increasing and computable bijection as in the proof of Proposition 5, and an increasing and computable bijection will produce an enumerator that enumerates elements in increasing order as in the proof of Proposition 6. Theorem 2 is then used to obtain the expected result.

(2) comes from Theorem 7, as “\(X\) is enumerable” means “there exists a computable bijection \(f:{\cal N}\mapsto X\).” (3) is logically equivalent to (2). \(\square\)

The above theorem shows that the properties of counting bijection \(f:{\cal N}\mapsto X\) is crucial to dictate whether \(X\) is decidable or computable. In particular, if \(X\) is computable but undecidable, then \(f\) must be computable but not increasing.

3 A Procedure for Countability↩︎

In mathematics, a poset (partial order set) is a pair \((S, \succeq)\), where \(S\) is a set and \(\succeq\) is a partial order of \(S\)—that is, \(\succeq\) is an antisymmetric, transitive, and reflexive relation on \(S\). For any \(a,b\in S\), we write \(a \succ b\) to mean \(a\succeq b\) and \(a \neq b\). The order \(\succeq\) is total if, for any \(a,b\in S\), exactly one of \(a \succ b\), \(b\succ a\), or \(a=b\) holds. It is well-founded if every non-empty subset of \(S\) has a minimal element with respect to \(\succeq\). The order \(\succeq\) is a well order if it is both total and well-founded. Finally, \(\succeq\) is dense if, for any \(a,b\in S\) with \(a \succ b\), there exists an element \(c\in S\) such that \(a\succ c\succ b\).

When proving the set of reals is not countable, Cantor’s diagonal argument is used to show that the assumed counting order is not proximal because some elements are left out of the order. The following proposition shows that the concept of counting orders is equivalent to that of countable.

.The finite case is trivial, so we consider only infinite sets. If \(S\) is countable, then \(S\) has a counting bijection \(f:{\cal N}\mapsto S\). Define \(\succeq\) over \(S\) by \(f(x) \succeq f(y)\) if \(x > y\) for any \(x,y\in{\cal N}\). Then \(\succeq\) is a proximal well order of \(S\), since \(\ge\) is a proximal well order of \({\cal N}\).

On the other hand, let \(\succeq\) be a proximal well-order of \(S\). For any \(n\in{\cal N}\), define \(g(n)\) to be the \((n+1)^{th}\) minimal element of \(S\) under \(\succ\). \(g:{\cal N}\mapsto S\) is injective because \(i^{th}\) minimal element is different from \(j^{th}\) minimal element if \(i \neq j\). \(g\) is surjective because \(\succeq\) is a counting order. That is, let \(a = min(S)\), \(b\in S\) and \(a\neq b\). Since \(\succeq\) is proximal, the set \(X = \{ c\in S \mid b \succ c \succ a \}\) is finite. If \(|X| = n\), then \(b\) is the \((n+2)^{th}\) minimal element of \(S\). Hence, for any \(b\in S\), there exists \(m\in{\cal N}\), \(g(m) = b\). Thus, \(g\) is a counting bijection of \(S\). \(\square\)

If \(S\) is enumerable yet undecidable, by Theorem 9, we can obtain a computable bijection \(f':{\cal N}\mapsto S\), where \(f\) is not increasing (with respect to \(\ge\)). In the above proof, from \(f\), we obtain a proximal well order \(\succeq\) of \(S\) such that \(f\) is increasing with respect to \(\succeq\). Obviously, \(\succeq\) is different from \(\ge\).

In the second part of the above proof, we defined the function \(g:{\cal N}\mapsto S\) to be the \((n+1)^{th}\) minimal element of \(S\) under \(\succ\). The same idea was used in the proof of the claim that every set of natural numbers is countable [10]. If \(S\) is undecidable, then \(g\) cannot be computable if \(\succ\) is \(>\) over \({\cal N}\), because an increasing computable \(g\) implies that \(S\) is decidable.

Proposition 12 claims that a set has a counting bijection iff it has a counting order, and provides a necessary and sufficient condition for countable sets.

Given a poset \((S, \succeq)\), where \(\succeq\) is a counting order of \(S\), we will design a procedure deleteMin\((S, \succeq)\) that removes the minimal element (with respect to \(\succeq\)) from \(S\) and returns the minimal element. This offers a procedural perspective for studying countability.

.In the following proof, we consider only infinite sets as the finite case is trivial.

\((1)\) By Proposition 12, \(S\) is countable iff \(S\) has a proximal well-order. deleteMin\((S, \succeq)\) exists iff \(\succeq\) exists, because for nonempty \(S\), \[min(S, \succeq) = x \leftrightarrow(x \in S \wedge\forall y\in S~\neg(x \succ y)).\] We may design deleteMin\((S,\succeq)\) which scans \(S\) once to locate \(min(S,\succeq)\), deletes it from \(S\), and returns it.

\((2)\) If \(S\) is enumerable, there exists a computable bijection \(f: {\cal N}\mapsto S\) and \(S = \{ f(n) \mid n\in{\cal N}\}\). In fact, \(f\) is total computable since \(f\) is total. Thus, the Turing machine that computes \(f\) is an algorithm. As in the proof of Proposition 12, for any \(x,y\in{\cal N}\), we define \(\succeq\) by \(f(x) \succeq f(y)\) if \(x \ge y\). Then \(min(S, \succeq) = f(0)\), and deleteMin\((S,\succeq)\) will return \(f(0)\), \(f(1)\), \(f(2)\), .… Since \(f\) is total computable, so is deleteMin\((S,\succeq)\). On the other hand, if deleteMin\((S,\succeq)\) is an algorithm, for any \(n\in{\cal N}\), let \(f(n)\) be the element returned by the \((n+1)^{th}\) call of deleteMin\((S, \succeq)\), then \(f\) is a computable counting bijection of \(S\). \(\square\)

Theorem 13 gives us a necessary and sufficient condition for an enumerable set \(S\): Having an algorithm deleteMin with a counting order \(\succeq\). Every element of \(S\) can be enumerated one by one from the smallest by the counting order \(\succeq\). Note that \(S\) can be any enumerable set, not just a set of natural numbers. If \(S\) is a set of natural numbers, then the enumerated numbers are not necessarily in increasing order of \(\ge\). For instance, let \(H\) be the formal language for the halting problem of Turing machines. \(H\) is computable but undecidable, then \(H\) cannot be enumerated in increasing order of \(\ge\) (see Theorem 2).

4 Unproven Statements about Countable Sets↩︎

The claim that “every subset of \({\cal N}\) is countable” appears in many textbooks on logic [11], set theory [12], [13], discrete mathematics [14], or theory of computation [15]. In a textbook on set theory [16] published in 1977, the author simply wrote without proof that “Obviously every subset of a countable set is countable.” It also appears in an influential textbook by Terence Tao [10] (Proposition 8.1.5).
of [10] Let \(X\) be an infinite subset of the natural numbers \({\cal N}\). Then there exists a unique bijection \(f: {\cal N}\mapsto X\) which is increasing, in the sense that \(f(n + 1) > f(n)\) for all \(n \in {\cal N}\). In particular, \(X\) has equal cardinality with \({\cal N}\) and is hence countable.
A proof sketch of the above proposition goes as follows [10]: Since \(<\) is a well order of \(X\), \(X\) has a minimal element under \(<\), say \(a_0 = min(X)\). Let \(X_0 = X\) and, for \(i>0\), \(X_i = X_{i-1} -\{ a_{i-1} \}\), where \(a_i = min(X_i)\), we obtain an increasing sequence \[a_0 < a_1 < a_2 < ...\] along with the sequence \(X_0, X_1, X_2, ...\). Since \(X\subseteq{\cal N}\), \(X = \{ a_0, a_1, a_2, ...\}\). Define \(f:{\cal N}\mapsto X\) by \(f(n) = a_n = min(X_n)\), it is evident that \(f\) is an increasing bijection (see the proof of Proposition 12).

.At first, the function \(min(X)\) can be specified in first-order arithmetic: \[(min(X) = a) \leftrightarrow(a \in X \wedge\forall b\in X~\neg(a > b)).\] Secondly, the counting bijection \(f:{\cal N}\mapsto X\) in the proof can be expressed by the function \(g\). That is, for all \(x\in{\cal N}\), \(f(n) = g(X, n)\), as follows: \[\begin{array}{rcl} g(X, 0) & = & min(X) \\ g(X, n+1) & = & g(X - \{ min(X) \}, n) \end{array}\] It is straightforward to check that \[f(n) = g(X_0, n) = g(X_1, n-1) = g(X_2, n-2) = \cdots = g(X_n, 0) = min(X_n) = a_n.\] Hence, the proof of Proposition 8.1.5 can be carried out in first-order arithmetic. \(\square\)

In first-order arithmetic, a natural number \(n\) is represented by the numeral \(\overline{n} = s^n0\), where \(0\) and \(s\) (the successor function) are the symbols of first-order arithmetic. A set \(S\subseteq {\cal N}\) is said to be definable in first-order arithmetic if \(S = \{ n\in{\cal N}\mid \phi(\overline{n}) \}\), where \(\phi(x)\) is a predicate of first-order arithmetic and \(x\) is the only free variable. If the relation \(p(n)\) represents the meaning of \(\phi(x)\) in the standard model of first-order arithmetic, then \(p(n)\) is true iff \(\phi(\overline{n})\) is true and \(S = \{ n\in{\cal N}\mid p(n)\}\).

Proposition 8.1.5 proved a stronger result than the claim that every subset of \({\cal N}\) is countable: every subset of \({\cal N}\) is increasingly countable. This stronger result leads to the following proposition.

. If \(S\) has an increasing counting bijection, then \(S\) is an infinite set of natural numbers. Let \(f: {\cal N}\mapsto S\) be an increasing bijection. For any \(n,m\in{\cal N}\), we define \(h:{\cal N}\times{\cal N}\mapsto\{0, 1\}\) as follows: \[\begin{array}{rcl} h(n, m) & = & {\boldsymbol{i}f}\;(f(m) = n)~ {\boldsymbol{t}hen}\;1\\ && {\boldsymbol{e}lse}\;{\boldsymbol{i}f}\;(f(m) > n)~{\boldsymbol{t}hen}\;0\\ && ~~~~~~~{\boldsymbol{e}lse}\;h(n, m+1) \end{array}\] When \(h(n,0)\) returns \(1\), there exists \(m\) such that \(f(m) = n\). When \(h(n,0)\) returns \(0\), there exists no \(0 \le x< m\) such that \(f(x) = n\). Since \(f\) is increasing, there exists no \(x\ge m\) such that \(f(x) = n\) because \(f(x)\ge f(m) > n\). Define \(T = \{n \in {\cal N}\mid h(n, 0) = 1 \}\), then \(S = T\) because for any \(n\in {\cal N}\), \(n\in S\) iff there exists \(m\) such that \(f(m) = n\). Let \(\phi(x)\) be the predicate such that \(\phi(\overline{n})\) is true iff \(h(n,0)\) is true, then \(S = T = \{ n\in{\cal N}\mid \phi(\overline{n})\}\), hence, \(S\) and \(T\) are definable in first-order arithmetic since \(h\) is a function definable in first-order arithmetic. \(\square\)

The inverse of the above proposition also holds. We say a predicate \(\phi(x)\) is total, where \(x\) is the only free variable, if \(\phi(\overline{n})\) is equivalent to true or false for every \(n\in{\cal N}\). We say a set \(S\subseteq {\cal N}\) is totally defined if \(S = \{ n\in{\cal N}\mid \phi(\overline{n})\}\) and \(\phi(x)\) is total.

.Suppose \(S\) is defined by \(\phi(x)\), a total predicate of first-order arithmetic, and the relation \(p(n)\) is the meaning of \(\phi(x)\) in the standard model of first-order arithmetic such that \(p(n)\) is true iff \(\phi(\overline{n})\) is true for any \(n\in{\cal N}\). Then \(p\) is total because \(\phi(x)\) is total and \(S = \{ n\in{\cal N}\mid p(n) \}\). For any \(n\in{\cal N}\), define \(f(n) = g(n, 0)\), where \(g: {\cal N}\times{\cal N}\mapsto{\cal N}\) is defined as follows: \[\begin{array}{rcl} g(n, m) & = & {\boldsymbol{i}f}\;p(m) \\ && {\boldsymbol{t}hen}\;{\boldsymbol{i}f}\;(n=0)~{\boldsymbol{t}hen}\;m~ {\boldsymbol{e}lse}\;g(n-1, m+1)\\ && {\boldsymbol{e}lse}\;g(n, m+1) \end{array}\] Let \(S = \{ a_0, a_1, a_2, ... \}\subseteq{\cal N}\) such that \(a_i < a_{i+1}\) for \(i\in{\cal N}\). For any \(n\in{\cal N}\), \(g(n,0)\) visits \(0, 1, ..., a_0\) before that \(n\) is decreased by \(1\) in the recursive calls of \(g\). Similarly, \(g(n-1, a_0+1)\) will visit \(a_0+1, ..., a_1\); \(g(n-2, a_1+1)\) will visit \(a_1+1, ..., a_2\), and so on, during the recursive calls. Finally, \(g(0, a_{n-1}+1)\) will return \(a_n\), the minimal number of \(S - \{f(0), f(1), ..., f(n-1)\}\). It is ready to check that \[f(n) = g(n, 0) = g(n-1, a_0+1) = g(n-2, a_1+1) = \cdots = g(0, a_{n-1}+1) = a_n.\] \(g(n,m)\) is totally defined because \(S\) is infinite and \(\phi(m)\) is true for an infinite number of \(m\). It is easy to check that \(f\) is an increasing counting bijection of \(S\). Note that we need \(p(m)\) to be total so that \(g(n,m)\) and \(f(n)\) are total, too. \(\square\)

.This theorem is the combination of Propositions 15 and 16. Note that the predicate \(\phi(x)\) constructed in the proof of Proposition 15 is total since \(h(n, m)\) is total. \(\square\)

The arithmetical hierarchy proposed by Stephen Kleene classifies formulas of first-order arithmetic by the use of (unbounded) quantifiers [17]. The classifications of formulas are denoted by \(\Sigma^0_{n}\) (and \(\Pi^0_{n}\)) for \(n\in{\cal N}\) (\(0\) in the superscript denotes first-order). For \(n>0\), a \(\Sigma^0_{n}\) formula is equivalent to a prenex formula that begins with some existential quantifiers and alternates \(n-1\) times between series of existential and universal quantifiers. Analogously, a \(\Pi^0_{n}\) formula, where \(n>0\), is equivalent to a prenex formula that begins with some universal quantifiers and then alternates. A set of natural numbers defined by a formula of \(\Sigma^0_n\) (\(\Pi^0_n\)) is called a \(\Sigma^0_n\)-set (\(\Pi^0_n\)-set). It is known that each \(\Sigma^0_0\)-set is decidable; each \(\Sigma^0_1\)-set is (partial) computable; each \(\Pi^0_1\)-set is co-computable. For \(n>1\), a \(\Sigma^0_n\)-set may be uncomputable [17]. Theorem 17 shows for the first time the equivalence of increasingly countable sets and first-order arithmetical sets as well as the connection between the properties of counting bijections and computability beyond Turing machines.

Tarski’s undefinability theorem is a fundamental limitative result in mathematical logic which states that no sufficiently powerful formal language can define its own truth predicate. Proved by mathematician and logician Alfred Tarski in 1933, the theorem establishes that any system capable of expressing basic arithmetic cannot mathematically formulate a comprehensive definition of “truth" for its own sentences without creating logical contradictions [18].

Let \(\mathcal{A}\) be the structure of the natural numbers and \({\mathcal{A}}\models\phi\) denote that formal \(\phi\) is true in \(\mathcal{A}\). True arithmetic is defined to be the set of all sentences in PA that are true in \(\mathcal{A}\), written \(T= \{ \phi \mid {\mathcal{A}}\models\phi\}\). That is, true arithmetic is the set of all true first-order statements about the arithmetic of natural numbers. Let \(T^* = \{ \ulcorner \theta \urcorner \mid \theta \in T\}\) be the set of Gödelnumbers of all true sentences in \({\mathcal{A}}\) [19].

Now we are ready to show that “every subset of \({\cal N}\) is countable” lacks a valid proof.

. 8.1.5 claims that every subset of \({\cal N}\) is increasingly countable. Since the constructed counting bijection is specifiable in first-order arithmetic (Proposition 14), By Proposition 15, every increasingly countable set is definable in first-order arithmetic. That leads to the claim that “every subset of \({\cal N}\) is definable in first-order arithmetic,” which contradicts Tarski’s undefinability theorem, since \(T^*\) is a subset of \({\cal N}\). \(\square\)

The root cause of the contradiction exposed by the above proposition is because a condition is ignored in the proof of Proposition 8.1.5. The existing proof merely proved that every set of natural numbers is increasingly countable if it is defined in first-order arithmetic. That is, in the definition of \(min(X)\), \[min(X) = a \leftrightarrow(a \in X \wedge\forall b\in X~\neg(a > b)),\] we need to check \(a\in X\) and \(b\in X\). This check is available in first-order arithmetic only when \(X\) is defined in first-order arithmetic. Proposition 8.1.5 skipped the condition that “\(X\) is defined in first-order arithmetic,” an error of hasty generalization.

The claim that “every subset of \({\cal N}\) is countable” is widely accepted and taught in many college courses. The claim has several equivalent statements.

. \((1)\Rightarrow(2)\): \({\cal N}\) is countable.

\((2)\Rightarrow(3)\): Let \(f: S\mapsto{\cal N}\) be injective and \(X = \{ f(x) \mid x \in S\}\). Since \(X\subseteq {\cal N}\), \(X\) is countable by \((2)\). Note that \(f: S\mapsto X\) is a bijection from \(S\) to \(X\), that is, \(S\) and \(X\) are the same size. So, \(S\) must be countable.

\((3)\Rightarrow(4)\): Let \(g: {\cal N}\mapsto S\) be surjective, then for every \(x\in S\), the set \(g^{-1}(x) = \{ y\mid g(y) = x\}\) is not empty. Define \(f: S\mapsto{\cal N}\) by \(f(x) = min(g^{-1}(x))\), then \(f\) is injective. By \((3)\), \(S\) is countable.

\((4)\Rightarrow(1)\): Let \(X\subseteq S\) and \(S\) be countable. If \(X\) is finite, then \(X\) is countable. If \(X\) is infinite, then \(S\) must be infinite and there exists a bijection \(h: {\cal N}\mapsto S\). Let \(a\) be an element of \(X\). Define \(g: {\cal N}\mapsto X\) by \(g(x) = h(x)\) if \(h(x)\in X\), otherwise \(g(x)=a\). Then \(f\) is surjective. By \((4)\), \(S\) is countable. If \(g\) is not required to be total, then “\(g(x)=a\)” is not needed when \(h(x)\notin X\). \(\square\)

Many textbooks claim that they are true statements, but they suffer the same error as that of Proposition 8.1.5. Hence, their validity remains an open problem. Indeed, if they are true, we may have an alternative yet simpler definition of “countable”: A set \(S\) is countable if there is an injective function from \(S\) to \({\cal N}\). Some textbooks use this definition [16]. This definition does not matter whether \(S\) is finite or not and uses only injection, not bijection.

5 Conclusions↩︎

In Cantor’s time, the notion of computability had not yet been formally defined. Cantor used the word count to indicate that an operation is performed. It turns out that the properties of counting bijections are closely related to computability. Our initial investigation shows that a set is computable if and only if it has a computable counting bijection, and that a set is decidable if and only if it has an increasing and computable counting bijection [8]. In this article, we provide a procedural perspective on countability. We show that a set \(S\) is countable if and only there exists a procedure deleteMin\((S, \succeq)\) that deletes the minimal element of \(S\) according to the counting order \(\succeq\). Moreover, \(S\) is computable if and only if deleteMin\((S, \succeq)\) is an algorithm. This result further strengthens the relationship between countability and computability.

For computability beyond Turing machines, one may use first-order arithmetic as a specification tool. We show that an infinite set \(S\) of natural numbers is totally definable in first-order arithmetic if and only if \(S\) has an increasing counting bijection which is specifiable in first-order arithmetic. This result has an important consequence: the standard proof of the claim that every subset of \({\cal N}\) is countable is invalid, as it contradicts Tarski’s undefinability theorem. Without a valid proof, the claim becomes an open problem. Proving it appears to be very challenging. According to Gödel’s incompleteness theorems [3], every sufficiently powerful axiom system has inherent limitations. If counting bijections of a set cannot be defined within an axiom system, the limitations of that system may imply the existence of another set of natural numbers whose counting bijections cannot be defined in the same system. There appears to be no upper bound on the difficulty or complexity in either computability or countability.

References↩︎