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
Tarski's undefinability theorem claims that the characteristic function of true arithmetic cannot be defined in first-order arithmetic. Based on this theorem, we prove that the popular claim that "every set of natural numbers is countable," which appears in many textbooks on set theory, logic, or discrete mathematics, lacks valid proof. Hence, the claim remains an open problem. Based on Godel's first incompleteness theorem, we extend Tarski's undefinability theorem to more sets of natural numbers: there exists an infinite set G of natural numbers whose characteristic function cannot be defined in any consistent effective formal system. This result may have impact on the application of Turing reduction where oracles are used. It appears that proving the countability of G is an insurmountable task, because G involves a formal system more complex than higher-order logic systems, and the hope of doing so in ZFC is slim.