takeonme79
Badges: 0
Rep:
?
#1
Report Thread starter 4 years ago
#1
Is there a non-trivial statement S for which the statement 'S is unprovable', is itself unprovable?

This was an idea that came into my head the other day.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#2
Report 4 years ago
#2
(Original post by takeonme79)
Is there a non-trivial statement S for which the statement 'S is unprovable', is itself unprovable?

This was an idea that came into my head the other day.
Yes. Just do the Gödel treatment on ZF to obtain an unprovable-but-true statement P, and let Q be the statement "P is unprovable and true". Q is unprovable in ZF (if it were provable, then ZF would prove "P is unprovable and true" and hence "P is true", contradiction). Therefore the statement "P is unprovable" is itself unprovable in ZF.

Gödel produces a sentence P which asserts its own unprovability in ZF. The sentence "P is unprovable" is unprovable in ZF, because if it were provable, then we could prove "P is unprovable" and hence (since "P is unprovable" implies P, by definition of P as asserting the unprovability of P) we can obtain P. That's a proof of P, contradiction.

I think that reasoning's sound - do let me know if it's not.
2
reply
poorform
Badges: 10
Rep:
?
#3
Report 4 years ago
#3
(Original post by Smaug123)
Yes. Just do the Gödel treatment on ZF to obtain an unprovable-but-true statement P, and let Q be the statement "P is unprovable and true". Q is unprovable in ZF (if it were provable, then ZF would prove "P is unprovable and true" and hence "P is true", contradiction). Therefore the statement "P is unprovable" is itself unprovable in ZF.

Gödel produces a sentence P which asserts its own unprovability in ZF. The sentence "P is unprovable" is unprovable in ZF, because if it were provable, then we could prove "P is unprovable" and hence (since "P is unprovable" implies P, by definition of P as asserting the unprovability of P) we can obtain P. That's a proof of P, contradiction.

I think that reasoning's sound - do let me know if it's not.


1
reply
takeonme79
Badges: 0
Rep:
?
#4
Report Thread starter 4 years ago
#4
(Original post by Smaug123)
Yes. Just do the Gödel treatment on ZF to obtain an unprovable-but-true statement P, and let Q be the statement "P is unprovable and true". Q is unprovable in ZF (if it were provable, then ZF would prove "P is unprovable and true" and hence "P is true", contradiction). Therefore the statement "P is unprovable" is itself unprovable in ZF.

Gödel produces a sentence P which asserts its own unprovability in ZF. The sentence "P is unprovable" is unprovable in ZF, because if it were provable, then we could prove "P is unprovable" and hence (since "P is unprovable" implies P, by definition of P as asserting the unprovability of P) we can obtain P. That's a proof of P, contradiction.

I think that reasoning's sound - do let me know if it's not.
Yes you are fully correct. I wasn't brave enough to sit down and attempt to find such an example. However, I suspected this kind of example existed and this is what I meant as a 'trivial' case.

Let me try and give an example of what I'm looking for:

The continuum hypothesis is unprovable within ZFC. It has been proved to be unprovable. I'm glad that the proof of unprovability existed otherwise we would still be figuring out how to prove the continuum hypothesis! But could there be a different hypothesis that is non trivial and has some mathematical importance, which is unprovable, but is also unprovable to be unprovable? In that case mathematicians will be forever wondering whether it's true, false or unprovable. How depressing!
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#5
Report 4 years ago
#5
(Original post by takeonme79)
Yes you are fully correct. I wasn't brave enough to sit down and attempt to find such an example. However, I suspected this kind of example existed and this is what I meant as a 'trivial' case.

Let me try and give an example of what I'm looking for:

The continuum hypothesis is unprovable within ZFC. It has been proved to be unprovable. I'm glad that the proof of unprovability existed otherwise we would still be figuring out how to prove the continuum hypothesis! But could there be a different hypothesis that is non trivial and has some mathematical importance, which is unprovable, but is also unprovable to be unprovable? In that case mathematicians will be forever wondering whether it's true, false or unprovable. How depressing!
I have two possible readings of your question, depending on what you mean by "unprovable". Do you mean "CH has been proved in ZFC to be unprovable"? I don't think that's true, is it? I don't know whether CH's independence of ZFC is provable in ZFC, although it's certainly provable from outside ZFC by simply (well, Fields-medal-worthily) constructing models of ZFC+CH and ZFC-CH.
0
reply
takeonme79
Badges: 0
Rep:
?
#6
Report Thread starter 4 years ago
#6
(Original post by Smaug123)
I have two possible readings of your question, depending on what you mean by "unprovable". Do you mean "CH has been proved in ZFC to be unprovable"? I don't think that's true, is it? I don't know whether CH's independence of ZFC is provable in ZFC, although it's certainly provable from outside ZFC by simply (well, Fields-medal-worthily) constructing models of ZFC+CH and ZFC-CH.
Yes you're right. CH's independence of ZFC is not provable in ZFC.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#7
Report 4 years ago
#7
(Original post by takeonme79)
Yes you're right. CH's independence of ZFC is not provable in ZFC.
Ah, so you're looking for a statement which is unprovable-in-maths, and whose unprovability-in-maths is unprovable-in-maths? (As opposed to unprovable-in-ZFC.) I'll look at this again tomorrow, but I have a sleepy suspicion that the existence of such statements is unprovable-in-maths.
0
reply
takeonme79
Badges: 0
Rep:
?
#8
Report Thread starter 4 years ago
#8
(Original post by Smaug123)
Ah, so you're looking for a statement which is unprovable-in-maths, and whose unprovability-in-maths is unprovable-in-maths? (As opposed to unprovable-in-ZFC.) I'll look at this again tomorrow, but I have a sleepy suspicion that the existence of such statements is unprovable-in-maths.
Yes, that's what I'm looking for I had a gut feeling too that this might turn out to be unprovable-in-maths. The CH was just an example but turns out to be a poor one for what I wanted.

So what happens if something like the P vs NP problem, or some other important conjecture, is unprovable and also for there to be no proof of unprovability? Sounds like the worst scenario I can think of for a mathematician.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#9
Report 4 years ago
#9
(Original post by takeonme79)
Yes, that's what I'm looking for I had a gut feeling too that this might turn out to be unprovable-in-maths. The CH was just an example but turns out to be a poor one for what I wanted.

So what happens if something like the P vs NP problem, or some other important conjecture, is unprovable and also for there to be no proof of unprovability? Sounds like the worst scenario I can think of for a mathematician.
I don't think there's a meaningful idea of unprovable-in-maths in the same sense as unprovable-in-ZFC, is there? If P is unprovable-in-maths, we develop theories in the two cases that P is true, and that P is false. (For instance, Choice is unprovable-in-maths because we get a world of maths whether or not Choice is true.) The only way P can be unprovable-in-maths is if maths is just as consistent whether or not P is true, and in that case we just split into two theories and consider each in turn.

Although now you mention it, there's probably a Gödel-induced limit on our own brains (since they're finite objects): presumably it's possible to do a Gödel thing on "the maximal axiom system I am capable of considering" to produce a statement I am unable to prove, even given all of maths, but which is true. Moreover, its unprovability would be unprovable (by me).
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • University of East Anglia
    Undergraduate Open Day Undergraduate
    Sun, 20 Oct '19
  • University for the Creative Arts
    Undergraduate Open Day Undergraduate
    Sun, 20 Oct '19
  • University of Gloucestershire
    Undergraduate Open Day Undergraduate
    Sun, 20 Oct '19

Have you made up your mind on your five uni choices?

Yes I know where I'm applying (58)
66.67%
No I haven't decided yet (19)
21.84%
Yes but I might change my mind (10)
11.49%

Watched Threads

View All