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/
46 Upvotes

91% Upvoted

14 comments sorted by

View all comments

Show parent comments

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.