# How can any statements be proven undecidable?

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.

-
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. – Johannes Kloos Apr 16 '12 at 12:35
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. – Jason DeVito Apr 16 '12 at 12:36
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 ... – Matt E Apr 16 '12 at 12:41
... your question.) Regards, – Matt E Apr 16 '12 at 12:41

There is no contradiction of $S$ doesn't mean $S$ is true.

The standard way is to construct "models" which satisfy all the axioms yet the statement is true in some model but false in some other model.

A famous example, the parallel postulate is independent from neutral geometry. There exists Euclidean geometry, of which the postulate hold; but also Non-euclidean geometry, of which the postulate fails.

-
For example (as Jason says in a comment): In the theory of groups, the "commutative law" is undecidable. To show this, you can exhibit two groups, one commutative, the other noncommutative. – GEdgar Apr 16 '12 at 12:52

There is a difference between "logically valid" and "provable". Some theorems can be proven; that is, they can be deduced from the axioms. That does not always imply that those theorems are logically valid (specifically in inconsistent theories), because logical validity is about "evaluating" specific statements, such as "$5>3$". It is either true or false, and in this case it is logically valid, and it is provable even ($1>0$, so $1+1>0$, so $2>0$ so $5>3$, depending on the axiom system you assume).

-
Actually, in first order logic "logically valid" is equivalent to "provable". In an inconsistent theory everything is logically valid (i.e., true in every model), because an inconsistent theory has no models. – Henning Makholm Apr 16 '12 at 14:09

The idea is that provability is a syntatic concept while truth is semantic.

Formally, a mathematical statement is simply a sequence of characters (often involving things like "(", "$\forall$ ", "$x_1$", "$\wedge$", etc). A proof is a simply a particular kind of sequence of characters. Note that while these characters have generally agreed upon meanings, we are NOT applying them at this stage - a proof really is just a "special type" of sequence of characters.

When one says "I can't prove statement X from axioms A", one (officially) means that there does not exist a "special type" of sequence of characters beginning with things in A and ending with X. Note that there is no notion of whether or not "X is true" at this point.

Now, one of the most common ways one shows "I can't prove statement X from axioms A" is by exhibiting a model M of A which certain properties. A model is a set together with interpretations of any constants, functions, and relations. A model allows us to interpret a syntatic formal-string-of-characters mathematics statement as an honest to goodness mathematical statement, which then has a true or false value.

Then, in order to show "I can't prove statement X from axioms A", one commonly exhibits two models M and M' (i.e., 2 different interpretations of the symbols appearing in your mathematical statements) with the property that in both M and M', all axioms in A are assigned the value true, while X is assigned true in M and false in M'.

The point is that whether or not X is true or false happens in the two different settings M and M', so there's no contradictions. In any given instance (model), X is either true or false but not both. Undecidability means there are models where it's true and models where it is false.

-