2024/03/26 by Hantao Zhang, Zhang, Hantao
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2406.08493
openalex publication_date 2024/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.