Re: Enderton problem

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

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). No if, as you _said_, < on M
is the inverse of the usual ordering.


so
it is also elementarily equivalent, which is a weaker property than
isomorphism but it is implied by it.
************************

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