bloaf » May 7th, 2017, 2:25 pm wrote:The blog posts appears to formalize the position that what functions are computable depends on the model of arithmetic/set theory that we choose. The point not made in the blog post, but made by Natural_ChemE, is that the models of arithmetic/set theory that we are capable of choosing are constrained only by physics.

LOL This thread is someguy1 bait for sure. I have less to say than you'd think but I'll do my best to shed some light.

Regarding NatChemE's position, he's not here to disagree so it would not be fair for me to rehash any of that thread. But Hamkins is talking about abstract set theory, and there's no known relation between set theory and physics at the present time. So it's not entirely sensible to bring up NatChemE's point of view in the context of the Hamkins articles. We're talking set theory and not physics. The space of all possible mathematical structures, whether they are physical or not.

In short, nothing in Hamkins's article or my exposition here have anything at all to do with the real world. As far as we know, of course.

bloaf » May 7th, 2017, 2:25 pm wrote:However, I'm not clean enough about the precise definition of "Model" used in Dr. Hamkins' post, and so I was hoping someone here might give me an explanation, or point me towards some learning materials.

First, Hamkins is a world-class set theorist on the forefront of research. So learning materials would include a fair amount of grad-level set theory at a minimum. If you ask specific questions I can fill you in on what little I know. I don't think there are very many elementary Wiki-type expositions of higher set theory. Maybe Google around for set theory, independence proofs, model theory, large cardinals, and so forth. Hamkins has a great article on his concept of the set-theoretic multiverse that's well worth reading.

But I can talk sensibly about models. Standard set theory is Zermelo-Fraenkel, ZF. We know that the axiom of choice (AC) is independent of ZF. That means we can take AC as an axiom, and ZF + AC, called ZFC, is consistent if ZF is.

Or we can take as an axiom the

negation of AC, and that system is consistent as well (if ZF is).

[By the way from now on I'll just say "such and so is consistent," leaving out the qualification "if ZF is." The point is that we know that *if* ZF is consistent, so is ZFC. But we don't know (within ZF) if ZF is consistent. So all statements about consistency are relative to other ones. If this is consistent then that is. In general I'll ignore this but it's always implied].

So ZFC and ZF-C (ZF minus C) are both consistent. They are in effect two different set theoretic worlds in which different statements of mathematics are true.

**

Math is not physicsNow first, please please please note that we are not talking about physics. There is not a shred of evidence or even a plausibility argument that ZF is instantiated in any way in the real world. For one thing. ZF assumes there are infinite sets. There are no infinite collections of anything in the real world.

It's not even plausible that a statement like AC even has a sensible truth value in the real world. To find out, we'd have to take an uncountably infinite collection of sets (whatever they are) and see if there's some other set containing exactly one element from each of these other sets.

Now what kind of sense can that make in physics? It's not any part of contemporary science. For the moment, set theory is purely an abstract mathematical idea with no referent in the real world.

Of course we can use basic ideas like unions and intersections. The set of boys and the set of red haired people has as their intersection the set of red haired boys. That's part of the world, to be sure, but it's far too simple to capture the actual strangeness of set theory.

If I have an apple on the desk, that's physical. Can you honestly tell me that there's some physical referent for the

set containing the apple? Let alone the set containing the empty set. Such things are purely mathematical abstractions.

So I hope that we can simply, flat out forget about any physical considerations. For some reason people have a hard time doing that in discussions of pure math, and much confusion ensues.

From now on we are simply not talking about the world. Only what goes on in modern set theory.

**

Back to the articleNow there are a lot of models of set theory. ZFC and ZF-C are two familiar ones. Even in ZF, which assumes infinite sets, we can actually deny that there are infinite sets and we still get a consistent set theory. It's basically the number theory of the Peano axioms. So those are more models.

Set theorists have gotten very good at cooking up exotic models of set theory in order to examine various exotic modern axioms.

So Hamkins's point is that given any function

there is SOME crazy model of set theory in which

is computable. That in itself is amazing. But remember, these are very weird models.

But now Hamkins has a very subtle cheat. Note his wording. I'll copy this in verbatim.

Hamkins wrote:There is a Turing machine program

with the property that for any function

on the natural numbers, including non-computable functions, there is a model of arithmetic or set theory inside of which the function computed by

agrees exactly with

on all standard finite input.

(Emphasis mine)

What's that bolded bit mean? Consider one of NatChemE's examples, the hyperreal numbers. The hyperreals are a nonstandard model of the first-order theory of the real numbers in which we have every familiar real number, along with lots and lots of infinite and infinitesimal numbers as well. In particular, the hyperreals contain

hyperintegers, or infinite integers, numbers that do not exist in the standard integers.

What Hamkins is saying is that our magic universe that makes some function computable, is only making that function computable on the standard, finite numbers. It's not necessarily computable on the nonstandard, non-finite numbers that exist in that model.

So in a sense, as surprising as Hamkins's result is, it's saying a little bit less than it seems. It's not saying the given function is computable in the new universe.

Only the function's restriction to the standard, finite integers matches the original function. We don't know anything about its extension to the nonstandard or on-finite numbers in the new model. It seems to be a bit weaker than the title of the article but this is pretty technical and I can't say for certain.

That's my first take from Hamkins's article. Fire away with questions, I'll do my best.

But if there is one single tl;dr takeaway, it's that this has nothing to do with physics.

Also by the way I should admit that I don't really grok what it means to have a Turing machine operating in an alternate model of set theory. I think that's the core mystery here. I don't know what that really means.