Results 1 to 4 of 4

Math Help - Model Theory - minimal sets

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    70

    Model Theory - minimal sets

    This time I've task with minimal sets.

    "We say that a structure A is minimal if A is infinite but the only subsets of \mbox{dom}(A) which are first-order definable with parameters are either finite or cofinite (i.e. complements of finite sets). More generally a set X \subseteq \mbox{dom}(A) which is first-order definable with parameters is said to be minimal if X is infinite, and for every set Z which is first-order definable in A with parameters, either X \cap Z or X\backslash Z is finite. "

    And now the exercise:

    == Let A be the graph whose vertices are all the sets \{m, n\} of exactly two natural numbers, with a joined to b iff a \cap b \neq \varnothing \wedge a \neq b. Show that A is not minimal, but it has infinitely many minimal subsets. ==


    I'll be grateful if this problem someone can show me step by step. When I understand this exercise I'll do the rest from my list. Because of this I'm asking for details. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    What relations and/or functional symbols are in the language here?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    70
    I know only that:

    G - graph.
    The elements of G are the vertices. There is one binary relation R^{G}. The ordered pair (a,b) lies in R^{G} iff there is an edge joining a to b.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    The vertex {0,1} is adjacent to infinitely many vertices, but also is non-adjacent to infinitely many vertices. Therefore, \exists x.\,R(\{0,1\},x) defines an infinite set whose complement is also infinite. Therefore, A is not minimal.

    My guess about the second part is to consider an infinite set of vertices that are pairwise non-adjacent, such as {{0, 1}, {1, 2}, {3, 4}, ...}. There are infinitely many such sets. The claim is that such sets are minimal because R is always false on them. I'll think more and post an update tomorrow.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Minimal Generating Sets (Basis) for a Group
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: March 10th 2011, 05:26 AM
  2. Model Theory - definiable classes
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 19th 2010, 09:21 AM
  3. Model theory - definiable sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 19th 2010, 09:12 AM
  4. Model theory - definiable sets 2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2010, 12:08 PM
  5. Model theory - definiable sets
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 16th 2010, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum