What relations and/or functional symbols are in the language here?
This time I've task with minimal sets.
"We say that a structure is minimal if is infinite but the only subsets of which are first-order definable with parameters are either finite or cofinite (i.e. complements of finite sets). More generally a set which is first-order definable with parameters is said to be minimal if is infinite, and for every set which is first-order definable in with parameters, either or is finite. "
And now the exercise:
== Let be the graph whose vertices are all the sets of exactly two natural numbers, with joined to iff . Show that 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.
The vertex {0,1} is adjacent to infinitely many vertices, but also is non-adjacent to infinitely many vertices. Therefore, 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.