# Relation between subsets: Simmons

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.

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