If $B \subseteq A$ and $f:A \xrightarrow{1-1} B$, prove that $\bigcap_{n \lt \omega}f^n[A]=\bigcap_{n\lt \omega}f^n[B]$

37 Views Asked by At

If after confirming the validity of my proof, someone could comment on the possibility of creating a direct proof...that would be awesome. At any rate:

Prove that $\bigcap_{n \lt \omega}f^n[A]=\bigcap_{n\lt \omega}f^n[B]$ using the following information:

i. $B \subseteq A$

ii. $f:A \xrightarrow{1-1} B$

iii. $f^n$ is simply saying iterate $f$ $n$ times (and $f^0$ is the identity function $I_A$)

iv. $A \supseteq B \supseteq f^1(A) \supseteq f^1 (B) \supseteq f^2(A) \supseteq f^2(B) \supseteq...$

The proof to iv. can be found here (as well as a more formal definition of $f^n$): If $B \subseteq A$ and $f:A\overset{1-1}\longrightarrow B$ then $A \supseteq B \supseteq f^1(A) \supseteq f^1 (B) \supseteq f^2(A) \supseteq...$

Importantly, iv. amounts to proving the following two induction claims, which will be used in this proof:

Statement 1. $\forall n \in \omega\big( f^{n+1}[A] \subseteq f^n[B]\big)$

Statement 2. $\forall n \in \omega\big( f^n[B] \subseteq f^n[A]\big)$


Proceed by contradiction: assume that $\bigcap_{n \lt \omega}f^n[A]\neq \bigcap_{n\lt \omega}f^n[B]$ and derive a contradiction.

I have broken this into two cases (based on what is meant by "not equal"):

$ \Big [\bigcap_{n \lt \omega}f^n[A]\neq \bigcap_{n\lt \omega}f^n[B] \Big] \rightarrow \Big [\bigcap_{n \lt \omega}f^n[A]\nsubseteq \bigcap_{n\lt \omega}f^n[B] \ \lor \ \bigcap_{n\lt \omega}f^n[B] \nsubseteq \bigcap_{n \lt \omega}f^n[A] \Big]$

Case One: $\bigcap_{n \lt \omega}f^n[A]\nsubseteq \bigcap_{n\lt \omega}f^n[B]$

Case Two: $\bigcap_{n\lt \omega}f^n[B] \nsubseteq \bigcap_{n \lt \omega}f^n[A]$


Case One:

$\Big [\bigcap_{n \lt \omega}f^n[A]\nsubseteq \bigcap_{n\lt \omega}f^n[B] \Big ] \rightarrow \exists x \Big( x \in \bigcap_{n \lt \omega}f^n[A] \land x \notin \bigcap_{n\lt \omega}f^n[B] \Big ) $ Call one such instance $x'$.

$x' \in \bigcap_{n \lt \omega}f^n[A] \rightarrow \forall n \in \omega \Big (x' \in f^n[A] \Big)$ $\dagger$

$x' \notin \bigcap_{n\lt \omega}f^n[B] \rightarrow \exists n \in \omega \Big (x' \notin f^n[B] \Big )$ Call one such instance $n'$.

So we have $x' \notin f^{n'}[B]$

However, we proved earlier through induction (Statement 1) that $\forall n \in \omega\big( f^{n+1}[A] \subseteq f^n[B]\big)$.

Consider when $n=n'$: we then have $f^{n'+1}[A] \subseteq f^{n'}[B]$

By our earlier universal claim $\dagger$, we know that $x' \in f^{n'+1}[A]$

But $\Big[x' \in f^{n'+1}[A] \land f^{n'+1}[A] \subseteq f^{n'}[B] \Big ] \rightarrow x' \in f^{n'}[B]$.

A contradiction

Case Two works similarly to Case One, except we will use Statement 2 instead of Statement 1. With both claims leading to contradiction, we must conclude that $\bigcap_{n \lt \omega}f^n[A]=\bigcap_{n\lt \omega}f^n[B]$.

I will include the proof for completeness.


Case Two:

$\Big [\bigcap_{n \lt \omega}f^n[B]\nsubseteq \bigcap_{n\lt \omega}f^n[A] \Big ] \rightarrow \exists x \Big( x \in \bigcap_{n \lt \omega}f^n[B] \land x \notin \bigcap_{n\lt \omega}f^n[A] \Big ) $ Call one such instance $x'$.

$x' \in \bigcap_{n \lt \omega}f^n[B] \rightarrow \forall n \in \omega \Big (x' \in f^n[B] \Big)$ $\dagger\dagger$

$x' \notin \bigcap_{n\lt \omega}f^n[A] \rightarrow \exists n \in \omega \Big (x' \notin f^n[A] \Big )$ Call one such instance $n'$.

So we have $x' \notin f^{n'}[A]$

However, we proved earlier through induction (Statement 2) that $\forall n \in \omega\big( f^n[B] \subseteq f^n[A]\big)$

Consider when $n=n'$: we then have $f^{n'}(B) \subseteq f^{n'}(A)$

By our earlier universal claim $\dagger\dagger$, we know that $x' \in f^{n'}[B]$

But $\Big[x' \in f^{n'}[B] \land f^{n'}[B] \subseteq f^{n'}[A] \Big ] \rightarrow x' \in f^{n'}[A]$.

A contradiction $\square$

1

There are 1 best solutions below

0
On BEST ANSWER

By straightforward induction, $$ f^{n+1}[A]\subseteq f^n[B]\subseteq f^n[A]$$ hence $$ \bigcap_{n<\omega}f^n[A]\subseteq\bigcap_{0\ne n<\omega}f^n[A]=\bigcap_{n<\omega}f^{n+1}[A] \subseteq \bigcap_{n<\omega}f^{n}[B]\subseteq\bigcap_{n<\omega}f^{n}[A].$$