Re: Torkel Franzen on truth



Alan Smaill wrote:
kleptomaniac666_@xxxxxxxxxxx writes:
On Dec 5, 4:29 pm, Alan Smaill <sma...@xxxxxxxxxxxxxxxx> wrote:
george <gree...@xxxxxxxxxx> writes:
On Dec 4, 8:32 pm, kleptomaniac6...@xxxxxxxxxxx wrote:

Also, would it not be the case that independence from PA would imply that
FLT is true?
As FLT can be expressed as a pi-1 sentence.

I do not see how to do that (express FLT as a Pi-1 sentence in the
language of PA), since the language of PA does not include an
exponentiation operator.

the expressibility of exponentiation in PA
was done by Goedel in his proof of incompleteness (and it's serious work).
Not sure if this would allow a pi-1 formulation, though.

--
Alan Smaill

I thought (though I could be wrong) that there was a general principle
that any statement in the language of first order arithmetic which
took the form: every positive integer has the property p, where p is a
property that can be algorithmically checked can be expressed as a
pi-1 sentence.

I'm not convinced;
according to Smullyan, the relation x^y = z is sigma-1 wrt PA.

In "Godel, Escher, Bach" Hofsteder mentions the difficulty of
defining "z is a power of x" in PA and challenges the reader to
define the simpler "z is a power of two".

I came up with "z has no odd factor greater than one". I don't know
if that's pi-1 or sigma-1. :-)

--
hz
.

Relevant Pages

  • Re: Torkel Franzen on truth
    ... As FLT can be expressed as a pi-1 sentence. ... language of PA), since the language of PA does not include an ... the expressibility of exponentiation in PA ...
    (sci.logic)
  • Re: Torkel Franzen on truth
    ... As FLT can be expressed as a pi-1 sentence. ... language of PA), since the language of PA does not include an ... the expressibility of exponentiation in PA ...
    (sci.logic)
  • Re: Torkel Franzen on truth
    ... As FLT can be expressed as a pi-1 sentence. ... exponentiation operator. ... the expressibility of exponentiation in PA ...
    (sci.logic)
  • Re: BASIC is still the best programming language!!!
    ... when I was writing a lot of C++ code ... A programming language should be designed to discourage the ... You like to bash COBOL. ... Relying on expressibility instead ...
    (comp.programming)
  • Re: True, False or unknown?
    ... A Pi-1 sentence is a sentence in the language of arithmetic of the form ... where P is Delta-0 formula, that is, a formula with only bounded ... The Goldbach conjecture, in its straightforward formalisation in the ...
    (sci.logic)
Quantcast