I am new to this forum, so I hope my mathematical way of writing here is correct, as I have not done it much before. :(
I am taking my logics class currently and stumbled upon the following task.
We are given a structure $\mathcal{G}$ from universal algebra entailing the domain (or universe) $G$ := $\wp(\mathbb{N})$ (the power set of natural numbers), a signature $\omega:=\{\cup,\cap\ , ^c \}$ where $\{\cup,\cap\, ^c \}$ is the set of function symbols and $^c$ is merely the complement of $\{G'^c= \mathbb{N} \setminus G'$ | $G'\in\wp(\mathbb{N})\}$ - in accord with the definition. (We have a purely algebraic structure without relation symbols).
Furthermore, we are given two subsets of the universe $\wp(\mathbb{N})$ (that are, again, universes in themselves) with
(1) $\{G'' \subseteq \mathbb{N}$ | $G''$ finite}.
(2) $\{G'' \subseteq \mathbb{N}$ | $G''$, $G''^c$ infinite}.
And, the way I understood it, we are supposed to prove if there exists a substructure of $\mathcal{G}$ over the universe (1). If not, we shall give the smallest substructure of $\mathcal{G}$ which contains (1) . The same for universe (2).
So, what I do know is that a substructure $\mathcal{F}$ (with its universe $F$) has to fulfill the properties
i. The domain of $\mathcal{F}$ is contained in the domain of $\mathcal{G}$, i.e. $|\mathcal{F}| \subseteq |\mathcal{G}|$. (or $F\subseteq G$)
ii. $\mathcal{F}$ and $\mathcal{G}$ have the same signature $\omega(\mathcal{F}) = \omega(\mathcal{G}) $.
Now, I do understand that, trivially, (1) cannot be the universe of a substructure of $\mathcal{G}$ because its subsets are not closed under the complement, and (2) cannot be, either, since its subsets are not closed under union. However, I don't really know how I could find the smallest substructure of $\mathcal{G}$ that would contain (1), (2), or both. So I would really appreciate your help.
Thanks so much, Gianna
In general, if $\mathcal{A}$ is an structure and $B\subseteq A$ is a subset of the domain $A$ of $\mathcal{A}$, then $B$ is the domain of a substructure of $A$ if and only if $B$ contains all the interpretations of constant symbols in the language and is closed under all the interpretations of function symbols in the language. That is, if $c$ is a constant symbol, we require that $c^{\mathcal{A}}\in B$, and if $f$ is an $n$-ary function symbol and $b_1,\dots,b_n\in B$, we require that $f^\mathcal{A}(b_1,\dots,b_n)\in B$.
For an arbitrary subset $B\subseteq A$, there is a smallest subset $\langle B\rangle$ containing $B$ which is the domain of a substructure. This is called the substructure generated by $B$. Intuitively, $\langle B\rangle$ consists of all elements of $A$ which can be "constructed" from the constants and the elements of $B$ by applying the functions. More formally, this can be described by $$\langle B\rangle = \{t^\mathcal{A}(b_1,\dots,b_k)\mid t(x_1,\dots,x_k) \text{ is a term, and }b_1,\dots,b_k\in B\}.$$
Ok, so in the situation of your question, we have the structure $\mathcal{G} = (\wp(\mathbb{N}),\cup,\cap,^c)$, where $\cup$, $\cap$, and $^c$ are function symbols (there are no constant symbols). As you pointed out, neither of the given sets is the domain of a substructure, since (1) is not closed under complements and (2) is not closed under intersections or union. So what are the substructures they generate?
Hints:
(1) The finite subsets of $\mathbb{N}$ are closed under intersections and unions, but not under complements. So as a first step we can throw in their complements to get $\{X\subseteq \mathbb{N}\mid X\text{ is finite}\}\cup \{X\subseteq \mathbb{N}\mid X^c\text{ is finite}\}$. Is this set closed under intersections, unions, and complements?
(2) The set $F = \{X\subseteq \mathbb{N}\mid X\text{ and }X^c\text{ infinite}\}$ is closed under complements, but not under intersections and unions. Which subsets of $\mathbb{N}$ can you make by intersecting two sets in $F$? What about by taking the union of two sets in $F$?