Re: Enderton problem

On Wed, 5 Dec 2007 14:19:29 -0800 (PST), Gc <Gcut667@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.

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?

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

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.

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.

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.

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.

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.

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?

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".

(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.)

The interpration what you are asking is impossible in the (M,<).
Surely we agree that you can`t interpred our theory eg the all truths
of N expressible in the language of (N,<) that way in the model (M,<),
because that would be contradictory?

Gorble freck.


************************

David C. Ullrich
.

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 ... 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
    ... 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)
  • Re: Enderton SOLUTION
    ... Add some constants to the language, ... So it's still true that M' contains a descending chain, ... Two structures A and B are elementarily equivalent iff they are ... similar and for EVERY first order language ...
    (sci.logic)
  • Re: Enderton problem
    ... our language. ... The problem asked for a structure where, according to the interpretation ... and also where there is an infinite descending chain ... Alan Smaill ...
    (sci.logic)