Prob. 3 (d), Sec. 1, in G.F. Simmon's INTRO TO TOPOLOGY & MODERN ANALYSIS 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?
 A: 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$.
