We have $k\ge2$ sets, and none of them are equal. Show that at least one of the sets contains none of the other sets. 
So we have $k$ sets, $k\ge2$. We are given that none of the sets are equal. We are asked to give a rigorous proof of the fact that at least one of the sets contains none of the other sets. 

I'm extremely new to writing proofs, and I do see intuitively why this should be true (at least when I visualize it), but I don't even know how to start. A step by step answer would be highly appreciated.
 A: $\bullet \; $ First Proof. By contradiction, suppose it's false. For $1\leq x\leq k$ let $f(x)$ be the least $n$ such that $A_x\supsetneqq A_n.$ (We take the least $n$ just to have a precise def'n of $f.$)
Note that $x\ne f(x).$
For $1\leq j\leq  k$ let $f^0(j)=j$ and for $n\in \mathbb N$ let $f^n(j)=f(f^{n-1}(j)).$
Note that $A_{f^m(j)}\ne A_{f^{m+1}(j)}$ for any $m,j$ because, with $x=f^m(j),$ we have $f^{m+1}(j)=f(x)\ne x,$ and $A_x\ne A_{f(x)}.$ 
Note that (by induction on $m'$) if $m<m'$ then $A_{f^m(j)}\supset A_{f^{m'}(j)}.$
For any $j,$ the sequence $f^0(j), f^1(j), f^2(j),...$ must have some $m, m'$ with $m< m'$ and $f^m(j)=f^{m'}(j)$ because  each member of the sequence belongs to the finite set $\{1,...,k\}.$ For such $m, m'$ we have $m'\ne m+1$: Because if $m'=m+1$ then $f^m(j)=f^{m'}(j)=f^{m+1}(j)=f(f^m(j)),$ which implies $x=f(x)$ when $x=f^m(j),$ contrary to  $x\ne f(x).$
So we have $m'\geq m+2$ and $f^{m'}(j)=f^m(j)\ne f^{m+1}(j).$ This implies $$A_{f^m(j)}\supsetneqq A_{f^{m+1}(j)}\supset A_{f^{m'}(j)}= A_{f^m(j)}$$ which is absurd: Because $A\supset B\supset A \implies A=B,$ so we cannot have $A\supsetneqq  B\supset C\supset A.$
Remark: From the part defining $f^n(j)$ for $j\in \mathbb N\cup \{0\}$, to the end, we could just consider the case $j=1.$ Thus we could simplify the notation. We will still need to define $f(x)$ for $1\leq x\leq k.$
$\bullet \; $ Second Proof. By induction on $k\geq 2.$ Call the proposition $P(k).$ We wish to prove  $\forall k\geq 2\;(P(k)).$
For $k=2$ we cannot have $A_2\subsetneqq A_1$ and $A_1\subsetneqq A_2$ because $A\subset B\subset A\implies A=B.$ So we have $P(2).$
We show that $P(k)\implies P(k+1)$ for any $k\geq 2$: There exists $j$ with $1\leq j\leq k$ such that $A_{j'}\not \subset A_j$ when $j'\ne j$ and $1\leq j'\leq k.$ Now for such  $j,$ we have 
(i) If $A_{k+1}\subset A_j$ then $A_j\not\subset A_{k+1}$. And if $j'\ne j$ with $1\leq j'\leq k,$ then $A_{j'}\not\subset A_{k+1},$ otherwise  $A_{j'}\subset A_j.$ So $A_i\not\subset A_{k+1}$ for  $1\leq i \leq k.$
(ii) If $A_{k+1}\not\subset A_j$ then $A_i\not\subset A_j$ for  $i\leq k+1$ with $i\ne j.$
A: Let $(A_i)_{1\leq i\leq n}$ be the given family of sets,  put $\bigcup_{i=1}^nA_i=:X$, and denote by $\chi_i:\>X\to\{0,1\}$  the characteristic function of $A_i\subset X$. Call two elements $x$, $y\in X$ equivalent if $\chi_i(x)=\chi_i(y)$ for all $i\in[n]$. This equivalence relation partitions $X$ into $\leq 2^n$ nonempty blocks (the atoms of the $\sigma$-algebra generated by the $A_i$). The $\chi_i$ are constant on the blocks, hence each $A_i$ is  a union of such blocks. There is an $A_r$ consisting of a minimal number of blocks; therefore it cannot contain any $A_i$ as a proper subset.
