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

New Article:

From Godel's First Incompleteness Theorem to the Uncountability of a Set of Natural Numbers by Hantao Zhang

In the proof of Godel's first incompleteness theorem, given a formal system F, Godel defined a set BF of natural numbers which are the Godel numbers of formulas that can be proved in F. We show that there exists a formal system F' such that the characteristic function of BF' cannot be constructed in any consistent formal system. We show further that an infinite set S of natural numbers is countable if and only if S has a characteristic function. Excluding inconsistent formal systems, we conclude that BF' is uncountable, because if BF' were countable, we would have obtained a characteristic function of BF'. BF' serves as a counterexample to the claim that “every set of natural numbers is countable,” which appears in many textbooks on set theory, logic, or discrete mathematics.

Textbook:

Logic in Computer Science by Hantao Zhang and Jian Zhang

Publications


Research Projects on Automated Reasoning:


Teaching:


Others



Hantao Zhang
Updated