1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Simmons: I don't get the last paragraph at all. what does the last question even mean? $\endgroup$ Commented Jun 9, 2023 at 4:13
  • $\begingroup$ @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 ... $\endgroup$ Commented Jun 9, 2023 at 5:22
  • $\begingroup$ ... 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. $\endgroup$ Commented Jun 9, 2023 at 5:24
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .