Relation between subsets: Simmons

Question

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.

Answer 1

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$ 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?