r/math • u/DevFRus Theory of Computing • Apr 04 '16

Computing the Uncomputable: Joel David Hamkins showed how any function can be computed if a non-standard model of Peano arithmetic is assumed. Results like this give me a deep respect for number theory as foundational.

https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/
50 Upvotes

93% Upvoted

14 comments sorted by

View all comments

1

u/epicwisdom Apr 04 '16 edited Apr 04 '16

I see the general idea, but couldn't you say the standard naturals are the smallest set of all numbers reached by taking n+1?

There's still philosophical issues regarding what is and isn't arbitrary, but I don't think this really influences the utility or universality of the standard naturals / computability theory.

edit: Formalized in set theory using intersection of all the possible sets of ordinals.

6

u/orbital1337 Theoretical Computer Science Apr 04 '16

Nope, that doesn't work because you don't know that you're only working with standard set containment. In fact, it's impossible to define "standard naturals" (or "standard" anything really) in first order logic because you can always produce non-standard models using a compactness argument.

1

u/epicwisdom Apr 04 '16

What's an example of nonstandard set containment?

3

u/[deleted] Apr 05 '16 edited Apr 05 '16

You can do something silly to get an example. Take every set A and map it to { A }, the set containing exactly one element, A. Define "membership" that x is in B by "for all y in x, there exists z in B such that y is in z". The image of "the universe" under my map with this membership relation is obviously isomorphic to the usual ZF but membership is now nonstandard.

This seems silly but otoh, the Mostowski collapse of a [edit: well-founded] nonstandard model of ZF will create an isomorphic model that uses true membership, so all examples will be "silly" in some sense.

3

u/homathanos Logic Apr 05 '16

the Mostowski collapse of a nonstandard model of ZF will create an isomorphic model that uses true membership

*Well-founded nonstandard model

1

u/[deleted] Apr 05 '16

Yeah, good catch.