For sure there are valid arguments on whether or not to use certain axioms which allow or disallow some set theoretical constructions, but given ZFC, is there anything that follows that is unprovable?
In particular, you have made sufficient assumptions to prove that almost all real numbers that exist can never be specified in any possible finite description. In what sense do they exist? You also wind up with weirder things. Such as well-specified finite problems that provably have a polynomial time algorithm to solve...but for which it is impossible to find or verify that algorithm, or put an upper bound on the constants in the algorithm. In what sense does that algorithm exist, and is finite?
Does that sound impossible? An example of an open problem whose algorithm may have those characteristics is an algorithm to decide which graphs can be drawn on a torus without any self-crossings.
If our notion of "exists" is "constructable", all possible mathematical things can fit inside of a countable universe. No set can have more than that.
I'm saying that to go from the uncountability of the reals to the idea that this implies that the infinity of the reals is larger, requires making some important philosophical assumptions. Constructivism demonstrates that uncountable need not mean more.
On the algorithm example, you could have asked what I was referring to.
The result that I was referencing follows from the https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo.... The theorem says that any class of finite graphs which is closed under graph minors, must be completely characterized by a finite set of forbidden minors. Given that set of forbidden minors, we can construct a polynomial time test for membership in the class - just test each forbidden minor in turn.
The problem is that the theorem is nonconstructive. While it classically proves that the set exists, it provides no way to find it. Worse yet, it can be proven that in general there is no way to find or verify the minimal solution. Or even to provide an upper bound on the number of forbidden minors that will be required.
This need not hold in special cases. For example planar graphs are characterized by 2 forbidden minors.
For the toroidal graphs, as https://en.wikipedia.org/wiki/Toroidal_graph will verify, the list of known forbidden minors currently has 17,523 graphs. We have no idea how many more there will be. Nor do we have any reason to believe that it is possible to verify the complete list in ZFC. Therefore the polynomial time algorithm that Robinson-Seymour says must exist, does not seem to exist in any meaningful and useful way. Such as, for example, being findable or provably correct from ZFC.
John Horton Conway:
> It's a funny thing that happens with mathematicians. What's the ontology of mathematical things? How do they exist? In what sense do they exist? There's no doubt that they do exist but you can't poke and prod them except by thinking about them. It's quite astonishing and I still don't understand it, having been a mathematician all my life. How can things be there without actually being there? There's no doubt that 2 is there or 3 or the square root of omega. They're very real things. I still don't know the sense in which mathematical objects exist, but they do. Of course, it's hard to say in what sense a cat is out there, too, but we know it is, very definitely. Cats have a stubborn reality but maybe numbers are stubborner still. You can't push a cat in a direction it doesn't want to go. You can't do it with a number either.
Errr, I'm just assuming the axioms of ZFC. That's literally all I'm doing.
> In what sense do [numbers that can't be finitely specified] exist?
In the sense that we can describe rules that lead to them, and describe how to work with them.
I understand that you're trying to tie the notion of "existence" to constructability, and that's fine. That's one way to play the game. Another is to use ZFC and be fine with "weird, unintuitive to laypeople" outcomes. Both are interesting and valid things to do IMO. I'm just not sure why one is obviously "better" or "more real" or something. At the end, it's all just coming up with rules and figuring out what comes out of them.
On the other hand, I think it's really cool to teach laypeople about things like "sizes of infinities", etc. They are deep math concepts that can be taught with relatively simple analogies that most people understand, and they're interesting things to know. I know that I personally loved learning about them as a kid, before I had almost any knowledge of math - it's one of the reasons that while I initially didn't connect with other areas of math, I found set theory delightful as a kid.
I just feel like if you need to first walk people through a bunch of philosophical back and forth on constructionism, you'll never get to the fun stuff.
But it is easy to present deep ideas from constructivism, without mentioning the word constructivism. Or even acknowledging that the philosophy exists.
For example the second half of https://math.stackexchange.com/questions/5074503/can-pa-prov... is an important constructivist thing. It shows why everything that a constructivist could ever be interested in mathematically, can be embedded in the natural numbers. With all of the constructions needing nothing more than the Peano Axioms. (Proving the results may need stronger axioms though...)
From my point of view, https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach does something similar. That book got a lot of people interested in basic concepts around recursion, computation, and what it means to think. Absolutely everything in it works constructively. And yet that philosophy is not mentioned. Not even once.
The only point where a constructivist need discuss all of the philosophical back and forth on constructivism, is in explaining why a constructivist need not accept various claims coming out of classical mathematics. And even that discussion would not be so painful if people who have learned classical mathematics were more aware of the philosophical assumptions that they are making.
To be honest, I don't feel like I know enough about the constructivist philosophy. What would be a good place to start if I want to learn more about it?
I haven't yet read your PA proving Goodstein sequences article, though I have skimmed it and it is, indeed, super interesting.
And for the record, Godel, Escher, Bach was probably the single most important influence on me even starting to get interested in computation, etc.
ZFC (and its underlying classical logic) is precisely the problem here though
In the sense that all statements of non-constructive "existence" are made, viz. "you can't prove that they don't exist in the general case", so you are allowed to work under the stronger assumption that they also exist constructively, without any contradiction resulting. That can certainly be useful in some applications.
But the fact that such systems don't create contradictions emphatically *DOES NOT* demonstrate the constructive existence of such an oracle. Doubly not given that in various usual constructivist systems, it is easily provable that nothing that exists can serve as such an oracle.
Of course, but it shows that you can assume that such an oracle exists whenever you are working under additional conditions where the existence of such a "special case" oracle makes sense to you, even though you can't show its existence in the general case. This outlook generalizes to all non-constructive existence statements (and disjunctive statements, as appropriate). It's emphatically not the same as constructive existence, but it can nonetheless be useful.
I won't ever be able to find a contradiction from that claim, because I have no way to find that bank account if it exists.
But that argument also won't convince me that the bank account exists.
Theoretically possible? Sure. But the kinds of questions that lead you there are generally in opposition to the kinds of principles that lead someone to prefer constructivism.
If the only questions you accept as meaningful are the decidable ones, then you can trust its answers for all the questions you accept as meaningful and for which it has answers.
Also, “provable that nothing that exists can serve as such an oracle” seems pretty presumptive about what things can exist? Shouldn’t that be more like, “nothing which can be given in such-and-such way (essentially, no computable procedure) can be such an oracle”?
Why treat it as axiomatic that nothing that isn’t Turing-computable can exist? It seems unlikely that any finite physical object can compute any deterministic non-Turing-computable function (because it seems like state spaces for bounded regions of space have bounded dimension), but that’s not something that should be a priori, I think.
I guess it wouldn’t really be verifiable if such a machine did exist, because we would have no way to confirm that it never errs? Ah, wait, no, maybe using the MIP* = RE result, maybe we could in principle use that to test it?
On being presumptive about what things can exist, that's the whole point of constructivism. Things only exist when you can construct them.
We start with things that everyone accepts, like the natural numbers. We add to that all of the mathematical entities that can be constructed from those things. This provides us with a closed and countable universe of possible mathematical entities. We have a pretty clear notion of what it means for something in this universe to exist. We cannot be convinced of the existence of anything that is outside of the universe without making extra philosophical assumptions. Philosophical assumptions of exactly the kind that constructivists do not like.
This constructible universe includes a model of computation that fits Turing machines. But it does not contain the ability to describe or run any procedure that can't fit onto a Turing machine.
Therefore an oracle to decide the Halting problem does not exist within the constructible universe. And so your ability to imagine such an oracle, won't convince a constructivist to accept its existence.
This is exactly what I’m saying is presumptive! If constructivism is to earn the merit of being less presumptive by virtue of not assuming the existence of various things, it should also not assume the non-existence of those things.
Which, I think many visions of constructivism do earn this merit, but not your description of it.
What makes you presume that you have any business telling someone with different beliefs from you, what is OK to believe? You may believe in the existence of whatever you like. Whether that be numbers that cannot be specified, or invisible pink unicorns.
I'll be over in the corner saying that your belief does not compel me to agree with you on the question of what exists. Not when your belief follows from formalism, which explicitly abandons any pretense of meaningfulness to its abstract symbol manipulation.
Merely believing that such a thing (a halting oracle) doesn’t exist, isn’t something I meant to call presumptive, only believing that you can know a-priori (with certainty) that such things cannot exist.
I don’t claim that you are obligated to agree with me that they do exist. Someone who believes they don’t, but doesn’t believe they can know this as certain a-priori knowledge, would be no more presumptive than I am, and someone who is agnostic on the question of whether they exist would be less presumptive than I am.
Also, I disagree with your notion of “meaningfulness”. At a minimum, all statements in the arithmetic hierarchy are meaningful. The continuum hypothesis might in a certain sense not be meaningful.
If you think that I was making that case, then you have misunderstood something important.
Constructivism is a statement about what kinds of arguments will convince me that things exist.
Could things exist that I don't believe in? Absolutely! There could well be a bank account with my name on it that I don't know about. Its existence is possible, and my lack of belief in it is no skin off of its back. But I still don't believe that it exists.
Similarly, the Platonists could be correct. There could be an omniscient God whose perfect mind gives existence to a perfect system of mathematics, beyond human comprehension. I have no way to prove that there isn't such a God, and therefore that there isn't such a perfect mathematics.
However the potential for such things to exist is a point of theology. I do not believe in their existence. Just as I do not believe in the existence of Santa. In neither case can I prove that they don't exist. And if you choose to believe in them, that's your business. Not mine.
There is nothing presumptive in my laying out the rules of reason that I will accept as convincing to me. There is a lot of presumption if anyone else comes along and tells me that I should think differently about unprovable propositions.
Now it happens to be the case that from the rules of reason that I use, I provably can't be convinced of the existence of certain things. That's a mathematical theorem. But the fact that I can't be convinced, doesn't prove that you shouldn't be convinced. You are free to be convinced of all of the unprovable assertions that you wish. And it is also true that on something like this, I have no way to convince you that it doesn't exist.
On meaningfulness, meaning is in the eye of the beholder. For example there are people who are willing to pay a million dollars for a century old stamp which was misprinted with the airplane upside-down. (See https://en.wikipedia.org/wiki/Inverted_Jenny to verify that.) They clearly find great meaning in that stamp. But I don't.
So again, you're free to find meaning in whatever you want. But you're in the wrong to object that I don't find meaning in what you consider important.
I might be confused here, but isn't an Oracle to decide the halting problem something that everyone agrees doesn't exist?
The whole idea is for this to be a thought experiment. "If we magically had a way to decide the halting problem, how would that affect things" seems like a normal hypothetical question.
Here is why a classical mathematician would say that this oracle exists.
Let f(program, input, n) be 1 or 0 depending on whether the program program, given input input, is still running at step n. This is a perfectly well-behaved mathematical function. In fact it is a computable one - we can compute it by merely running a simulation of a computer for a fixed number of steps.
Let oracle(program, input) be the limit, as n goes to infinity, of f(program, input, n). Classically this limit always exists, and always gives us 0 or 1. The fact that we happen to be unable to compute it, doesn't change the fact that this is a perfectly well-defined function according to classical mathematics.
If you give up the existence of this oracle, you might as well give up the existence of any real numbers that do not have a finite description. Which is to say, almost all of them. Why? Because the set of finite descriptions is countable, and therefore the set of real numbers that admit a finite description is also only countable. But there are an uncountable number of real numbers, so almost all real numbers do not admit a finite description.
The real question isn't whether this oracle exists. It is what you want the word "exists" to mean.
If I'm following you, then most "mathematical" CS is based on constructivist foundations? E.g. while a halting problem Oracle might "exist" in the mathematical sense, it's not considered to "exist" for most purposes of deciding complexity classes, etc.
> The real question isn't whether this oracle exists. It is what you want the word "exists" to mean.
I was going to say the same thing. I'm not sure what "exists" means in some of these discussions.
As for what exists means, here are the three basic philosophies of mathematics.
The oldest is Platonism. It is the belief that mathematics is real, and we are trying to discover the right way to do it. Ours is not to understand how it is to exist, it is to try to figure out what actually exists. Kurt Gödel is a good example of someone who argued for this. See https://journals.openedition.org/philosophiascientiae/661 for a more detailed exploration of his views, and how they changed over time. (His Platonism does seem to have softened over time.)
Historically this philosophy is rooted in Plato's theory of Forms. Where our real world reflects an ideal world created by a divine Demiurge. With the rise of Christianity, that divine being is obviously God. This fit well with the common idea during the Scientific Revolution that the study of science and mathematics was an exploration of the mind of God.
Formalism dates back to David Hilbert. In Hilbert's own description, it reduces mathematics to formal symbol manipulation according to formal rules. It's a game to figure out what the consequences are of the axioms that were chosen. As for existence, "If the arbitrarily posited axioms together with all their consequences do not contradict each other, then they are true and the things defined by these axioms exist. For me, this is the criterion of truth and existence." See page 39 of https://philsci-archive.pitt.edu/17600/1/bde.pdf for a reference.
In other words if we make up any set of axioms and they don't contradict each other, the things that those axioms define have mathematical existence. Whether or not we can individually describe those things, or learn about them.
Over on the constructivist side of the fence, there are a wide range of possible views. But they share the idea that mathematical things can only exist when there is a way to construct them. But that begs the question.
Finitism only accepts the existence of finite things. In an extreme form, even the set of natural numbers doesn't exist. Only individual natural numbers. Goodstein of the Goodstein sequence is a good example of a finitist.
Intuitionism has the view that mathematics only exists in the minds of men. Anything not accessible to the minds of men, doesn't exist. The best known adherent of this philosophy is Brouwer.
My sympathies generally lie with the Russian school, founded by Markov. (Yes, the Markov that Markov chains are named after.) It roots mathematics in computability.
Erret Bishop is an example of a more pragmatic version of constructivism. Rather than focus on the philosophical claims, he pragmatically focuses on what can be demonstrated constructively. https://www.amazon.com/Foundations-Constructive-Analysis-Err... is his best known work.