# Proof for a part of Tarski-Knaster th: $F: P(A) \rightarrow P(A)$ s.t. $X \subseteq Y \subseteq A \Rightarrow F(X) \subseteq F(Y)$.[…]

sorry for having provided not an helpful title, but the exercise is pretty long and it does not fit in the title.

I was wondering if you could help me with this (simple?) exercise taken from Enderton's Elements of Set Theory (Exercise 30, Chapter 3).

Assume that $F: \mathcal{P} A \longrightarrow \mathcal{P} A$ and that $F$ has the monotonicity property: $$X \subseteq Y \subseteq A \Rightarrow F(X) \subseteq F(Y)$$ Define $$B = \bigcap\{X \subseteq A | F(X) \subseteq X\} \quad \text{and} \quad C = \bigcup\{X \subseteq A | X \subseteq F(X)\}$$ a) Show that $F(B) = B$ and $F(C) = C$

b) Show that if $F(X) = X$ then $B \subseteq X \subseteq C$

I'd really love to share with you some "sketch of proof" or "what have I tried", but basically, the only thing I managed to do was starring at the sheet of paper where I copied the problem for some halves of hour then I gave up. :-( (Actually I was able to state this property for the members of B: $B = \bigcap \{X | F(X) \subseteq X \subseteq A\}$, but then I don't know what to do with that).

I was wondering if you could give me a hint (or even a complete solution; I won't read it entirely at first, I promise) for solving this problem.

Thanks a lot to everybody.

Note: I found this in math.stackexchange, but it contains too little information about the proof... :-( Moreover, I read this in a book about set theory and it does not explain (nor I know) what a lattice is.

• How about making the title a bit more descriptive of the problem itself? – Asaf Karagila Dec 4 '17 at 7:54

## 3 Answers

You did not state the "property for $B$" correctly. $B$ is a subset of $A$, and $\{X\mid F(X)\subseteq X\subseteq A\}$ is a subset of $\mathcal P(A)$. And of course, $A\neq\mathcal P(A)$.

Instead, $B$ is the intersection of all the sets in the collection that you specified. And we are going to use that to prove that $F(B)=B$.

Of course, let me start with the obvious, that (b) is just a corollary from (a). If $F(B)=B$ and $B$ is defined as above, then if $F(X)=X$, it follows that $F(X)\subseteq X$, so $X$ is in the collection whose intersection defines $B$, and therefore $B\subseteq X$. A similar argument works for $X\subseteq C$.

Now, to conclude that $B=F(B)$, we want to prove that $B\subseteq F(B)$ and that $F(B)\subseteq B$. But the second inclusion should spark something recognizable. It's the same inclusion which defines the collection whose intersection is $B$.

Moreover, if $F(B)\subseteq B$, then by monotonicity, $F(F(B))\subseteq F(B)$, and therefore $F(B)$ is in the collection, and so $B\subseteq F(B)$ by definition! So it is enough to prove that $F(B)\subseteq B$.

We have exactly two things to work with:

1. The property of $F$ as monotonous.
2. The fact that $B$ is the intersection of $\mathcal B=\{X\mid F(X)\subseteq X\}$.

From these two properties, we get that if $X\in\cal B$, then $F(X)\in\cal B$ as well, and that since $B\subseteq X$, $F(B)\subseteq F(X)$.

So if $b\in F(B)$, it follows that for all $X\in\cal B$, $x\in F(X)$, and therefore $x\in X$. In particular $x\in F(B)$ implies that for all $X\in\cal B$, $x\in X$. In other words, $x\in\bigcap\cal B$, or simply put $x\in B$.

So we have proved that $F(B)\subseteq B$. It follows from this, as explained above, that $B\subseteq F(B)$ and therefore that $B=F(B)$.

The proof of $C=F(C)$ is left as an exercised for you.

• Thanks a lot for your answer. I skimmed through it, however, I haven't got enough time to study it. I'll do that as soon as possible. Thanks a lot. – LuxGiammi Dec 6 '17 at 8:14

Let F = { x : $f(x) \subseteq x$ }, b = $\cap F$. If x in F, then $b \subseteq x, f(b) \subseteq f(x) \subseteq x.$ Thus $f(b) \subseteq b.$
So $ff(b) \subseteq f(b), f(b) \in F, b \subseteq f(b).$

The second C part is simular, in reverse order, except for the mistatement of it. This all is part of the Tarski-Knaster theorem that is about partial orders including the subset order for sets of a power set.

Both answers solved my problem. I decided, just for the sake of completeness, to write here the proof of $F(C) = C$ (hoping not to make mistakes).

In order to prove $F(C) = C$ we are going to prove $C \subseteq F(C)$ and $F(C) \subseteq C$.

Let's prove first $C \subseteq F(C)$. Define $\mathcal{C} = \{X\subseteq A | X \subseteq F(X)\}$ and $C = \bigcup \mathcal{C}$. Take $X \in \mathcal{C}$.

So: $$X\in \mathcal{C} \\ \Rightarrow X \subseteq C \qquad \text{by definition of union} \\ \Rightarrow F(X) \subseteq F(C) \qquad \text{by monotonicity of F}$$

Also: $$X \in \mathcal{C} \Rightarrow X \subseteq F(X) \qquad \text{by definition of \mathcal{C}}$$

Therefore: $$X \subseteq F(X) \land F(X) \subseteq F(C) \Rightarrow X\subseteq F(X) \subseteq F(C)$$

Now take $x \in X$. We have: $$x \in X \Rightarrow x \in F(C) \qquad \text{by inclusion}$$

So $$\forall X \in \mathcal{C}, \forall x \in X. x \in X \Rightarrow x \in F(C) \qquad \text{by arbitrariness of X \in \mathcal{C}}$$

Therefore, by definition of union (all elements of the sets that are elements of the set $\mathcal{C}$ are in $C = \bigcup \mathcal{C}$): $$\bigcup \mathcal{C} \subseteq F(C) \Rightarrow C \subseteq F(C)$$.

For the converse we start from $C \subseteq F(C)$: $$C \subseteq F(C) \\ \Rightarrow F(C) \subseteq F(F(C)) \\ \Rightarrow F(C) \in \mathcal{C} \qquad \text{by definition of \mathcal{C}}$$

Therefore: $$F(C) \in \mathcal{C} \\ \Rightarrow F(C) \subseteq \bigcup \mathcal{C} = C \qquad \text{by definition of union}$$.

Therefore: $F(C) \subseteq C \land C \subseteq F(C) \Rightarrow F(C) = C$.

Q.E.D.

• You write $X\subseteq\cal C$, is this a typo or a mistake? Also, if you proved that $C\subseteq F(C)$, then you proved that $C\in\cal C$. Use this to conclude that $F(C)\in\cal C$ and finish the proof. – Asaf Karagila Dec 9 '17 at 17:18
• That's a good proof now. – Asaf Karagila Dec 10 '17 at 11:29
• @AsafKaragila, Thanks. I corrected the typo, I was writing a comment to thank you for having found it, then I got distracted by another math question on this website. Thanks for your help! I will add the alternative proof for $F(C) \subseteq C$ as soon as possible. Thank you!! – LuxGiammi Dec 10 '17 at 11:33