## Eliminating Decision Problem Undecidability

Next
• 8.2k
If there is no possible way to know that expression X is true then we can't possibly know
that expression X is true. AKA when X lacks a truth-maker then X is not true.

We must get through this key point first because it is the core foundation of everything
that I am saying. I oversimplified this a little bit so that you can get the gist of what I am saying.
As I said, we know it from an indirect proof. We can prove that not-X is false, hence we assume that mathematics is consistent, hence X is true (as either X or not-X is true).

Cantor's diagonalization argument is one of the easiest examples of this.

Cantor start from the assumption that all reals are listed, and makes from this list a real number that cannot be on the list. Hence the reductio ad absurdum proof.
• 8.9k
Let's debate this from another angle.
In mathematics, do you think there can be true, but unprovable statements?
Do you think that all true statements are also provable?
And finally, can an indirect reductio ad absurdum proof prove something?
Yes on No answers would be appreciated (of course with reasoning too).
ssu

TonesInDeepFreezessu
is in my opinion one of the folks on TPF whose voice carries weight in his subject matter. I am not. But I think I can answer these, and maybe tones will correct errors I may make.

True but unprovable. Tones, above, covers this explicitly. Here the language matters, and not taking that into account leads to trouble. Better as, true-in-system-X but not provable-in-system-X. That leaves the way open for provable in some other system. Godel was careful and rigorous to make explicit what his system(s) are, equally careful and rigorous in the claims he made. Informally, not too hard to understand; formally not-so-easy. And the best way in is actually to read Godel's paper. It is a model of clarity and not too long.

All true statements provable. The simplest counter-examples are axioms - that's why they're called axioms. And just here the door to whole other discussions with plenty of rabbit-holes as hazards.

Indirect reductio ad absurdum proofs. Not sure what those are. Do you have an example? (In trust we both get the joke, here.)

As I read our now-banned member, It seemed to me he was making a limited and ultimately trivial claim, that he had unfortunately persuaded himself was somehow general and significant. All I could do was ask him for clarity, which he could not provide. Tones on the other hand was setting him straight, which (in my opinion) he was too disturbed to accept, appreciate, or follow.

And the substance of the claim, as I read it, was that if you have a closed system/listing of propositions that are proved true (whatever that is), and your standard for inclusion in this listing is that the proposition be provably true and everything else false, then - and here insert his claims. The main difficulty being that while his claims may have been true for some closed system in theory, he wanted it to apply across-the-board - and never mind that his closed system was (I think) not even theoretically possible.

Nice I wouldn't know, but otherwise I think you're exactly right, because I suffer that a lot myself - and could wish for even just a fewer trees here on TPF! So I feel gratitude to the mods for saving me from myself while I learn to do it for myself!
• 8.2k
Thanks for continuing this thread, Tim!

Indirect reductio ad absurdum proofs. Not sure what those are. Do you have an example? (In trust we both get the joke, here.)
Lol, well, if math is consistent, you'll get the proof. :razz:

As I read our now-banned member, It seemed to me he was making a limited and ultimately trivial claim, that he had unfortunately persuaded himself was somehow general and significant. All I could do was ask him for clarity, which he could not provide. Tones on the other hand was setting him straight, which (in my opinion) he was too disturbed to accept, appreciate, or follow.
It's typical to underestimate the people on this Forum. But the issue here is that there's still a lot of debate on exactly what the undecidability results mean. What exactly is the realm of "true, but unprovable mathematical statements" or the role of non-computable mathematics. Obviously something that at first mathematicians don't want to find their answers to be in the realm of.

It sounds like an oxymoron and for our banned member it was totally nonsense and he obviously didn't get even after your and @TonesInDeepFreeze's effort.

And the substance of the claim, as I read it, was that if you have a closed system/listing of propositions that are proved true (whatever that is), and your standard for inclusion in this listing is that the proposition be provably true and everything else false, then - and here insert his claims. The main difficulty being that while his claims may have been true for some closed system in theory, he wanted it to apply across-the-board - and never mind that his closed system was (I think) not even theoretically possible.
This clearly shows the person simply doesn't grasp the Undecidability results. And just to repeat again and again that Gödel is referring to the Liar paradox (and hence you can disregard it) is the typical error here.

