Return to Question

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "formal enough" to be productive.

So, let us suppose that we're working with an ambient logic that is classical (we believe in LEM and induction principle), and that we were able to define some formal theory in our natural language that is strong enough to have undecidable statements.

Let $A$ be any proposition of this formal theory, and call $Dec(A)$ the proposition "there exists a proof of $A$ or there exists a proof of $\neg A$". $Dec(A)$ is true iff $A$ is decidable, $Dec(A)$ being false iff $A$ is undecidable.

Notice that because of LEM, $Dec(A) = Dec(\neg A)$.

What can we say about $Dec(Dec(A))$ ? (here begins the non formal stuff, supposing we have at our disposal some stratified ``infinite order logic'' that can speak about its own propositions and proofs (say, level $n$ propositions can speak about level $m \leq n$ propositions and proofs)).

If $Dec(A)$ is right, then there either exists a proof of $A$ or a proof of $\neg A$ that we can write down as a finite string of symbols. Thus, by finding such a proof, we proved that it is possible to find a proof of $A$ or that it is possible to find a proof of $\neg A$, hence $Dec(Dec(A))$ is true. By obvious induction, $Dec^n(A)$ true implies $Dec^{n+1}(A)$ true.

This leads us to the following definition of $n$-undecidability: A proposition $A$ is said to be $n$-undecidable iff there exists some positive integer $n$ such that for all $m \leq n$, $Dec^m(A)$ is false and $Dec^{n+1}(A)$ is true.

We can also define the notion of $\infty$-undecidability: We call $\infty$-undecidable, any proposition $A$ such that for all $n$, $Dec^n(A)$ is false.

Question: can we prove that an $\infty$-undecidable proposition exists ? It appears that not: Let $A$ be any proposition, and let $B$ = there exists an $\infty$-undecidable proposition. What can we say about $Dec(B)$ ?

If $Dec(B)$ is true, then we can either find a proof of $B$ or a proof of $\neg B$. Finding a proof of $B$ means to find a statement $C$ and to prove that for all $n$, $Dec^n(C)$ is false. This implies that $Dec^{n+1}(C)$ is true, and hence contradiction. If we can find a proof of $\neg B$, that is, a proof that there exists no $\infty$-undecidable statement, this means that for all statements $C$ we can find an $n$ such that $Dec^n(C)$ is true, and in particular, for $C = B$. Thus there exists an $n$ such that $Dec^n(B)$ is true and it therefore becomes decidable to know if it is decidable ... that there exists an $\infty$-undecidable proposition.

If $Dec(B)$ is false, what can we say about $Dec^n(B)$ for all $B$ ? It appears that there must exist some $m$ such that $Dec^m(B)$ is true too, or we would have found a proof that there exists an infinitely undecidable statement, and hence contradiction.

Any comment, recommandations, references about this stuff?

PS: it really looks like that one needs to have a theory that is able to speak about its own lower level propositions and proofs, say, an infinite order stratified language.

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "formal enough" to be productive.

So, let us suppose that we're working with an ambient logic that is classical (we believe in LEM and induction principle), and that we were able to define some formal theory in our natural language that is strong enough to have undecidable statements.

Let $A$ be any proposition of this formal theory, and call $Dec(A)$ the proposition "there exists a proof of $A$ or there exists a proof of $\neg A$". $Dec(A)$ is true iff $A$ is decidable, $Dec(A)$ being false iff $A$ is undecidable.

Notice that because of LEM, $Dec(A) = Dec(\neg A)$.

What can we say about $Dec(Dec(A))$ ? (here begins the non formal stuff, supposing we have at our disposal some stratified ``infinite order logic'' that can speak about its own propositions and proofs (say, level $n$ propositions can speak about level $m \leq n$ propositions and proofs)).

If $Dec(A)$ is right, then there either exists a proof of $A$ or a proof of $\neg A$ that we can write down as a finite string of symbols. Thus, by finding such a proof, we proved that it is possible to find a proof of $A$ or that it is possible to find a proof of $\neg A$, hence $Dec(Dec(A))$ is true. By obvious induction, $Dec^n(A)$ true implies $Dec^{n+1}(A)$ true.

This leads us to the following definition of $n$-undecidability: A proposition $A$ is said to be $n$-undecidable iff there exists some positive integer $n$ such that for all $m \leq n$, $Dec^m(A)$ is false and $Dec^{n+1}(A)$ is true.

We can also define the notion of $\infty$-undecidability: We call $\infty$-undecidable, any proposition $A$ such that for all $n$, $Dec^n(A)$ is false.

Question: can we prove that an $\infty$-undecidable proposition exists ? Let $B$ = there exists an $\infty$-undecidable proposition. What can we say about $Dec(B)$ ?

If $Dec(B)$ is true, then we can either find a proof of $B$ or a proof of $\neg B$. Finding a proof of $B$ means to find a statement $C$ and to prove that for all $n$, $Dec^n(C)$ is false. This implies that $Dec^{n+1}(C)$ is true, and hence contradiction. If we can find a proof of $\neg B$, that is, a proof that there exists no $\infty$-undecidable statement, this means that for all statements $C$ we can find an $n$ such that $Dec^n(C)$ is true, and in particular, for $C = B$. Thus there exists an $n$ such that $Dec^n(B)$ is true and it therefore becomes decidable to know if it is decidable ... that there exists an $\infty$-undecidable proposition.

If $Dec(B)$ is false, what can we say about $Dec^n(B)$ for all $B$ ? It appears that there must exist some $m$ such that $Dec^m(B)$ is true too, or we would have found a proof that there exists an infinitely undecidable statement, and hence contradiction.

Any comment, recommandations, references about this stuff?

PS: it really looks like that one needs to have a theory that is able to speak about its own lower level propositions and proofs, say, an infinite order stratified language.

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "formal enough" to be productive.

So, let us suppose that we're working with an ambient logic that is classical (we believe in LEM and induction principle), and that we were able to define some formal theory in our natural language that is strong enough to have undecidable statements.

Let $A$ be any proposition of this formal theory, and call $Dec(A)$ the proposition "there exists a proof of $A$ or there exists a proof of non $A$". $Dec(A)$ is true iff $A$ is decidable, $Dec(A)$ being false iff $A$ is undecidable.

Notice that because of LEM, $Dec(A) = Dec($non $A)$.

What can we say about $Dec(Dec(A))$ ? (here begins the non formal stuff, supposing we have at our disposal some stratified ``infinite order logic'' that can speak about its own propositions and proofs (say, level $n$ propositions can speak about level $m \leq n$ propositions and proofs)).

If $Dec(A)$ is right, then there either exists a proof of $A$ or a proof of non $A$ that we can write down as a finite string of symbols. Thus, by finding such a proof, we proved that it is possible to find a proof of $A$ or that it is possible to find a proof of $A$, hence $Dec(Dec(A))$ is true. By obvious induction, $Dec^n(A)$ true implies $Dec^{n+1}(A)$ true.

This leads us to the following definition of $n$-undecidability: A proposition $A$ is said to be $n$-undecidable iff there exists some positive integer $n$ such that for all $m \leq n$, $Dec^m(A)$ is false and $Dec^{n+1}(A)$ is true.

We can also define the notion of $\infty$-undecidability: We call $\infty$-undecidable, any proposition $A$ such that for all $n$, $Dec^n(A)$ is false.

Question: can we prove that an $\infty$-undecidable proposition exists ? It appears that not: Let $A$ be any proposition, and let $B$ = there exists an $\infty$-undecidable proposition. What can we say about $Dec(B)$ ?

If $Dec(B)$ is true, then we can either find a proof of $B$ or a proof of $non B$. Finding a proof of $B$ means to find a statement $C$ and to prove that for all $n$, $Dec^n(C)$ is false. This implies that $Dec^{n+1}(C)$ is true, and hence contradiction. If we can find a proof of $non B$, that is, a proof that there exists no $\infty$-undecidable statement, this means that for all statements $C$ we can find an $n$ such that $Dec^n(C)$ is true, and in particular, for $C = B$. Thus there exists an $n$ such that $Dec^n(B)$ is true and it therefore becomes decidable to know if it is decidable ... that there exists an $\infty$-undecidable proposition.

If $Dec(B)$ is false, what can we say about $Dec^n(B)$ for all $B$ ? It appears that there must exist some $m$ such that $Dec^m(B)$ is true too, or we would have found a proof that there exists an infinitely undecidable statement, and hence contradiction.

Any comment, recommandations, references about this stuff?

PS: it really looks like that one needs to have a theory that is able to speak about its own lower level propositions and proofs, say, an infinite order stratified language.

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "formal enough" to be productive.

So, let us suppose that we're working with an ambient logic that is classical (we believe in LEM and induction principle), and that we were able to define some formal theory in our natural language that is strong enough to have undecidable statements.

Let $A$ be any proposition of this formal theory, and call $Dec(A)$ the proposition "there exists a proof of $A$ or there exists a proof of $\neg A$". $Dec(A)$ is true iff $A$ is decidable, $Dec(A)$ being false iff $A$ is undecidable.

Notice that because of LEM, $Dec(A) = Dec(\neg A)$.

What can we say about $Dec(Dec(A))$ ? (here begins the non formal stuff, supposing we have at our disposal some stratified ``infinite order logic'' that can speak about its own propositions and proofs (say, level $n$ propositions can speak about level $m \leq n$ propositions and proofs)).

If $Dec(A)$ is right, then there either exists a proof of $A$ or a proof of $\neg A$ that we can write down as a finite string of symbols. Thus, by finding such a proof, we proved that it is possible to find a proof of $A$ or that it is possible to find a proof of $\neg A$, hence $Dec(Dec(A))$ is true. By obvious induction, $Dec^n(A)$ true implies $Dec^{n+1}(A)$ true.

This leads us to the following definition of $n$-undecidability: A proposition $A$ is said to be $n$-undecidable iff there exists some positive integer $n$ such that for all $m \leq n$, $Dec^m(A)$ is false and $Dec^{n+1}(A)$ is true.

We can also define the notion of $\infty$-undecidability: We call $\infty$-undecidable, any proposition $A$ such that for all $n$, $Dec^n(A)$ is false.

Question: can we prove that an $\infty$-undecidable proposition exists ? It appears that not: Let $A$ be any proposition, and let $B$ = there exists an $\infty$-undecidable proposition. What can we say about $Dec(B)$ ?

If $Dec(B)$ is true, then we can either find a proof of $B$ or a proof of $\neg B$. Finding a proof of $B$ means to find a statement $C$ and to prove that for all $n$, $Dec^n(C)$ is false. This implies that $Dec^{n+1}(C)$ is true, and hence contradiction. If we can find a proof of $\neg B$, that is, a proof that there exists no $\infty$-undecidable statement, this means that for all statements $C$ we can find an $n$ such that $Dec^n(C)$ is true, and in particular, for $C = B$. Thus there exists an $n$ such that $Dec^n(B)$ is true and it therefore becomes decidable to know if it is decidable ... that there exists an $\infty$-undecidable proposition.

If $Dec(B)$ is false, what can we say about $Dec^n(B)$ for all $B$ ? It appears that there must exist some $m$ such that $Dec^m(B)$ is true too, or we would have found a proof that there exists an infinitely undecidable statement, and hence contradiction.

Any comment, recommandations, references about this stuff?

PS: it really looks like that one needs to have a theory that is able to speak about its own lower level propositions and proofs, say, an infinite order stratified language.