Hantao Zhang
Hantao Zhang Professor of Computer Science, University of Iowa
Ph.D., Rensselaer Polytechnic Institute, 1988.
Email: hantao-zhang@uiowa.edu (THE BEST WAY TO REACH ME!)
Snail Mail: Department of Computer Science
University of Iowa
Iowa City, Iowa 52242
The following general statements often appear in the textbooks on computability theory: (1) Every finite set of natural numbers is decidable; (2) every set of natural numbers has a characteristic function; and (3) every set of natural numbers is countable. The known proofs of these statements made implicit assumptions not mentioned in them. As a result, the validities of these general statements are questionable, as they fall victim to the fallacy of hasty generalization. We will examinate each of them in detail and propose remedies.
Countability versus Computability by Hantao Zhang
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. The {\em characteristic function} of a set is a total Boolean function which tells if an element is a member of the set or not. Given an infinite set $S$ of natural numbers, we prove the coexistences of a counting bijection of $S$ and its characteristic function in first-order arithmetic. This result has a significant implication: the standard proof that every set of natural numbers is countable is invalid. This is because ``every set $S$ of natural numbers is countable'' implies ``a counting bijection of $S$ is definable in first-order arithmetic,'' which (by our result) would imply that a characteristic function of $S$ is definable in first-order arithmetic. This contradicts the fact that there are uncountably many sets of natural numbers whose characteristic functions are undefinable in first-order arithmetic.