I am trying to solve the below exercise in 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?
Here is my attempt at a solution.
(a) We have four possible relations:
\begin{align*}
& \emptyset \subset U & & \text{True; the empty set is a subset of every set} \\
& U \subset \emptyset & & \text{False; $1 \in U$} \\
& \emptyset \subset \emptyset & & \text{True; every set contains itself} \\
& U \subset U & & \text{True; every set contains itself}
\end{align*}
(b) There are four subsets:
$$\emptyset, \{1\}, \{2\}, \{1,2\}.$$
Every set is a subset of itself, giving $4$ true relations. The empty subset is a subset of the other three subsets, giving $3$ more true relations. (And three false relations since the empty set is not a superset of the other three subsets.) The two single sets are subsets of $\{1,2\}$, giving $2$ more true relations. Further, they are not supersets of $\{1,2\}$. The singleton sets are not subsets of each other, giving two more false relations. All $16$ relations have been accounted for, so we have
$$4 + 3 + 2 = 9$$
true relations.(c) The possible subsets of $U = \{1,2,3\}$ are
$$\emptyset, \{1\}, \{2,\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}.$$
The empty set is a subset of every set, so that gives $8$ true relations. Every set is a subset of itself, giving $8$ more true relations. There are $\binom{3}{2} = 3$ singleton sets, which are not contained in any of the three three-element sets, giving three more $3 \cdot 3 = 9$ false relations. There are three two-element sets, none of which are contained in $\{1,2,3\}$, giving three more false relations. The three singleton sets aren't contained in each other, so that gives two more false relations. The three two-element sets are not contained in each other, so that gives two more false relations.
At this point, I'm having trouble completing this. Though I could surely do this by brute-force, there surely must be a good way to generalize it to $n$ element sets that I cannot think of at this moment.
Any hints on how to generalize would be appreciated.
Best Answer
Your answers to (a) and (b) are correct, and you correctly listed the subsets of $\{1,2,3\}$, but your count of true relations among them of the form $A\subseteq B$ is incorrect: all of the subsets, including the two-element ones, are subsets of $\{1,2,3\}$. Correct brute force counting will yield a total of $27$ true relations.
The numbers $3,9=3^2$, and $27=3^3$ of true relations when $U=\{1\}$, $U=\{1,2\}$, and $U=\{1,2,3\}$, respectively, suggest that for $U=\{1,2,\ldots,n\}$ the number of true relations probably ought to be $3^n$. This is not too hard to prove. We want to count the pairs $\langle A,B\rangle$ of subsets of $U$ such that $A\subseteq B$. We can build such a pair by running through $U$ one number at a time and deciding whether to put it in $A$, in $B\setminus A$, or in $U\setminus B$. In how many ways can such a sequence of $n$ decisions be made?