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.

  • 0
    ... your question.) Re$g$ard$s$,2012-04-16

3 Answers 3

7

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.

  • 3
    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.2012-04-16
2

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.

0

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).

  • 2
    Act$u$ally, in first order logic "logically valid" _is_ eq$u$ivalent to "provable". In an inconsistent theory everything is logically valid (i.e., tr$u$e in every model), beca$u$se an inconsistent theory has no models.2012-04-16