I am self-studying Hrbacek and Jech's Introduction to Set Theory (3rd edition), and I want to know if the following solution to problem 5.10 (c) is correct. Unfortunately the book contains no answers and the only solution manual for the book I found thought it was too trivial to include its solution. For problem 5.10 (d) I would like some sort of clue, since the hint given in the book is, I think, a typo.
Let $A$ be a non empty set and $\operatorname{Pt}{(A)}$ be the set of all partitions of $A$. Define a relation $\preceq$ in $\operatorname{Pt}{(A)}$ by: $S_1 \preceq S_2$ if and only if for every $C \in S_1$ there is $D \in S_2$ such that $C \subseteq D$. Take $T \subseteq \operatorname{Pt}{(A)}$.
- Prove $\inf{T}$ exists.
The idea is to find the greatest partition $S$ of $A$ such that, $S \preceq Q,$ for every $Q \in T$. Since $A \neq \emptyset$, take $x \in A$ and consider the set $P_x = \{ z \in A: \forall Q \in T, \exists E \in Q, (x,z \in E) \}$. Define $S = \{P_x: x \in A \}$. I want to prove $S = \inf T$. First we show $S$ is indeed a partition of $A$:
- $S$ contains non empty sets: This is easy, since for any $x \in A$, $x \in P_x$ (Remember, for every $Q \in T, A = \bigcup Q$).
- $S$ is a collection of disjoint sets: Take $P_x, P_y \in S$ and $z \in P_x \cap Py$. Then for every $Q \in T$, there is some $E \in Q$ and some $F \in Q$ such that $x,z \in E$ and $y, z \in F$. Since $E$ and $F$ belong to the partition $Q$ and $z \in E \cap F$, we must have $E = F$. This implies $P_x = P_y.$
- $A = \bigcup S$: $x \in A \Longleftrightarrow$ for every $Q \in T, x \in \bigcup Q \Longleftrightarrow$ for every $Q \in T$ there is some $E \in Q$ such that $x \in Q \Longleftrightarrow x \in P_x,$ for $x \in A$ $\Longleftrightarrow x \in \bigcup S$.
So $S \in \operatorname{Pt}{(A)}$, as desired. We now proceed to prove $S$ is indeed the infimum of $T$:
- $S$ is a lower bound of $T$: We want to show that $S \preceq R$, for every $R \in T$. So let $R$ be any partition in $T$. If $P_x \in S,$ for $x \in A$, let $F$ be the set in $R$ that contains $x$ (there is one and only one such set); we show $P_x \subseteq F$. If $z \in P_x$, then for every $Q \in T$ there is some $E \in Q$ such that $x,z \in E$. In particular, for partition $R$ we have $x,z \in F$. Then $P_x \subseteq F$ and we conclude $S \preceq R$, as wanted.
- $S = \inf{T}$: Let $S_0 \in \operatorname{Pt}{A}$ such that $S_0 \preceq Q$, for every $Q \in T$. We prove $S_0 \preceq S$, so let us take $F \in S_0$ and $x \in F$ (the set $F$ is not empty). Then, for every $Q \in T$ there is some $E \in Q$ such that $F \subseteq E$; so every element in $F$ (in particular $x$) is contained in all those sets $E$, hence $F \subseteq P_x$, with $P_x \in S$. We conclude $S_0 \preceq S$.
We conclude $\inf{T} = S$.
- Prove $\sup{T}$ exists.
For this the book suggests forming $T_0 = \{ R \in \operatorname{Pt}{(A)}: \forall Q \in T, Q \preceq R \}$, and then showing $\sup{T_0} = \inf{T}$; however I think this is a typo, and the authors meant $\sup{T} = \inf{T_0}$. For this part, actually, I am a bit lost. I tried writing the definitions, but couldn't even show $\inf{T}$ is an upper bound for $T$.
In problem 5.10 (c) I would like any feedback, especially from the very last part ($S = \inf{T}$), as it feels a bit sketchy for me. Thank you for the help.
Update: Thank you for the answer. I will fill in the details in your argument, if only for the sake of future reference:
- Prove $\inf{T}$ exists. Let us start by recalling that there is an asossiated equivalence relation $\sim_Q$ in $A$ for every $Q \in \operatorname{Pt}{(A)}$: $x \sim_Q y \Longleftrightarrow$ there is some $C \in Q$ such that $x, y \in C$.
- Let $Q, R \in \operatorname{Pt}{(A)}$. Then, $Q \preceq R \Longleftrightarrow \sim_Q \subseteq \sim_R$: First the ($\Longrightarrow$) direction: Assume $Q \preceq R$. If $x \sim_Q y$, then there is some $C \in Q$ such that $x,y \in C.$ But this implies the existence of some $D \in R$ such that $C \subseteq D$ (definition of $\preceq$). Hence $x, y$ both belong to some set in $R$ (namely $D$), so $x \sim_R y$. We concluce $\sim_Q \subseteq \sim_R$. Now the ($\Longleftarrow$) direction: Assume $\sim_Q \subseteq \sim_R$. If $C \in Q$, then $C \neq \emptyset$, so we take some $x \in C$. The relation $\sim_Q$ is reflexive so $x \sim_Q x$, which implies $x \sim_R x$. This is, $x$ belongs to some $D \in R$. Notice this set $D$ is unique, for if $y \in C$ and $x \neq y$, then $x \sim_Q y$; this again implies $x \sim_R y$, which means $x$ and $y$ belong to the same set in $R$. But $R$ is a partition, so $x$ can belong to only one set in this partition, the set $D$. Thus, $C \subseteq D$ and $Q \preceq R$.
Now we define $\sim = \bigcap \{\sim_Q: Q \in T\}$, which is an equivalence relation in $A$ (we leave this easy verification for the reader). This relation induces a partition of $A$, $A/\sim = \{[x]_\sim: x \in A\}$, which will be denoted by $S$ for simpliticy. We show $\inf{T} = S$:
$S$ is a lower bound of $T$: We know $\sim \subseteq \sim_Q$, for every $Q \in T$. Then, $S \preceq Q$, for every $Q \in T$.
$\inf{T} = S$: Let $S_0 \in \operatorname{Pt}{(A)}$ be such that $S_0 \preceq Q$, for every $Q \in T$. Then $\sim_{S_0} \subseteq \sim_Q$, for every $Q \in T$. Hence, $\sim_{S_0} \subseteq \sim$, which implies $S_0 \preceq S$ as desired. We conclude $\inf{T} = S$.
- Prove $\sup{T}$ exists.
Let $T_0 = \{ R \in \operatorname{Pt}{(A)}: \forall Q \in T, Q \preceq R \}$. By the previous exercise, $\inf{T_0} = F$ exists and its induced equivalence relation is: $\sim_F = \bigcap\{\sim_R: R \in T_0\}$. We show $\sup{T} = F$.
$F$ is an uper bound of $T$: Take $Q \in T$. Then we have $Q \preceq R$, for every $R \in T_0$, which implies $\sim_Q \subseteq \sim_R$, for every $R \in T_0$. Hence $\sim_Q \subseteq \sim_F$, and thus $Q \preceq F$. So $F$ is an upper bound of $T$.
$\sup{T} = F$: The partition $\inf{T_0} = F$ is an upper bound for $T$, but $T_0$ is the set of upper bounds for $T$ and, then, it is the least upper bound for $T$. We conclude $\sup{T} = F$.
Your proof of the first part is fine.
You’re right about the typo in the second part: you should indeed be trying to show that $\sup T=\inf T_0$. For each $R\in\operatorname{Pt}A$ let $\sim_R$ be the associated equivalence relation on $A$: $a\sim_Rb$ iff there is an $E\in R$ such that $a,b\in E$. Then $\sim_R$ is a subset of $A\times A$, and it’s not hard to verify that for any $Q,R\in\operatorname{Pt}A$, $Q\preceq R$ iff $\sim_Q\subseteq\sim_R$. Let $\sim=\bigcap\{\sim_R:R\in T_0\}$; then $\sim$ is an equivalence relation on $A$, so it induces a partition, and it’s not hard to check that this partition is $\inf T_0$. (In fact this is an alternative approach to the first part of the problem.)
Now let $Q\in T$. Then for each $R\in T_0$ we have $Q\preceq R$ and hence $\sim_Q\subseteq\sim_R$. It follows that $\sim_Q\subseteq\bigcap\{\sim_R:R\in T_0\}=\sim$ and hence that $Q\preceq\inf T_0$. Thus, $\inf T_0$ is an upper bound for $T$, and since $T_0$ is the set of upper bounds for $T$, $\inf T_0$ is actually the least upper bound for $T$.