In my view many people just don't understand that negative self-reference a simply logical limitation, especially when your primary idea has refered to all or everything. Then you just show even one example that it's impossible and that's it.

Nice I wouldn't know, but otherwise I think you're exactly right, because I suffer that a lot myself - and could wish for even just a fewer trees here on TPF! So I feel gratitude to the mods for saving me from myself while I learn to do it for myself!
Especially in logic, mathematics, but also in philosophy I think there's a good guideline. If someone says that you are wrong or misunderstand something, that isn't yet worrysome. But if two or more say that, you really have to consider going over what were saying. Now if people especially after some discussion simply fall silent, then you perhaps can have a point. Either nothing to add, or it goes totally over their head (which is also a possibility).

Hence I do urge the people here to correct mistakes, it truly is something that others can also learn from.
• 8.9k
Amen to all.
that there's still a lot of debate on exactly what the undecidability results mean.ssu
Well, there is what they are. What they mean is just that which they exactly say. Significance a different question.

E.g., Godel's sentence, usually referred to as just "g," is expressed by Godel in his paper as 17genR. Unpacked - and while Godel is rigorous in his packing, thee and me can follow it if we're willing to to be not-so-rigorous while not forgetting that he is - it says if you have a numbered listing of all possible arguments expressible in a certain broad class of systems that include arithmetic, let's call them ω, then for all x (the 17gen), x being the index number of the arguments, none is proof of the proposition numbered R. The catch, of course, being that R is just that proposition itself, asserting its own unprovability. And there are details that matter in that they make the "picture" more exact.

The trick is self-reference. But are there propositions in ω - or arithmetic - that are true but unprovable that do not involve self-reference? And that gets into what a proof is, how long it can be, or how it is to be defined. A subject that can be so dry it makes my brain wrinkle.
• 8.2k
What they mean is just that which they exactly say. Significance a different question.
Exactly. And referring to the significance of Gödel's results usually gets a response of someone questioning you exactly how the difficult proof goes and repeating it (and sidelining the part that you were talking about: the significance of the results).

The trick is self-reference. But are there propositions in ω - or arithmetic - that are true but unprovable that do not involve self-reference?
That's an absolutely great question.

Because now everything on this field does hang on the (negative) self-reference. Every undecidability result has it. Please correct me now (anybody) if it isn't so! One possibility I've been thinking about is that the procedure defines a whole realm of mathematics. Of course, getting an undecidability result without negative self reference would be really revolutionary and counter my idea.

Yet even to admit just how important the undecidability results are would be important too. The way that first the paradoxes and then the undecidability results are seen as something against the idea of logicism is the problem. I think that mathematics is certainly logical, yet logicism shouldn't be so controversial. The thinking should be turned around: these undecidability results are a cornerstone for mathematics to be logical. Not everything is simply computable and hence what defines non-computable mathematics is a very important law for all of mathematics. In my view if you get in mathematics a paradox simply means that your premises, or more properly the axioms you think are self evident actually aren't so. Yet it seemed that with the paradoxes, they were thought as of a mistake and with the undecidability results, people simply hope to avoid them and hope them to be not important. Hence the idea was first going with Type theory (like Russell did) or simply make axioms that ban the paradox (as ZF did). This didn't erase the issue, as the famous undecidability results showed. It's like when the Greeks at first thought that all numbers have to be rational, and then when confronted by irrational numbers, they didn't like it. Because math was perfect so everything had to be rational, right? The basic problem then in Russell's time (and even now) was the idea that all the essential building blocks of mathematics and it's foundations are already in place. I think they aren't. The paradoxes and then the undecidability results simply show this.

Which makes then you question even more important. It's still just a working hypothesis that everything is based on negative self reference, in the way of "with negative self reference, you can lose computability/the ability to give a direct proof". Obviously a good counter-question is what you asked.

• 8.9k
Or another way: that there is the subject matter, and also how we feel about it. Distinguishing between aging and maturing, It would seem that as one matures one learns to - and how to - deal with new ideas. While as aging, one becomes increasingly likely to complain, "Who ordered that?!" Maturing aspirational, work, open, good. Aging natural, to be fought, closed, bad, but ultimately victorious in the end.

There used to be in general use - and still in some places - a computer language called COBOL. A distinguishing characteristic being the need to carefully define storage. And if not well-defined, or if inputs didn't match storage parameters, then if you were lucky the program blew up. If unlucky, it would run and simply accumulate error. These days programs are not so persnickety - at least in this way.

And to my way of thinking, thinking often works along similar COBOL lines, in the sense of there being a pre-existing set of personal parameters for thinking about and dealing with new inputs. If open and easy, good. If closed, and difficult, then either you freak out, blow up, or simply function in increasing error.

Examples abound. We're born, grow up, and learn things that to learn even a fraction of which as an adult would prostrate most of us. Maths is full of such ideas. Philosophy itself. And snakes: for some people just another new and interesting animal, for others intolerable.

Undecidable propositions, then, either just new and interesting and to be got used to, or snakes. The trick not to goggle at them.
• 8.2k
Or another way: that there is the subject matter, and also how we feel about it.
And in something as logical and rigorous as mathematics, the last thing is for us to accept that we have feelings about how it should be. Or that they would matter. It's like the person who declares: "Philosophy is meaningless to me, I do just science" has a quite specific philosophical view about science.

If open and easy, good. If closed, and difficult, then either you freak out, blow up, or simply function in increasing error.
In economics one way to model self reference or basic interaction of the variables is to use dynamic models. And there you have to make quite careful models that stay in some equilibrium. The amount of premises just increase.

The trick not to goggle at them.
Hm, I'm not sure what you mean by this.

I just think they are quite interesting. For example, here's a thought experiment to clarify (hopefully) my reasoning why this is such a general finding:

Is there a limitation on what kind of answer you can write on PF?

- Obviously not, you can write anything you want (you might be banned later, but aside of that).

If so, can we deduce then from the above that you can write EVERY answer there exists, if you would have infinite time and the ability write anything, any kind of length answer (the typical Busy-Beaver argumentation etc.)?

- Actually not, because you cannot write an answer that you don't write.

Wait a minute! Wasn't it so that there isn't any limitation on what to write?

- Yes, but assuming that you can write everything isn't equivalent to there not being any limitations on what you can write.

As this is purely theoretical and I have infinite time and ability to write, how can there be any limitation?

- Because of diagonalization. From everything you written taken as whole, you can use this to create something you haven't written.

Is this totally trivial? Obviously a person cannot write what he or she doesn't write.

In mathematics when it comes to computing and proving something, it isn't so trivial. But the mechanism is the same.
• 1.8k
But I applaud The Philosophy Forum for its toleration, allowing even the most incorrigible cranks to start thread after redundant thread, spewing disinformation like a crudely written bot.

I guess this is the confirmation I was not wrong when everytime I saw one of those threads I had the feeling it was a crackpot rambling. In my bouts of self-doubt, I wondered if it wasn't my ignorance of the topic that didn't allow me to follow the conversation.
• 6k
@TonesInDeepFreeze

Tones was doing a good job refuting all the crankery in a highly educational manner. That can make for a good thread. Albeit a frustrating one for whoever is doing the hard teaching work.

It's quite difficult to draw a principled line between someone who misunderstands something repeatedly in a rude manner and an incorrigible, disruptive crank.

Anyway they're banned now, thanks @TonesInDeepFreeze for persistently unraveling the cranking.
• 5.2k
I wondered if it wasn't my ignorance of the topic that didn't allow me to follow the conversation.

Same here. I remember I took part in one of @PL Olcott' s threads when he focused on 'Carol' (yes/no incorrect questions. Here). I did my best arguing with him, but he always twisted the words with the aim of making circular points. I ended up with the conclusion that it was actually my fault for not being capable of following his points. I felt very ignorant about myself.
Next
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal