Countability versus Computability

Abstract

The concept of {\em countable sets} is attributed to Georg Cantor, who established the distinction between countable and uncountable sets in 1874. The concept of {\em computable sets} emerged in the 1930s through the foundational work on computing models by \Godel, Church, and Turing. In this paper, we investigate the connection between countability and computability. A {\em counting bijection} of a set $S$ is a bijection from the set of natural numbers to $S$. We say $S$ is {\em enumerable} if it is either finite or admitting a computable counting bijection. Our initial investigation shows that a set $S$ is enumerable if and only if it is computable. This equivalence offers new insights into set theory and computability theory. We further show that a set is countable if and only if it admits a {\em counting order}, which is a well order satisfying the {\em proximal} property. Based on this concept, we provide a procedure whose existence gives a necessary and sufficient condition for a set to be countable. This procedure is an algorithm if and only if the set is computable. A counting bijection $f$ is {\em increasing} if $f(x)>f(y)$ whenever $x>y$. We prove that an infinite set $S$ of natural numbers is definable in first-order arithmetic if and only if $S$ has an increasing counting bijection. This result has a significant implication: the standard proof that every set $S$ of natural numbers is countable is invalid. This is because the existing proof establishes that $S$ has an increasing counting bijection, which (by our result) would imply that $S$ is definable in first-order arithmetic. This leads to a contradiction with Tarski's undefinability theorem when $S$ is the set of \Godel\ numbers of the true arithmetic sentences.

This is a revision of the previous manuscript entitled "Equivalence of Countable and Computable"

Topics & keywords