1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LuxGiammi Dec 6 '17 at 8:14
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Dec 9 '17 at 17:18
  • $\begingroup$ That's a good proof now. $\endgroup$ – Asaf Karagila Dec 10 '17 at 11:29
  • $\begingroup$ @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!! $\endgroup$ – LuxGiammi Dec 10 '17 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.