# please help - Structures and Definability

Printable View

• Dec 13th 2012, 12:28 PM
drg
please help - Structures and Definability
Hi everyone,

I need some help to understand the following question:

Given that A and B are L-structures (where we take L to be a language with countably many nonlogical symbols)
such that B is an elementary substructure of A and |A| $\neq$ |B| (where |A| and |B| are the underlying sets of A and B, respectively) ...

... show that |B| is not definable in |A| (and is not even definable allowing points from B).

These notes http://www.math.caltech.edu/~2010-11...at6cNotes7.pdf actually helped me understand better what's going on and how one would go about proving this for specific structures, but given the above definition of A and B, I do not really know where to start.

One of hints that is given is to assume, towards a contradiction, that |B| is a A-definable subset of |A|, by some formula $\phi (x)$ whose only free variable is x. Then using this formula I need to find a sentence of L true in A but false in B.

Any help would really be appreciated.
• Dec 13th 2012, 03:12 PM
Deveno
Re: please help - Structures and Definability
my guess here is the formula would be something like:

$\exists x: \lnot \phi(x)$ or to be more precise, it seems to me that if |A| ≠ |B|, but |B| is a substructure of |A| there is some element a of |A| not in |B|. assuming |B| is non-empty (perhaps this requires a separate case) we have some element b in |B|, and we have the automorphism:

f(x) = x, if x ≠ a,b
f(a) = b
f(b) = a

under which φ is not invariant.
• Dec 14th 2012, 02:04 AM
emakarov
Re: please help - Structures and Definability
Suppose |B| is definable in A by $\varphi(x)$, i.e., $A\models\varphi(b)$ iff $b\in|B|$. Then, since B is an elementary substructure of A, $B\models\varphi(b)$ for all $b\in|B|$, i.e., $B\not\models\exists x,\,\neg\varphi(x)$. On the other hand, since |B| is a proper subset of |A|, we have $A\models\exists x,\,\neg\varphi(x)$, which contradicts the fact that B is an elementary substructure of A.
• Dec 14th 2012, 12:39 PM
drg
Re: please help - Structures and Definability
That makes sense. Thanks to both of you for your help.