5
$\begingroup$

As I understand it, undecidability means that there exists no proofs or contradictions of a statement.

So if you've proved $X$ is undecidable then there are no contradictions to $X$, so $X$ always holds, so $X$ is true. Similarly though, if $X$ is undecidable then $\lnot X$ is undecidable. But again, this would mean $\lnot X$ is true which is a contradiction.

  • 1
    You seem to be confusing various terms here. As far as I know, undecidability is defined for sets: A set $A$ is called undecidable if there is no algorithm that calculates, for some given $x$, whether $x \in A$ or not. What you seem to be talking about is independence of a logical statement. A logical statement $\varphi$ is called independent of some logical theory, say $T$, if both $\varphi$ and $\neg \varphi$ are compatible with the theory. To prove this, it is sufficient to show that both $T \cup \{ \varphi \}$ and $T \cup \{ \neg \varphi \}$ are satisfiable.2012-04-16
  • 6
    Are you familiar with group theory? The statement $\forall x \forall y$ $xy = yx$ is independent of the axioms of group theory (since there are both abelian and nonabelian groups). This does not mean that ALL groups are both abelian and nonabelian. Rather, it means that there are some groups which are abelian and some which are nonabelian.2012-04-16
  • 2
    The point is that "not deducible from the axioms" is not the same as "not true". The axioms may be *incomplete*, meaning that there are statements such that neither they nor their negation are deducible from the axioms. This is (presumably) what happens in the cases of undecidability you have heard about. (I write "presumably" because in some of the most famous examples, such as those involving arithmetic or set-theory, it is not known definitely that incompleteness is what is holding; an alternative possibility is that the axioms do indeed lead to a contradiction, as you envisaged in ...2012-04-16
  • 0
    ... your question.) Regards,2012-04-16

3 Answers 3