# Thread: Model Theory - minimal sets

1. ## 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.

2. What relations and/or functional symbols are in the language here?

3. 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$.

4. 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.