Incomplete theory proving its incompleteness by a formula neither provable true nor false in the theory

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

Would it be possible that an incomplete theory had a formula that proved its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false, so you could never prove it's incomplete in first place?

logic soft-question incompleteness

share|cite|improve this question

edited Jul 24 at 2:15

Parcly Taxel

33.5k136588

asked Jul 24 at 2:10

Daniel Bonilla Jaramillo

38319

• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Parcly I believe your edit has changed the OP's intended question
  – David Diaz
  Jul 24 at 2:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidDiaz it hasn't…
  – Parcly Taxel
  Jul 24 at 2:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you mean "... had a formula that expressed its incompleteness ..."? Formulas don't prove anything.
  – Henning Makholm
  Jul 24 at 2:23
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

Would it be possible that an incomplete theory had a formula that proved its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false, so you could never prove it's incomplete in first place?

logic soft-question incompleteness

share|cite|improve this question

edited Jul 24 at 2:15

Parcly Taxel

33.5k136588

asked Jul 24 at 2:10

Daniel Bonilla Jaramillo

38319

• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Parcly I believe your edit has changed the OP's intended question
  – David Diaz
  Jul 24 at 2:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidDiaz it hasn't…
  – Parcly Taxel
  Jul 24 at 2:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you mean "... had a formula that expressed its incompleteness ..."? Formulas don't prove anything.
  – Henning Makholm
  Jul 24 at 2:23
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

Would it be possible that an incomplete theory had a formula that proved its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false, so you could never prove it's incomplete in first place?

logic soft-question incompleteness

share|cite|improve this question

edited Jul 24 at 2:15

Parcly Taxel

33.5k136588

asked Jul 24 at 2:10

Daniel Bonilla Jaramillo

38319

Would it be possible that an incomplete theory had a formula that proved its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false, so you could never prove it's incomplete in first place?

logic soft-question incompleteness

share|cite|improve this question

edited Jul 24 at 2:15

Parcly Taxel

33.5k136588

asked Jul 24 at 2:10

Daniel Bonilla Jaramillo

38319

share|cite|improve this question

share|cite|improve this question

edited Jul 24 at 2:15

Parcly Taxel

33.5k136588

edited Jul 24 at 2:15

Parcly Taxel

33.5k136588

edited Jul 24 at 2:15

Parcly Taxel

33.5k136588

33.5k136588

asked Jul 24 at 2:10

Daniel Bonilla Jaramillo

38319

asked Jul 24 at 2:10

Daniel Bonilla Jaramillo

38319

asked Jul 24 at 2:10

Daniel Bonilla Jaramillo

38319

38319

• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Parcly I believe your edit has changed the OP's intended question
  – David Diaz
  Jul 24 at 2:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidDiaz it hasn't…
  – Parcly Taxel
  Jul 24 at 2:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you mean "... had a formula that expressed its incompleteness ..."? Formulas don't prove anything.
  – Henning Makholm
  Jul 24 at 2:23
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Parcly I believe your edit has changed the OP's intended question
  – David Diaz
  Jul 24 at 2:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidDiaz it hasn't…
  – Parcly Taxel
  Jul 24 at 2:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you mean "... had a formula that expressed its incompleteness ..."? Formulas don't prove anything.
  – Henning Makholm
  Jul 24 at 2:23
  

  
  
  
  

@Parcly I believe your edit has changed the OP's intended question
– David Diaz
Jul 24 at 2:14

@Parcly I believe your edit has changed the OP's intended question
– David Diaz
Jul 24 at 2:14

@DavidDiaz it hasn't…
– Parcly Taxel
Jul 24 at 2:15

@DavidDiaz it hasn't…
– Parcly Taxel
Jul 24 at 2:15

1

1

Do you mean "... had a formula that expressed its incompleteness ..."? Formulas don't prove anything.
– Henning Makholm
Jul 24 at 2:23

Do you mean "... had a formula that expressed its incompleteness ..."? Formulas don't prove anything.
– Henning Makholm
Jul 24 at 2:23

add a comment | 

2 Answers
2

active

oldest

votes

up vote
2
down vote

I'm assuming what you actually mean is,

Would it be possible that an incomplete theory had a formula that expressed its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false by that theory, so you could never prove it's incomplete in first place?

If so, the answer is, "yes, easily".

A boring way to see this is to select a theory so weak that it proves hardly anything at all -- for example Robinson Arithmetic. It is just about strong enough that it's defensible to say that the standard (Gödelian) way of encoding statements about provability into the language of arithmetic is meaningful for it, but definitely not strong enough to prove interesting general statements about provability.

As a less boring example, your favorite foundational theory such as PA or ZFC will also be an example. Proving the theory to be incomplete would in particular prove it to be consistent, and we know from the second incompleteness theorem that PA or ZFC cannot prove their own consistency, unless they are in fact inconsistent.

share|cite|improve this answer

answered Jul 24 at 2:33

Henning Makholm

225k16290516

add a comment | 

up vote
0
down vote

In the presentations I have seen the proof of incompleteness is not in the base theory. We have a base theory, like Peano Arithmetic (PA), and we construct a sentence in the language of PA that we can argue outside of PA is undecidable inside of PA. That convinces us as observers that PA is incomplete.

The original Gödel proof constructed a predicate $Proof(x,y)$ that is true if $x$ is the number representing a proof of $y$. This predicate is primitive recursive, so (with great effort) can be made quantifier free. If we let $z$ be the number representing $0=S(0)$ (the formal version of $0=1$) the statement that PA is consistent can be represented as $lnot exists x Proof(x,z)$ because an inconsistent theory can prove anything it can express. PA does not prove this sentence undecidable. Outside of PA (often called in the metatheory) we can argue that if PA could prove $Con(PA)=lnot exists x Proof(x,z)$ it would be inconsistent. This is Gödel's second incompleteness theorem.

share|cite|improve this answer

answered Jul 24 at 2:38

Ross Millikan

275k21186351

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860941%2fincomplete-theory-proving-its-incompleteness-by-a-formula-neither-provable-true%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

I'm assuming what you actually mean is,

Would it be possible that an incomplete theory had a formula that expressed its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false by that theory, so you could never prove it's incomplete in first place?

If so, the answer is, "yes, easily".

A boring way to see this is to select a theory so weak that it proves hardly anything at all -- for example Robinson Arithmetic. It is just about strong enough that it's defensible to say that the standard (Gödelian) way of encoding statements about provability into the language of arithmetic is meaningful for it, but definitely not strong enough to prove interesting general statements about provability.

As a less boring example, your favorite foundational theory such as PA or ZFC will also be an example. Proving the theory to be incomplete would in particular prove it to be consistent, and we know from the second incompleteness theorem that PA or ZFC cannot prove their own consistency, unless they are in fact inconsistent.

share|cite|improve this answer

answered Jul 24 at 2:33

Henning Makholm

225k16290516

add a comment | 

up vote
2
down vote

I'm assuming what you actually mean is,

Would it be possible that an incomplete theory had a formula that expressed its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false by that theory, so you could never prove it's incomplete in first place?

If so, the answer is, "yes, easily".

A boring way to see this is to select a theory so weak that it proves hardly anything at all -- for example Robinson Arithmetic. It is just about strong enough that it's defensible to say that the standard (Gödelian) way of encoding statements about provability into the language of arithmetic is meaningful for it, but definitely not strong enough to prove interesting general statements about provability.

As a less boring example, your favorite foundational theory such as PA or ZFC will also be an example. Proving the theory to be incomplete would in particular prove it to be consistent, and we know from the second incompleteness theorem that PA or ZFC cannot prove their own consistency, unless they are in fact inconsistent.

share|cite|improve this answer

answered Jul 24 at 2:33

Henning Makholm

225k16290516

add a comment | 

up vote
2
down vote

up vote
2
down vote

I'm assuming what you actually mean is,

Would it be possible that an incomplete theory had a formula that expressed its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false by that theory, so you could never prove it's incomplete in first place?

If so, the answer is, "yes, easily".

A boring way to see this is to select a theory so weak that it proves hardly anything at all -- for example Robinson Arithmetic. It is just about strong enough that it's defensible to say that the standard (Gödelian) way of encoding statements about provability into the language of arithmetic is meaningful for it, but definitely not strong enough to prove interesting general statements about provability.

As a less boring example, your favorite foundational theory such as PA or ZFC will also be an example. Proving the theory to be incomplete would in particular prove it to be consistent, and we know from the second incompleteness theorem that PA or ZFC cannot prove their own consistency, unless they are in fact inconsistent.

share|cite|improve this answer

answered Jul 24 at 2:33

Henning Makholm

225k16290516

I'm assuming what you actually mean is,

Would it be possible that an incomplete theory had a formula that expressed its incompleteness, but that same formula belonged to the set of formulae of that theory that can't be proven true or false by that theory, so you could never prove it's incomplete in first place?

If so, the answer is, "yes, easily".

A boring way to see this is to select a theory so weak that it proves hardly anything at all -- for example Robinson Arithmetic. It is just about strong enough that it's defensible to say that the standard (Gödelian) way of encoding statements about provability into the language of arithmetic is meaningful for it, but definitely not strong enough to prove interesting general statements about provability.

As a less boring example, your favorite foundational theory such as PA or ZFC will also be an example. Proving the theory to be incomplete would in particular prove it to be consistent, and we know from the second incompleteness theorem that PA or ZFC cannot prove their own consistency, unless they are in fact inconsistent.

share|cite|improve this answer

answered Jul 24 at 2:33

Henning Makholm

225k16290516

share|cite|improve this answer

share|cite|improve this answer

answered Jul 24 at 2:33

Henning Makholm

225k16290516

answered Jul 24 at 2:33

Henning Makholm

225k16290516

answered Jul 24 at 2:33

Henning Makholm

225k16290516

225k16290516

add a comment | 

add a comment | 

up vote
0
down vote

In the presentations I have seen the proof of incompleteness is not in the base theory. We have a base theory, like Peano Arithmetic (PA), and we construct a sentence in the language of PA that we can argue outside of PA is undecidable inside of PA. That convinces us as observers that PA is incomplete.

The original Gödel proof constructed a predicate $Proof(x,y)$ that is true if $x$ is the number representing a proof of $y$. This predicate is primitive recursive, so (with great effort) can be made quantifier free. If we let $z$ be the number representing $0=S(0)$ (the formal version of $0=1$) the statement that PA is consistent can be represented as $lnot exists x Proof(x,z)$ because an inconsistent theory can prove anything it can express. PA does not prove this sentence undecidable. Outside of PA (often called in the metatheory) we can argue that if PA could prove $Con(PA)=lnot exists x Proof(x,z)$ it would be inconsistent. This is Gödel's second incompleteness theorem.

share|cite|improve this answer

answered Jul 24 at 2:38

Ross Millikan

275k21186351

add a comment | 

up vote
0
down vote

In the presentations I have seen the proof of incompleteness is not in the base theory. We have a base theory, like Peano Arithmetic (PA), and we construct a sentence in the language of PA that we can argue outside of PA is undecidable inside of PA. That convinces us as observers that PA is incomplete.

The original Gödel proof constructed a predicate $Proof(x,y)$ that is true if $x$ is the number representing a proof of $y$. This predicate is primitive recursive, so (with great effort) can be made quantifier free. If we let $z$ be the number representing $0=S(0)$ (the formal version of $0=1$) the statement that PA is consistent can be represented as $lnot exists x Proof(x,z)$ because an inconsistent theory can prove anything it can express. PA does not prove this sentence undecidable. Outside of PA (often called in the metatheory) we can argue that if PA could prove $Con(PA)=lnot exists x Proof(x,z)$ it would be inconsistent. This is Gödel's second incompleteness theorem.

share|cite|improve this answer

answered Jul 24 at 2:38

Ross Millikan

275k21186351

add a comment | 

up vote
0
down vote

up vote
0
down vote

In the presentations I have seen the proof of incompleteness is not in the base theory. We have a base theory, like Peano Arithmetic (PA), and we construct a sentence in the language of PA that we can argue outside of PA is undecidable inside of PA. That convinces us as observers that PA is incomplete.

The original Gödel proof constructed a predicate $Proof(x,y)$ that is true if $x$ is the number representing a proof of $y$. This predicate is primitive recursive, so (with great effort) can be made quantifier free. If we let $z$ be the number representing $0=S(0)$ (the formal version of $0=1$) the statement that PA is consistent can be represented as $lnot exists x Proof(x,z)$ because an inconsistent theory can prove anything it can express. PA does not prove this sentence undecidable. Outside of PA (often called in the metatheory) we can argue that if PA could prove $Con(PA)=lnot exists x Proof(x,z)$ it would be inconsistent. This is Gödel's second incompleteness theorem.

share|cite|improve this answer

answered Jul 24 at 2:38

Ross Millikan

275k21186351

In the presentations I have seen the proof of incompleteness is not in the base theory. We have a base theory, like Peano Arithmetic (PA), and we construct a sentence in the language of PA that we can argue outside of PA is undecidable inside of PA. That convinces us as observers that PA is incomplete.

The original Gödel proof constructed a predicate $Proof(x,y)$ that is true if $x$ is the number representing a proof of $y$. This predicate is primitive recursive, so (with great effort) can be made quantifier free. If we let $z$ be the number representing $0=S(0)$ (the formal version of $0=1$) the statement that PA is consistent can be represented as $lnot exists x Proof(x,z)$ because an inconsistent theory can prove anything it can express. PA does not prove this sentence undecidable. Outside of PA (often called in the metatheory) we can argue that if PA could prove $Con(PA)=lnot exists x Proof(x,z)$ it would be inconsistent. This is Gödel's second incompleteness theorem.

share|cite|improve this answer

answered Jul 24 at 2:38

Ross Millikan

275k21186351

share|cite|improve this answer

share|cite|improve this answer

answered Jul 24 at 2:38

Ross Millikan

275k21186351

answered Jul 24 at 2:38

Ross Millikan

275k21186351

answered Jul 24 at 2:38

Ross Millikan

275k21186351

275k21186351

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860941%2fincomplete-theory-proving-its-incompleteness-by-a-formula-neither-provable-true%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email