Here is Prob. 3, Sec. 1, in the book Introduction To Topology And Modern Analysis by George F. Simmons.
(a) Let $U$ be the single-element set $\{ 1 \}$. There are two subsets, the empty set $\emptyset$ and $\{ 1 \}$ itself. If $A$ and $B$ are arbitrary subsets of $U$, there are four possible relations of the form $A \subseteq B$. Count the number of true relations among these.
(b) Let $U$ be the set $\{ 1, 2 \}$. There are four subsets. List them. If $A$ and $B$ are arbitrary subsets of $U$, there are $16$ possible relations of the form $A \subseteq B$. Count the number of true ones.
(c) Let $U$ be the set $\{ 1, 2, 3 \}$. There are $8$ subsets. What are they? There are $64$ possible relations of the form $A \subseteq B$. Count the number of true ones.
(d) Let $U$ be the set $\{ 1, 2, \ldots, n \}$ for an arbitrary positive integer $n$. How many subsets are there? How many possible relations of the form $A \subseteq B$ are there? Can you make an informed guess as to how many of these are true?
I know that there are a total of $2^n$ subsets of the set $U \colon= \{ 1, \ldots, n \}$ for any positive integer $n$. So, given any arbitrary subsets $A$ and $B$ of set $U$, there are $2^n \times 2^n = 2^{2n}$ relations of the form $A \subseteq B$, of which $3^n$ are true relations. This much we can conclude from the parts (a) through (c) above. Am I right?
Now my question is, how to prove rigorously (i.e. using induction or otherwise) that there are a total of $3^n$ true relations?
My Attempt:
Our desired assertion of course holds for $n = 1$. Suppose it holds for an arbitrary positive integer $n$. Now let us consider the set $U$ given by $$ U \colon= \{ 1, \ldots, n, n+1 \}. $$ Let us form the set $U^\prime$ as $$ U^\prime \colon= \{ 1, \ldots, n \}. $$ Then of course $$ U^\prime \subset U, $$ and also $$ U \setminus U^\prime = \{ n+1 \}. $$
Let $A$ and $B$ be arbitrary subsets of $U$. We want to count the total number of tru relations $A \subseteq B$.
The following four cases arise:
Case 1. Suppose both $A$ and $B$ are subsets of $U^\prime$. Then there are a total of $3^n$ true relations of the form $A \subseteq B$, by our inductive hypothesis.
Case 2. Suppose that $A \subseteq U^\prime$ and $B \not\subseteq U^\prime$. Then $n + 1 \in B$ but $n + 1 \not\in A$. Let us form the set $B^\prime$ as $$ B^\prime \colon= B \setminus \{ n+1 \}. $$ Then both $A$ and $B^\prime$ are subsets of $U^\prime$, and so by our inductive hypothesis there are a total of $3^n$ true relations of the form $A \subseteq B^\prime$, and since $B^\prime \subset B$, we can conclude that corresponding to each of the $3^n$ true relations of the form $A \subseteq B^\prime$, we have the true relation $A \subseteq B$. Thus there are at least a total of $3^n$ true relations of the form $A \subseteq B$.
On the other hand, as $n+1 \in B$ but $n+1 \not\in A$, so if $A \subseteq B$, then we also have $A \subseteq B^\prime$, and since there are a total of $3^n$ true relations of the form $A \subseteq B^\prime$, we can conclude that there are at most a total of $3^n$ true relations of the form $A \subseteq B$.
From the preceding two paragraphs we can conclude that there are exactly $3^n$ true relations of the form $A \subseteq B$.
Case 3. Suppose that $A \not\subseteq U^\prime$ and $B \subseteq U^\prime$. Then $n + 1 \in A$ but $n+1 \not\in B$. Thus $A \not\subseteq B$. There are a total of $0$ true relations of the form $A \subseteq B$.
Case 4. Suppose that $A \not\subseteq U^\prime$ and $B \not\subseteq U^\prime$. Then $n+1 \in A$ and $n+1 \in B$. Let us form the sets $A^\prime$ and $B^\prime$ as follows: $$ A^\prime \colon= A \setminus \{ n+1 \} \qquad \mbox{ and } \qquad B^\prime \colon= B \setminus \{ n+1 \}. $$ Then of course $$ A^\prime \subseteq U^\prime \qquad \mbox{ and } \qquad B^\prime \subseteq U^\prime. $$ So by our inductive hypothesis there are a total of $3^n$ true relations of the form $A^\prime \subseteq B^\prime$. But whenever $A^\prime \subseteq B^\prime$ holds, we also have $$ A^\prime \cup \{ n+1 \} \subseteq B^\prime \cup \{ n+1 \}, $$ that is, $$ A \subseteq B. $$ Thus there are at least $3^n$ true relations of the form $A \subseteq B$.
On the other hand, suppose that $A \subseteq B$. Let $x \in A^\prime$. Then $x \neq n+1$ and as $A^\prime \subset A$, so we also have $x \in A$, which from the supposition of $A \subseteq B$ implies that $x \in B$; thus $x \in B$ and $x \neq n+1$, which implies that $x \in B^\prime$. So it follows that $A^\prime \subseteq B^\prime$. Therefore whenever $A \subseteq B$ holds, we also have $A^\prime \subseteq B^\prime$. Thus there are at most $3^n$ true relations of the form $A \subseteq B$.
Combining the conclusions of the preceding two paragraphs we can conclude that there are exactly $3^n$ true relations of the form $A \subseteq B$.
Since the above four cases are mutually exclusive and collectively exhaust all the possibilities for subsets $A$ and $B$ of our set $U$, therefore we can conclude that there are a total of $$ 3^n + 3^n + 0 + 3^n = 3 \times 3^n = 3^{n+1} $$ true relations of the form $A \subseteq B$, where $A$ and $B$ are arbitrary subsets of the set $U$ given by $$ U = \{ 1, \ldots, n, n+1 \}. $$
Thus by the principle of mathematical induction our assertion holds for all positive integers $n$.
Is my proof correct in each and every detail of its logic and presentation? If so, is my presentation clear enough?
Or have I made any errors or mistakes?
It could be shortened and tightened up a bit, but it’s correct and understandable. Here’s a quick sketch of a shorter version of the induction step. Each of the $3^n$ true relations $A\subseteq B$ with $A,B\subseteq U'$ clearly generates $3$ distinct true relations between subsets of $U$: $A\subseteq B$, $A\subseteq B\cup\{n+1\}$, and $A\cup\{n+1\}\subseteq B\cup\{n+1\}$. This ensures that there are at least $3\cdot 3^n=3^{n+1}$ true relations between subsets of $U$. On the other hand, if $A,B\subseteq U$ with $A\subseteq B$, let $A'=A\cap U'$ and $B'= B\cap U'$. Clearly $A'\subseteq B'$ is one of the $3^n$ true relations for $U'$, and it’s not hard to check that $\langle A,B\rangle$ is one of the pairs $\langle A',B'\rangle$, $\langle A',B'\cup\{n+1\}\rangle$, and $\langle A'\cup\{n+1\},B'\cup\{n+1\}\rangle$ generated from $\langle A',B'\rangle$. Thus, every true relation for $U$ is one of the $3^{n+1}$ generated from true relations for $U'$, and there are therefore exactly $3^{n+1}$ true relations for $U$.
However, there is a simpler argument that doesn’t use induction. Let $n=|U|$. There is an obvious bijection between true relations $A\subseteq B$ between subsets of $U$ and partitions of $U$ into $3$ sets labelled $A$, $B\setminus A$, and $U\setminus B$. (In contrast to the usual notion of partition we allow any of these parts to be empty.) And there are $3^n$ ways to assign the $n$ members of $U$ to the three parts, so there are $3^n$ true relations $A\subseteq B$ between subsets of $U$.