# Thread: Model Theory - minimal sets

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

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

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

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