1
$\begingroup$

So I'll try keeping this real short and simple.

Assume that language $L$ is defined as $\{ x\in \{0,1\}^* \}$ (finite binary strings) such that $x$ encodes a proof in ZFC that 4 is a prime number.

I would like to know that

  1. Is $L$ the empty language?
  2. Is $L$ is a decidable language? (That is, is there a Turing Machine that halts on every input $x\in \{0,1 \}^*$ and accepts $x$ iff $x$ is in $L$)
  3. Can the above results be proved in ZFC?

Any help will be appreciated.

$\endgroup$

1 Answer 1

3
$\begingroup$

Suppose that ZFC is inconsistent. Then there is a proof that $4$ is prime (since in an inconsistent system everything is both true and false).

On the other hand if ZFC is consistent, then there is no proof that $4$ is prime.

Thus, determining whether $L$ is empty or not is equivalent to proving the consistency of ZFC: "con(ZFC)". Godel showed that con(ZFC) follows from ZFC if and only if con(ZFC) is false.

This means that the answer to "1." is independent from ZFC.

"3." is true only if ZFC is inconsistent.

$\endgroup$
2
  • 2
    $\begingroup$ 2. can be determined - this particular set is computable regardless whether it is empty. $\endgroup$ Commented Nov 18, 2014 at 3:05
  • $\begingroup$ Thanks @CarlMummert ... I took out my (erroneous) comment about 2. :) $\endgroup$
    – Bill Cook
    Commented Nov 18, 2014 at 3:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .