Re: Enderton problem

On 6 joulu, 02:33, David C. Ullrich <ullr...@xxxxxxxxxxxxxxxx> wrote:
On Wed, 5 Dec 2007 14:19:29 -0800 (PST), Gc <Gcut...@xxxxxxxxxxx>
wrote:



On 5 joulu, 23:18, David Ullrich <ullr...@xxxxxxxxxxxxxxxx> wrote:
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.

Each model is an interpretation of the language and the axioms of
question.

Uh, yes.

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.

It depends on the interpretation of "<". The interpretations in each
model of the symbols in the language are each totally independent of
the some other model.

Yes. That's exactly why your comment "It depends on how you interpret
things!" makes no sense here. In each of those two models we have
_fixed_ an interpretation of <. Other interpretations are irrelevant.

This is nonsense. You can`t interpret "<" in the model (M,<) in that
way if the theory is theory of (N,<).

The sentence ExAy~(y<x) is true in N and false in M,
so they're not elementarily equivalent. QED.

If they are isomorphic, they are of course elementarily equivalent.
You can check this in for example in Hinman`s book of logic.

Of course isomorphic models are elementarily equivalent. There
have been many different things above called "M". Which one
are we talking about?

M is the non-positive integers.

The non-positive integers with the usual ordering are
not elemtarily equivalent to N. Hence they do not give
a solution to the problem.

Yes they are.

The non-positive integers, with < interpreted as the
reverse of the usual ordering, of course are isomorphic
to N. Hence they obvious do not give a solution to the problem.

It`s all about the model being isomorphic or not. And we know that the
model (M,<) has a descending chain.

Which one are you talking about right now?

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.

That would lead that (M,<) wouldn`t be a model at all to TH(N,<).

Uh, that's correct. It's not.

Yes it is. You can`t interpred "<" as being the same ordering as (M,<)
than in (N,<).
Otherwise the (M,<) wouldn`t be a model of our theory.

You
get from complete theories which have only infinite models that all
their models are caterorical.

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.

But you don`t have to make those asumptions.

Yes it does. Do you understand this? If nRm = (n < m) in (N,<) and aPb
= (-n >* -m) in (M,<) then there is map alfa such that nRm = (n < m) =
nRm<=> alfa(n)Palfa(m) = (-n >* -m) this is map alfa(n) = - m just is
an isomorphism of the two structures.

Much of the notation here makes no sense, for example defining alfa
by alfa(n) = -m. No doubt the problems are just typos, but I can't
figure out what you're trying to say.

It`s not a definition. It just says what the a(n) are.

M2 does _not_ contain a descending chain. That would be a sequence
n1, n2, n3, ... such that, _with_ the interpretation of < used in
M2, n1 > n2 > n3 ... . And that would be a sequence of non-positive
integers n1, n2, ..., such that _with_ the _usual_ interpretation of
<, n1 < n2 < ... . And there is no such sequence.

Yes there is. Look at the (-n >* -m).

An now you are claiming that isomorphic structures aren`t elementarily
equivalent.

What? M2 does not contain a descending chain. It's isomorphic to N.
N does not contain a descending chain either. How do you conclude that
I'm claiming what you say?

I have explained this now all over again. We know in our meta-theory
that (M,<) has a denceding chain, right? Now if (M,<) is a model of
our theory, then that fact doensn`t go away. You seem to think that
the model somehow chances if we interpred the theory in it.



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?

Yes. In set theory that is our meta theory we can proof that (M,<) has
a descending chain. Give me first the axioms of our theory, then I can
verify each and every one of them in the model (M,<).

This is nonsense. Tell _me_ what the descending chain _is_. That
has nothing to do with axioms in any theory, it just has to
do with the definition of "descending chain".

OK. I read the definition in wikipedia, an it is not the I thought it
was. I thought it was just a ever smaller getting chain, but I
reasoned it about your earlier post and about your solution. Can you
tell me to what constant your solution approaches?

.

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
    ... 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
    ... It's also not elementarily equivalent to N, ... have language with usual truths about N expressible in this ... It depends on the interpretation of "<". ... an isomorphism of the two structures. ...
    (sci.logic)
  • Re: Enderton problem
    ... of our language. ... and also where there is an infinite descending chain ... N is the naturals and < their usual order, ... isomorphism here is isomorphism as ordered sets. ...
    (sci.logic)
  • Re: Enderton problem
    ... their usual ordering. ... 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 ...
    (sci.logic)