# Suppose that $Z \subseteq Y \subseteq X$ and that $f:X \to Z$ is bijective. Then $A$ is the minimal element of $\mathcal{F}$

Please have a look at the below proof and check whether it contain any error. I'm very thankful for your help!

Theorem:

Let $Z \subseteq Y \subseteq X, \space f:X \to Z$ is bijective, $\mathcal{F}=\{ V\subseteq X \mid (X-Y) \subseteq V \text{ and } f(V) \subseteq V \}$, and $A=A_0\cup A_1\cup A_2\cup\cdots$ where $A_0=X-Y$ and $A_{n+1}=f(A_n)$. Then $\forall V\in\mathcal{F},A\subseteq V$.

Proof:

1. $A \in \mathcal{F}$

$f(A)=f(A_0\cup A_1\cup A_2\cup\cdots)=f(A_0)\cup f(A_1)\cup f(A_2)\cup\cdots=A_1\cup A_2\cup A_3\cup\cdots \implies$ $f(A) \subseteq A$. Furthermore, $A=A_0\cup A_1\cup A_2\cup\cdots \implies A=A_0 \cup f(A)=(X-Y)\cup f(A)$ $\implies (X-Y)\subseteq A$. Thus, $f(A) \subseteq A$ and $(X-Y)\subseteq A \implies A \in \mathcal{F}$.

2. $\forall A'\subsetneq A, A'\notin \mathcal{F}$

$A_0 =X-Y \implies A_0 \cap Y=\varnothing. A_{n+1}=f(A_n) \implies A_{n+1} \subseteq Y \space \forall n \in \mathbb{N}\implies A_0\cap A_n =\varnothing\space\forall n>0 \text{ (and we also know that } f \text{ is injective) }\implies f^m(A_0) \cap f^m(A_n)=\varnothing\space\forall m\in\mathbb{N}\text{ and } n>0\implies A_m \cap A_{m+n} =\varnothing \space \forall m \in \mathbb{N} \text{ and } n>0 \implies A_m \cap A_n =\varnothing \space \forall m \neq n.$

Thus $A$ is the union of disjoint sets. As a result, if $x\in A$, then $x$ only belongs to a unique $A_n$. For $A'\subsetneq A$, let $i=\min \{n \in \mathbb{N} \mid \exists x\in A_n \text{ such that } x\notin A'\}$. It's clear that $\exists y\in A_i \text{ such that } y\notin A'$ and that $A_n \subseteq A' \space\forall n<i$. We have two cases in total.

a. $i=0$

$\implies y \in A_0 \implies y \in X-Y \implies X-Y \not \subseteq A' [\text{ since } y\notin A'] \implies A' \notin \mathcal{F}.$

b. $i>0$

$\implies i=t+1 \implies A_t \subseteq A' \implies f(A_t) \subseteq f(A') \implies A_{t+1} \subseteq f(A') \implies y \in f(A')$. We have that $y \in f(A')$ and $y \notin A' \implies f(A') \not \subseteq A' \implies A' \notin \mathcal{F}.$

3. $\forall V'\in\mathcal{F},A\cap V' \in \mathcal{F}$

$A\in\mathcal{F}\implies X-Y\subseteq A$ and $f(A)\subseteq A$. $V'\in\mathcal{F}\implies X-Y\subseteq V'$ and $f(V')\subseteq V'$. Thus $X-Y\subseteq A\cap V' \text{ and } f(A\cap V')=f(A)\cap f(V')$ [Since $f$ is injective] $\subseteq A\cap V'.$ This implies $A\cap V' \in \mathcal{F}$.

4.$\forall V\in\mathcal{F},A\subseteq V$

Assume the contrary, i.e. $\exists V'\in\mathcal{F},A\not\subseteq V' \implies \exists a\in A, a\notin V' \implies A\cap V'\subsetneq A$ and $A\cap V' \in\mathcal{F}$. But this contradicts the fact that $\forall A'\subsetneq A, A'\notin \mathcal{F}$. Thus $\forall V\in\mathcal{F},A\subseteq V$, or equivalently $A$ is the minimal element of $\mathcal{F}$. $$\tag*{\blacksquare}$$

• This is a bit off topic but may i ask which text are you using because i have seen some of your recent posts and the problems therein seem quite interesting. – Atif Farooq Apr 24 '18 at 13:30
• @AtifFarooq, most of my questions are proofs about fundamental things in set theory and arithmetic. They are not entirely in any textbook, but for your question, I'm self-study textbook amazon.com/Course-Mathematical-Analysis-Foundations-Elementary/…. – LE Anh Dung Apr 24 '18 at 16:38
• For part 2, it suffices to observe that if $f(V)\subset V$ then by induction on $n$ we have $f^n(V)\subset V$ for all $n\geq 0.$. So if $V\in F$ then $V\supset X-Y$ and $V= \cup_{n\geq 0}f^n(V)\supset \cup_{n\geq 0}f^n(X-Y)=A.$... Part 1 is fine. I have not examined your work in Part 2. – DanielWainfleet Apr 25 '18 at 1:12
• Hi @DanielWainfleet, I'm very curious about why you didn't go on to check Part 2 (You have already checked Part 1). – LE Anh Dung Apr 26 '18 at 14:52
• I was tired. And I saw a short method that i decided to share – DanielWainfleet Apr 26 '18 at 16:20

It suffices to prove $B \notin \mathcal F$.
Why? Perhaps $A \setminus \{x\}\notin \mathcal F$ for all $x \in A$, but if we take away a whole bunch of points -- say we remove $X \subset A$, where $X$ contains more than one point -- then $A \setminus X \in \mathcal F$. This doesn't immediately seem absurd. So the "It suffices..." point, in my opinion, requires argument.
Other than that, it'd probably be better to note where you used the hypothesis that $f$ is bijective in the beginning of step 2, but you did use it validly.
• At step 2, i used the hypothesis "$f$ is bijective" in $A_0\cap A_n =\varnothing\space\forall n>0 \text{ (and we also know that } f \text{ is injective) }\implies f^m(A_0) \cap f^m(A_n)=\varnothing\space\forall m$ $\in\mathbb{N}\text{ and } n>0$. Thank you for discovering my mistake in It suffices to prove $B \notin \mathcal{F}$. I have fixed that error too. Please have a look and check. Thank you so much! – LE Anh Dung May 12 '18 at 15:58