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


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$.


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$}$$

  • 1
    $\begingroup$ 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. $\endgroup$ – Atif Farooq Apr 24 '18 at 13:30
  • 1
    $\begingroup$ @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/…. $\endgroup$ – Le Anh Dung Apr 24 '18 at 16:38
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Apr 25 '18 at 1:12
  • $\begingroup$ Hi @DanielWainfleet, I'm very curious about why you didn't go on to check Part 2 (You have already checked Part 1). $\endgroup$ – Le Anh Dung Apr 26 '18 at 14:52
  • $\begingroup$ I was tired. And I saw a short method that i decided to share $\endgroup$ – DanielWainfleet Apr 26 '18 at 16:20

I'd say this proof is really almost there. I think the biggest hole is

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.

  • $\begingroup$ 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! $\endgroup$ – Le Anh Dung May 12 '18 at 15:58
  • $\begingroup$ @CrazyGuy Looks much better now! $\endgroup$ – Y. Forman May 13 '18 at 2:09
  • $\begingroup$ Hi @Forman, I've posted a proof of Inclusion–Exclusion Principle but receive no answer or comment. If you have some free time, please have a look at it math.stackexchange.com/questions/2783980/…. Thank you so much! $\endgroup$ – Le Anh Dung May 18 '18 at 2:55

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.