# 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$$ 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?
• @JiaoCtagon: $U=\{1,2,\ldots,n\}$. If $A\subseteq B\subseteq U$, $A$ and $B$ partition $U$ into three sets, $A$, $B\setminus A$, and $U\setminus B$: each $n\in U$ belongs to exactly one of these three sets. We can build a pair $\langle A,B\rangle$ by deciding for each $k\in U$ whether to put it in $A$, in $B\setminus A$, or in $U\setminus B$; that’s a $3$-way choice for each element of $U$. To distribute all of $U$ among the three sets $A,B\setminus A$, and $U\setminus B$ we must make a $3$-way choice for each of the $n$ elements of $U$. That’s a sequence of $n$ $3$-way choices. How many ... Commented Jun 9, 2023 at 5:22
• ... different ways are there to make such a sequence of choices? It’s exactly like calculating the number of possible different sequences of heads and tails when a coin is tossed $n$ times, except that each toss of the coin has only $2$ possible results, while in our problem here each element of $U$ can be given any of $3$ outcomes. Commented Jun 9, 2023 at 5:24
Lets consider $$B$$ has $$r$$ elements we can select $$B$$ in $$n C r$$ ways. For each $$B$$ we can find subsets of $$0,1,2,...,r$$ elements in $$r C_0, r C_1, r C_2, ..., r C_r$$ ways respectively. Therefore for $$B$$ with $$r$$ elements there are $$r C_0 + r C_1 + r C_2 + ... + r C_r = 2^r$$ subsets. Therefore in total, number of true relations equals $$n C_0 2^0 + n C_1 2^1 + ... + n C_n 2^n = 3^n$$.