Results 1 to 4 of 4

Thread: 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 $\displaystyle A$ is minimal if $\displaystyle A$ is infinite but the only subsets of $\displaystyle \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 $\displaystyle X \subseteq \mbox{dom}(A)$ which is first-order definable with parameters is said to be minimal if $\displaystyle X$ is infinite, and for every set $\displaystyle Z$ which is first-order definable in $\displaystyle A$ with parameters, either $\displaystyle X \cap Z$ or $\displaystyle X\backslash Z$ is finite. "

    And now the exercise:

    == Let $\displaystyle A$ be the graph whose vertices are all the sets $\displaystyle \{m, n\}$ of exactly two natural numbers, with $\displaystyle a$ joined to $\displaystyle b$ iff $\displaystyle a \cap b \neq \varnothing \wedge a \neq b$. Show that $\displaystyle 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,577
    Thanks
    790
    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:

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

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    The vertex {0,1} is adjacent to infinitely many vertices, but also is non-adjacent to infinitely many vertices. Therefore, $\displaystyle \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: Mar 10th 2011, 05:26 AM
  2. Model Theory - definiable classes
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 19th 2010, 09:21 AM
  3. Model theory - definiable sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 19th 2010, 09:12 AM
  4. Model theory - definiable sets 2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 16th 2010, 12:08 PM
  5. Model theory - definiable sets
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Nov 16th 2010, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum