Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Can L(<) be the language of the naturals?
Replies: 35   Last Post: Sep 10, 2013 2:12 AM

 Messages: [ Previous | Next ]
 Jim Burns Posts: 1,200 Registered: 12/6/04
Re: Can L(<) be the language of the naturals?
Posted: Sep 1, 2013 12:35 PM

[Postscript: I think I spelled trichotomy wrong.]

There was some discussion recently of various subsets of
"the language of arithmetic" (scare quotes because I'm not
very familiar with all this). This question is part of
that one, I suppose, except that I am not interested in
whether the definitions are Nam-positive or Nam-negative.

If I say that I have a set with a semi-infinite,
discrete, linear order, (N, <), is that enough to
define the naturals?

Specifically, if I say

Ax Ay Az
(x<y)&(y<z) -> (x<z)

[Second try:]
Ax Ay
( (x<y)&(~ x=y)&(~ y<x) ) V
( (x=y)&(~ x<y)&(~ y<x) ) V
( (y<x)&(~ x<y)&(~ x=y) )

Ax Ay ( x < y ) ->
( Ez( ( x < z =< y ) & ~Ew( x < w < z ) ) )

Ax Ay ( x < y ) ->
( Ez( ( x =< z < y ) & ~Ew( z < w < y ) ) )

Ex Ay ( x =< y )

~Ex Ay ( y =< x )

(where there is no important difference between having
a lower bound and no upper bound or vice versa),
then it looks like I can define 0 and S and prove their
necessary properties -- except possibly for induction.

x = 0 <-> Ay ( x =< y )

Sx = y <-> (x<y) & ~Ez( x < z < y )

E!x ( x = 0 )

Ax E!y ( Sx = y )

~Ex ( Sx = 0 )

Ax Ay ( Sx = Sy ) -> ( x = y )

I suspect that this is well-known among those who
know it well.

Is this right?

Is there a better way of putting it?

Is this enough to make induction available?
If not, what would I need to add in order to be able to
support induction as well?

Date Subject Author
9/1/13 Jim Burns
9/1/13 Jim Burns
9/1/13 David Hartley
9/1/13 Peter Percival
9/1/13 Virgil
9/1/13 Peter Percival
9/1/13 Virgil
9/2/13 albrecht
9/6/13 albrecht
9/6/13 Robin Chapman
9/6/13 Tucsondrew@me.com
9/6/13 LudovicoVan
9/6/13 Tucsondrew@me.com
9/7/13 albrecht
9/6/13 Michael F. Stemper
9/7/13 albrecht
9/6/13 FredJeffries@gmail.com
9/7/13 albrecht
9/7/13 FredJeffries@gmail.com
9/8/13 albrecht
9/6/13 Robin Chapman
9/6/13 Brian Q. Hutchings
9/7/13 albrecht
9/6/13 LudovicoVan
9/7/13 albrecht
9/7/13 LudovicoVan
9/8/13 albrecht
9/8/13 LudovicoVan
9/8/13 albrecht
9/9/13 LudovicoVan
9/10/13 albrecht
9/1/13 Jim Burns
9/2/13 Shmuel (Seymour J.) Metz
9/2/13 Shmuel (Seymour J.) Metz
9/2/13 Shmuel (Seymour J.) Metz
9/2/13 Peter Percival