Results 1 to 4 of 4

Math Help - please help - Structures and Definability

  1. #1
    drg
    drg is offline
    Newbie
    Joined
    Nov 2012
    From
    my mom's basement
    Posts
    4

    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.
    Last edited by drg; December 13th 2012 at 06:47 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    758

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    drg
    drg is offline
    Newbie
    Joined
    Nov 2012
    From
    my mom's basement
    Posts
    4

    Re: please help - Structures and Definability

    That makes sense. Thanks to both of you for your help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: June 7th 2012, 06:58 AM
  2. Structures and Polarity
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: September 22nd 2011, 02:58 PM
  3. A question on the definability of convolution
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 19th 2010, 04:58 AM
  4. Structures
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 27th 2008, 10:45 PM
  5. Help with Structures
    Posted in the Algebra Forum
    Replies: 5
    Last Post: June 7th 2006, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum