Re: question about categoricity

[rearranging a bit]
Chris Menzel wrote:
> On 25 Nov 2005 19:42:03 -0800, Per Freem <perfreem@xxxxxxxxx> said:
> > ...it seems like Chris's trick in his post would work in this case to
> > show that T is not Nat-categorical.
>
> Right. I was assuming, perhaps hastily, that you had this theory in
> mind in your original post.
[snip]
> >i still cannot find a formula which
> > is true on M but not true on M'...finding such a formula should be
> > possible since they are not isomorphic.
>
> Not so. Non-isomorphic models of a theory can completely agree on the
> sentences they think are true. See the definition of "elementarily
> equivalent".

i believe we have a difference of terminology here, and since Torkel
Franzen made a similar point in his post, perhaps i'm using
unconventional terminology, but: i take sentences to mean formulas with
no free variables. as far as i know, if two models are non-isomorphic
there must be a type (i.e. a set of formulas) realized on one and not
on the other--so in the above example M' and M are clearly elementarily
equivalent since they model the same /complete/ theory but can still
satisfy not satisfy the same exact formulas, or at least satisfy them
differently--is this correct now? if it is, what would such a formula
be?

i'll give an example for which i know it works: given the structure M =
(Nat, <) and M' = (Nat - {1}, <) we can have a formula expressing 'the
element such that it is smaller than all others'. then M will have an
element 1 that is realized by this formula while M' won't have that (in
M' it will be 2) -- assuming again a language with distinct constants
for every element in M and M'.

> > first, is this reasoning correct?
>
> Well, you need to assume explicitly that every element of M is denoted
> by some constant, otherwise you might be able to define an isomorphism
> with M' even though M' contains an element not in M (e.g., if there are
> denumerably many unnamed elements in both models). And your reasoning
> above doesn't really *show* that there is no isomorphism from M to M',
> though (given the assumption just noted) the fact that k* is not the
> denotation of any constant will be crucial to that.

i see, yes i meant to make that assumption about the constants--i
apologize for not making it clearer. the reason i am trying to find
types omitted by one model of a complete theory and realized by another
to determine nonisomorphism is because the 'model existence proofs'
unfortunately do not make sense to me. i have the following attempt,
based on a proof from H. Enderton's excellent book, to show what i've
tried to do above using your suggestion slightly differently: given the
same language we had before and the same structure, our proof of there
being a nonisomorphic model M' of Th(M) can be as follows.

1. construct a language L' such that L' = L U {k}. that is, L' has an
additional constant symbol.
2. construct a set W such that: W = {c_i < k} for all i in Nat;
meaning k is larger than all the elements denoted by every constant. if
we could show that W U Th(M) has a model, then by Lowenheim-Skolem we
could conclude that it has some countable model, which would prove our
result.
3. apply compactness: show that every finite subset of W U Th(M) has a
model and conclude that W U Th(M). showing an arbitrary finite subset
has a model is trivial.

but here's the part that confuses me: for our result to hold, we must
eventually show that this model can be reduced from our extended
language L' back to L, or else what we proved is irrelevant (since we'd
be in a different language). but how is this reduction possible if L
does not have our special constant k? if it *did* have the special
constant k, then it would have to denote something in the domain, i.e.
something which is bigger than all the elements of N (the natural
numbers) which would mean our domain is uncountable, so L obviously
cannot have k. but then again, if L does not have k, I cannot see how
our structure M' can be reduced to it.

thanks!

.

Relevant Pages