Re: Gdel, Turing, and Cantor
From: Jeffrey Ketland (ketland_at_ketland.fsnet.co.uk)
Date: 09/16/04
- Next message: Randy Poe: "Re: I do not have any more time for you cowards, but James is more a man than any of you"
- Previous message: Jack Sarfatti: "Zero Point Energy, Gravity and Cold Fusion"
- In reply to: Michael Jørgensen: "Re: Gdel, Turing, and Cantor"
- Next in thread: Jeffrey Ketland: "Re: Gdel, Turing, and Cantor"
- Reply: Jeffrey Ketland: "Re: Gdel, Turing, and Cantor"
- Messages sorted by: [ date ] [ thread ]
Date: Thu, 16 Sep 2004 15:27:49 +0100
Michael Jørgensen wrote in message
<41493ea6$0$182$edfadb0f@dread11.news.tele.dk>...
>Just what does it mean that a statement is "true"? Within a formal system
it
>surely only makes sense to discuss statements that are "provable true" or
>"provable false". So when you say that "AxP(x) is true", does that have any
>meaning in PA? Is it verifiable within PA?
If your formal system is meaningless, then no question of truth arises, only
the question of the existence of finite sequences of certain sorts (formal
derivations). If one believes that all mathematical theories are such
uninterpreted formal systems, then this is the ideology of one version of
formalism. But this doesn't really make sense, because the theory of finite
sequences (and operations on sequences, such as concatenation and
substitution) is just as undecidable as the theory of numbers.
In short, formalism tries to reduce mathematics to syntax, perhaps hoping
that all syntactical problems have a decision procedure. But the Goedelian
incompleteness theorems apply just as much to syntax as they do to number
theory. I.e., there are truths of syntax, that no interpreted, consistent,
recursively axiomatized theory of syntax proves.
If, however, the formal system is attached to the interpreted language of
arithmetic, then the question of truth does arise. PA is usually understood
to be a formalization of part of our informal knowledge of the properties of
natural numbers. The language of arithmetic is therefore an interpreted
language. The quantifiers of L_{PA} range over the set of numbers {0, 1, 2,
...}, and the symbols "0", "S", "+" and "x" have their obvious meanings: the
number zero, the successor, addition and multiplication operations. I.e.,
"0" denotes zero, etc.
In this setting, as Torkel Franzen pointed out (following Alfred Tarski,
1933), the notion of truth behaves exactly as it intuitively should. So,
"AxP(x) is true" means "every number n has property P". Similarly, the
statement "Goodstein's theorem is true" means simply "every Goodstein
sequence converges to zero". This is the best way to respond to certain
kinds of scepticism about the use of the notion of truth.
If you really want to know the inductive definition of truth for the
language of arithmetic, here it is (sentences of the language are built up
from equations of terms, and negations, conjunctions and universal
quantifications):
(i) An equation t=u is true iff the value of t = the value of u;
(ii) A negation ~phi is true iff phi is not true;
(iii) A conjunction phi & psi is true iff phi is true and psi is true;
(iv) A quantification Ax phi(x) is true iff, for all n, phi(n) is true.
It turns out (Tarski's Indefinability Theorem) that this definition cannot
be expressed in the language of arithmetic.
If you permit quantification over sets of sentences, then one can convert
this inductive definition to a direct definition of the set Tr of true
arithmetic sentences. Roughly, Tr is the smallest set X of arithmetic
sentences satisfying conditions (i)-(iv).
One can also define Tr by first defining the structure (N, 0, S, +, x) of
the natural numbers. Then Tr is identical to the set of sentences which are
true in (N, 0, S, +, x).
>In other words, among the statements that are undecidable, i.e. U=^(S | T),
>does it make sense to further subdivide this set into statements that are
>true versus those that are false.
Yes.
>How can they be distinguished within PA?
They can't (not all of them), and not even in any consistent formal system
(whose axiom set is recursive).
In a nutshell: the set Tr of arithmetic truths is not axiomatizable.
>The way I see it, one needs some device *outside* PA in order to define the
>notion of "true".
Right. The inductive definition I wrote down above does this, and cannot be
expressed in the language of arithmetic. However, as Torkel Franzen pointed
out, if you want to define "the subset Tr_n of arithmetic truths whose
quantifier complexity is n", then this subset is definable in the language
of arithmetic. But note that definability does not entail provability (in
some formal system).
--- Jeff
- Next message: Randy Poe: "Re: I do not have any more time for you cowards, but James is more a man than any of you"
- Previous message: Jack Sarfatti: "Zero Point Energy, Gravity and Cold Fusion"
- In reply to: Michael Jørgensen: "Re: Gdel, Turing, and Cantor"
- Next in thread: Jeffrey Ketland: "Re: Gdel, Turing, and Cantor"
- Reply: Jeffrey Ketland: "Re: Gdel, Turing, and Cantor"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
