Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

OP never claimed there were countably many functions from N to N, only that there are countably many Turing machines which is true.

By "polynomials" OP doesn't mean polynomials over the reals but over, for example, the rationals – the point is that there's a countable subset of R that's algebraically closed.



I know those things. OP does not claim that the set of functions from N to N is uncountable. One gives up things if only countable things are considered. For instance those things that I mentioned.


Oh, I see, you're addressing the "we don't need uncountable sets" statement by giving examples of intuitively obvious things which are uncountable. But I think OP's claim is that we don't "need" those things because we could do mathematics with the set of Turing machines instead of the set of functions, etc.


Yes, but can Turing machines do enough mathematics? The second order Peano Axioms are categorical and the first order axioms are not. The Incompleteness Theorem tells us that there are statements that are true in the standard model of N that are not provable by a Turing Machine.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: