In this system of axioms, it can be shown that A = 5 is undecidable

Axioms: A is a prime number, A is greater than 4, A is less than 8

This is because both A = 5 and A = 7 are consistent with these axioms.

Could you provide a toy example (sort of like the one above) of a statement and a system of axioms in which the statement's decidability is itself undecidable?

Are there statements that are undecidable but not provably undecidable

This link is similar to my question, but I would like an example using some nonstandard, non-useful system of axioms (sort of like the one above) for simplicity.

Please explain as simply as possible. I am not a math major.


Note that no "reasonable" system can prove the independence of any sentence within itself: such a system would a fortiori prove its own consistency (if anything is independent of $T$, it must be the case that $T$ can't prove ea contradiction). So we have to ask about undecidability in $T$ being proved or not proved in some further "reasonable" theory $S$. This all makes the question rather messy.

The following result however shows that in a very strong sense we'll never avoid "undecidable undecidability" (without introducing inconsistency, anyways); the key shift is away from specific axiom systems and towards computability-theoretic concerns, the point being that the latter apply to all ("reasonable") axiom systems at once.


$(*)\quad$ Assume that (say) first-order Peano arithmetic (PA) is consistent. Then the set $U$ of sentences undecidable in PA is not computable.

In particular, if $T$ is any computably axiomatizable theory which doesn't prove any false $\Sigma^0_1$ facts (specifically: doesn't prove "PA proves $\varphi$" when in fact PA does not prove $\varphi$), then there is some sentence $\varphi$ which is independent of PA but whose PA-independence is itself independent of $T$.

The proof of $(*)$ is via the following form of Godel's first incompleteness theorem:

$(**)\quad$ There is no complete consistent computable theory extending PA.

(More snappily: "PA is essentially incomplete.")

To see why $(**)$ implies $(*)$, suppose that $U$ were computable. Then we could build a computable consistent completion of PA as follows. Let $(\varphi_e)_{e\in\mathbb{N}}$ be the usual lexicographic ordering of sentences of arithmetic, and consider the following recursively-defined sequence of sentences:

We ask $U$ whether the sentence $$\theta_i\equiv(\psi_0\wedge ...\wedge\psi_{i-1})\rightarrow\varphi_i$$ is independent of PA. (For $i=0$ we set $\theta_0\equiv\varphi_0$.) If the answer is yes, we let $\psi_i=\varphi_i$. If the answer is no, we search for either a PA-proof or PA-disproof of $\theta_i$. If we find a PA-proof of $\theta_i$ we let $\psi_i=\varphi_i$; if we find a PA-disproof of $\theta_i$ we let $\psi_i=\neg\varphi_i$.

Assuming $U$ is computable, this whole procedure is computable and defines (by induction) a complete consistent theory extending PA.

Can we turn this into a "toy" example?

Well, not really: in order for a theory to even be able to talk about provability, it needs to be capable of stating and proving basic facts about finite strings of symbols. In my opinion this really rules out anything I'd consider a "toy" example. In particular, even if we go back to my first paragraph and look for a "toy" theory $T$, some sentence $\varphi$ in the language of $T$, and some "reasonable" theory $S$ such that $\varphi$ is independent of $T$ but $S$ can't prove that (note that that fact about $\varphi,T,$ and $S$ itself is proved within an implicit third theory $U$!), we still have to deal with $S$ itself not being a "toy," and the fact that $S$ will be reasonably powerful also forces $T$ to be complicated.

So I'd say that you're not going to find a toy example of this phenomenon - it's fundamentally about "arithmetized logic," which is inherently a complicated phenomenon.

| cite | improve this answer | |
  • $\begingroup$ Thank you for the question ... and what a nice answer! $\endgroup$ – jcdornano Apr 30 at 2:27

I've been trying to think of a simple example of a statement and a set of axioms in which the statement's decidability is undecidable according to the axioms.

I started with the statement "A = 5" and the axioms: A is a prime number, A is greater than 4, A is less than 8.

The statement "A = 5" is undecidable in this system of axioms because A = 5 and A = 7 are consistent with the axioms.

I again used this same logic.

I began with the statement "statement A is undecidable" and the axioms: statement A is a statement, statement A can be written on paper, statement A can be stated in English.

The statement "statement A is undecidable" is undecidable in this system of axioms because both the statements "statement A is undecidable" and "statement A is decidable" are consistent with the axioms.

Since the statement "statement A is undecidable" is undecidable in this system of axioms, this implies that statement A's decidability is undecidable in this system of axioms.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.