Re: Enderton problem

Gc wrote:
On 5 joulu, 18:20, David Ullrich <ullr...@xxxxxxxxxxxxxxxx> wrote:
Gc wrote:
On 5 joulu, 14:08, David C. Ullrich <ullr...@xxxxxxxxxxxxxxxx> wrote:
On Tue, 4 Dec 2007 13:03:16 -0800 (PST), Gc <Gcut...@xxxxxxxxxxx>
wrote:
On 4 joulu, 02:34, dpo...@xxxxxxxxxxxxx wrote:
If you have Enderton's A Mathematical Introduction to Logic handy,
this problem comes from number 7 in chapter 2, section 6.
Consider a language with a two-place function predicate symbol <, and
let N = (N; <) be the structure consisting of the natural numbers with
their usual ordering. Show that there is some A elementarily
equivalent to N such that <A has a descending chain.
Okay, here's what I'm thinking. We let the domain of A be the set {1/
n : n in the natural numbers} and define (m, n) is in <A iff (n, m) is
in <N. So A appears to have a descending chain. Now I need to show
that A and N are elementarily equivalant. I can do this by showing A
is a model for ThN. But...how do I do this? Enderton suggests
applying the compactness theorem...but I'm not sure how this leads to
showing they are elementarily equivalent.
I don`t see why you can`t just take the non-positive integers M with
their usual ordering. That structure is isomorphic to the (N; <),
It is?
Hint: No, it's not.
Hint: It's also not elementarily equivalent to N, because for example
it does not have a least element, while N does.
Apparently you don`t know anything what you are talking about. You
have language (N,<) with usual truths about N expressible in this
language (N,<) eg. ExVy not-(y < x) is valid. Morphism means that we
have a map alfa to which holds alfa(ExVy not-(y < x)) = ExVy not-
(alfa(y)alfa(<) alfa(x). So in the positive - integers - structure
sign < is interpreted otherwise.
Yes, until the last sentence. In the model "(N,<), where < is
the usual ordering" < is _not_ interpreted "otherwise".

OK. That was a typo. I meant the non-positives.

Hint: A structure that _is_ isomporphic to N cannot possibly
be the answer to the question, since if it's isomorphic to N
it does not have a descending chain.
Look, we can of course interpret < otherwise. (N,<) is not a special,
canonical intepretation of <.
The problem was about the theory of (N,<), where < is the
usual ordering.

In our meta theory in which we do model

theory, we have in (M,<) a descending chain, were M are the non-
positive integers.
Yes if < is the usual ordering on the non-positive integers
(in which case (M,<) is not a solution because it's not
elemntarily equivalent to N).

Yes it is. Exactly the same formulas are valid in it. If nRm = (n < m)
in (N,<) and aPb = (-n > -m) in (M,<) then there is map alfa such that
nRm = (n < m) = nRm<=> -nP-m = alfa(n)Palfa(m) = (-n > -m)

I have a hard time following that because of the "a" and "b" -
they must have something to do with n and m... But never mind.

No if, as you _said_, < on M
is the inverse of the usual ordering.

But it`s just how you interpret things!

Look.

First, let me say this: When I write "N" that's an abbreviation
for "(N,<), where < is the usual order on N".

Now, N is _a_ structure. It has _an_ ordering on it, which
is _the_ interpretation of "<" in N. The question is about
_the structure N_, not about N where < is interpreted differently.

Let's say M1 = (S, <), where S is the set of non-positive integers
and < is the usual order on S. Then M1 is _not_ elementarily
equivalent to N, because N has a smallest element and M1 does
not. The sentence ExAy~(y<x) is true in N and false in M,
so they're not elementarily equivalent. QED. That sentence
is either true in M or false in M - talking about the existence
of alfa such that this and how things are interpreted doesn't
change the fact that that sentence is _true_ in N and
_false_ in M1.

Say M2 = (S, <), where S is the set of non-positive integers
and < is the reverse of the usual ordering. Then M2 _is_
elementarily equivalent to N. In fact M2 is isomorphic to
N, and hence it's clear that M2 is not a solution to the
problem either, since M2 does not contain a descending chain.



The theory of (N,<) of course
doens`t know the difference if the structures are isomorphic or even
elementarily equivalent, but the meta theory does. Look, it is like
this: meta theory of informal group theory does know the difference
between the symmetric group of order 5 and the special linear group
(2, 5) even if the axioms of the gropus doensn`t. But they are
different structures, because the nature of their elements are
different and in some different language when we are looking some
other aspects of them they might not be isomorphic.

True. So what? Does any of that imply (i) ExAy~(y<x) is false in N,
(ii) ExAy~(y<x) is true in M1, or (iii) M2 has a descending chain?

(If you think so, which one of (i), (ii) or (iii) do you think
is true? And why? If you think that ExAy~(y<x) is false in N,
please show that there exists a natural number smaller than 0.
Without any alfa's or "interpretations" - the truth or falsity
of (i) depends precisely on whether there exists a natural
number less than 0, period. If you think that ExAy~(y<x) is
true in M1, please provide a proof that there is a smallest
non-negative integer (in the _usual_ ordering). If you
think that M2 has a descending chain, please give an example
of a infinite descending chain in M2; note that that would
be a sequence of non-negative integers which is _increasing_
in the _standard_ order.)
.

Relevant Pages

  • Re: Enderton problem
    ... So A appears to have a descending chain. ... It's also not elementarily equivalent to N, ... have language with usual truths about N expressible in this ... It depends on the interpretation of "<". ...
    (sci.logic)
  • Re: Enderton problem
    ... So A appears to have a descending chain. ... It's also not elementarily equivalent to N, ... have language with usual truths about N expressible in this ... an isomorphism of the two structures. ...
    (sci.logic)
  • Re: Enderton problem
    ... their usual ordering. ... So A appears to have a descending chain. ... It's also not elementarily equivalent to N, ... an isomorphism of the two structures. ...
    (sci.logic)
  • Re: Enderton problem
    ... their usual ordering. ... have language with usual truths about N expressible in this ... elementarily equivalent, but the meta theory does. ...
    (sci.logic)
  • Re: Enderton problem
    ... their usual ordering. ... have language with usual truths about N expressible in this ... elementarily equivalent, but the meta theory does. ...
    (sci.logic)
Loading