Consider the relation $R \subseteq \mathcal{P(\mathbb{N})} \times \mathcal{P(\mathbb{N})}$ where, for any $X \subseteq \mathbb{N}$ and $Y \subseteq \mathbb{N}$, $(X,Y) \in R$ if and only if there exist $u,v \in X$ such that $Y=X \cup \{u+v\}$. For example, $(\{1,2\}, \{1,2,3\}) \in R$ and $(\{1,2\}, \{1,2,4\}) \in R$, but $(\{1,2\}, \{1,2,5\}) \notin R$.
The problem is to prove whether the transitive closure of the relation $R$ is a partial order, and, if so, to find minimal, maximal, minimum, and maximum elements.
I couldn't figure out what the transitive closure looks like, but some doubts that raised were:
-
Since $\emptyset \subseteq \mathbb{N}$ and $\emptyset$ is not related to any other set (even itself I think?), does this already break the properties of a partial order? Shouldn't the properties hold for any subset of $\mathbb{N}$, in particular $\emptyset$?
-
What about singleton sets such as $\{1\} \subseteq \mathbb{N}$? Certainly, $(\{1\},\{1\}) \notin R$ because I cannot pick two elements that sum up to $1$. If I haven't missed anything, this remains true in the transitive closure, so can I claim right away that it's not reflexive, and therefore not a partial order?
I think the exercise would not ask for minimals, maximals, etc., if the transitive closure wasn't a partial order (or maybe not?). At first, I thought the singleton sets were the minimal elements, but then there is the question in (2). If the transitive closure is not a partial order, I cannot even speak of minimals, right? In addition, since the relation is defined on an infinite set, there would not be a maximum element. As for the maximals, I have no idea, I believe they don't exist either.
Best Answer
Let $S'$ be the transitive closure of $R$. As correctly said in the OP, $R$ and hence $S'$ are not reflexive (since $(\{1\},\{1\}) \notin R$), thus $S'$ is not an order (I assume that an order is a reflexive, transitive and antisymmetric binary relation).
The question is interesting if we consider instead the reflexive-transitive closure of $R$.
Let $S$ be the reflexive-transitive closure of $R$, that is, $$ (X,Y) \in S \iff \exists \, n \in \mathbb{N} : X = X_0, \ Y = X_n, \ (X_i, X_{i+1}) \in R \ \ \forall \, 0 \leq i < n $$ (note that for $n = 0$ we have $(X,X) \in S$, so $S$ is reflexive).
Let us see that $S$ is an order. As $S$ is reflexive and transitive by construction. Thus, we only have to prove that $S$ is antisymmetric.
First, note that $R$ is antisymmetric. Indeed, if $(X,Y) \in R$ and $(Y,X) \in R$ then $Y = X \cup \{x + x'\}$ for some $x, x' \in X$ and $X = Y \cup \{y + y'\}$; in particular $X \subseteq Y$ and $Y \subseteq X$, and therefore $X = Y$.
From the antisymmetry of $R$, it easily follows that $S$ is antisymmetric, and hence $S$ is an order.
The order $S$ is not total. For instance, $\emptyset$ is comparable only with itself (indeed, there is no $X \subseteq \mathbb{N}$ such that $(X,\emptyset) \in R$ or $(\emptyset, X) \in R$, so we only have $(\emptyset, \emptyset) \in S$ by reflexivity). This also means that there are not maximum or minimum elements for $S$ and that $\emptyset$ is a maximal and minimal element for $S$.
Another subset of $\mathbb{N}$ that is comparable only with istelf is $\{0\}$ (indeed, for every $X \subseteq \mathbb{N}$, if $(X,\{0\}) \in R$ or $(\{0\}, X) \in R$ then $X = \{0\}$). This also means that $\{0\}$ is a maximal and minimal element for $S$.
In general, what are the maximal elements for $S$? All and only the maximal elements for $S$ are the subsets of $\mathbb{N}$ that are closed under addition (a formal proof of this requires some knowledge on elementary number theory and deserves another post). Some examples are $\emptyset$ and $\{0\}$, but also $\mathbb{N}$ and $2\mathbb{N} = \{2n : n \in \mathbb{N}\}$ and $2\mathbb{N} \smallsetminus \{0,2\}$, and so on (the list is quite long...).
In general, what are the minimal elements for $S$? All and only the minimal elements for $S$ are the sets $X \subseteq \mathbb{N}$ whose elements are "linearly independent", that is, for ever $x \in X \smallsetminus \{0\}$, there are not $x_1, \dots, x_k \in X$ such that $x = n_1 \cdot x_1 + \dots + n_k \cdot x_k$ for some $n_1, \dots, n_k > 0$ (again, a formal proof of this requires some knowledge on elementary number theory and deserves another post). Some examples are $\emptyset$ and every singleton subset of $\mathbb{N}$ and $\{2, 5\}$, but not $\{2,5,7\}$ or $\{2,5,9\}$ because $(\{2,5\}, \{2,5,7\}) \in R$ and $(\{2,5, 7\}, \{2,5,9\}) \in R$.