# Cardinality of a set $\{A,B\}$ $A$ is a subset of $B$, which is a subset of $S$

Let's say that $A$ is a subset of $B$ and be is a subset of a set $S$ of $n$ elements.

How big is the set $\{(A,B)\}$ then.

-
Do you want to know the cardinality of $\{(A,B)\}$, or of $\{A,B\}$? These are not the same thing. –  Chris Eagle Feb 17 '13 at 0:52
the former option –  user60862 Feb 17 '13 at 3:54

Assuming $A \neq B$, then there are exactly two elements in $\{A, B\}$, elements which happen to be sets $A, B$. Hence, the cardinality of $\{A,\,B\}$ is $2$. I.e., $|\{A, \,B\}| =2.$ Else, we can only say $|\{A, \,B\}| \leq 2$.

The set $\{(A, B)\}$ has one element, (cardinality 1), which happens to be an ordered pair of sets.

The information about the relation between sets $A, B,$ and between $B, S$ and the elements of $S$ is irrelevant: that information is what they call a "red herring."

-
Unless, of course, $A=B$. –  Chris Eagle Feb 17 '13 at 0:52
Ahha, you're correct, @Chris –  amWhy Feb 17 '13 at 0:54

The set $\{A,B\}$ has at most two elements, and if $A\neq B$ then it has exactly two.

The set $\{(A,B)\}$ has exactly one element, the ordered pair $(A,B)$.

-

Perhaps you are asking to find $|N|$ where $N = \{(A, B) \mid A \subseteq B \subseteq S, |S| = n\}$ for some integer $n$.

To solve this, let's first fix some $B_0$ and let $m = |B_0|$. Then the number of subsets of $B$ is just $2^m$. Clearly, $0 \leq m \leq n$. So $|N| = \sum_{i=0}^{n}{2^i}=2^{n+1}-1$

-
I appreciate your answer, but to indicate that the OP's question could be read in a different way is slightly misleading. The notation is clear and unambiguous, and for the set(s) that the OP asked about, several people have answered the question. What you are doing is answering the question for the set (you think) the OP meant to ask about. –  Michael Albanese Feb 17 '13 at 1:20
@MichaelAlbanese Yes, I see that my original wording is misleading. I will edit it for clarification. –  Code-Guru Feb 17 '13 at 1:25

It depends on whether you mean the set in the title of your question, or the set in the question itself.

As $A \subseteq B \subseteq S$, $A$ and $B$ are elements of $\mathcal{P}(S)$, the power set of $S$. So $\{A, B\} \subseteq \mathcal{P}(S)$. This set has cardinality two, unless (as Chris Eagle pointed out in a comment on another answer) $A = B$, in which case $\{A, B\} = \{A\}$ which has cardinality one.

The notation $(\cdot, \cdot)$ is used to denote an ordered pair, which is an element of the cartesian product of two sets. Again, $A, B \in \mathcal{P}(S)$, so $(A, B) \in \mathcal{P}(S)\times\mathcal{P}(S)$, hence $\{(A, B)\} \subseteq \mathcal{P}(S)\times\mathcal{P}(S)$. In particular, $\{(A, B)\} \neq \{A, B\}$. The former set has cardinality one, regardless of whether or not $A = B$.

-
What if $A$ and $B$ range over all possible sets which satisfy the given conditions? –  Code-Guru Feb 17 '13 at 1:01
Do you mean $\{\{A, B\}\ |\ A \subseteq B \subseteq S\}$ or $\{\{(A, B)\}\ |\ A \subseteq B \subseteq S\}$? –  Michael Albanese Feb 17 '13 at 1:05
It might be interesting to do both. I already posted an answer for the later. –  Code-Guru Feb 17 '13 at 1:10