Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$

Question

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$.

Prove by induction that one of these $n$sets is a subset of all of them.

I have no idea where to start, any help would be very useful.

Answer 1

start with the case $n=2$ (easy!), then $n=3$. If you have three sets $A_1,A_2,A_3$ satisfying the conditions, can you conclude that one must be contained in all three? Can you reduce the argument to the case $n=2$? if so, tackle the induction step.

For a more specific hint, for the inductive step, given $k+1$ sets, look at $A_1$ and $A_2$ and without loss of generality assume $A_2\subseteq A_1$. Now look at the sets $A_2,\cdots, A_{k+1}$ and apply the induction hypothesis.

Answer 2

This is obvious when $n=1$.

If it is true for $n$:

• if $A_{n+1}$ is a subset of every $A_k, k<n+1$. Then you are done.
• Otherwise, there is a $k<n+1$ such as $A_k\subset A_{n+1}$. Using the induction hypothesis, there is a $k'\le n$ such as: $$\forall k''\ge n\ \ \ A_{k'}\subset A_{k''} $$But also $$ A_{k'}\subset A_{k}\subset A_{n+1}. $$