1.2 Sets, Subsets, and Power Sets

The previous section wrote an elevator’s allowed floors as $\{1,2,3,4,5,6\}$ but treated the braces as a simple state list. We now study that structure formally. The purpose is not to accumulate symbols; it is to answer precise questions: Does an object occur in the list? Are two lists identical? Is one list contained entirely in another?

The section proceeds in three stages:

• Read and write a set, then decide whether an object belongs to it.

• Compare sets using equality, cardinality, and the subset relation.

• Collect every possible subset into a new object called a power set.

A set organizes distinct objects into one collection. The objects inside it are elements. If $x$ belongs to set $A$, write $x\in A$; if it does not, write $x\notin A$.

Translate the notation directly when reading it:

• $3\in\{1,2,3\}$ says “3 belongs to the set $\{1,2,3\}$.”

• $5\notin\{1,2,3\}$ says “5 does not belong to the set $\{1,2,3\}$.”

• $A=\{1,2,3\}$ gives this set the name $A$.

Elements do not need to be numbers. $C=\{\text{red},\text{blue},\text{yellow}\}$ is a set of colors; $M=\{\text{stopped},\text{running}\}$ is a set of machine modes; an element may even be another set.

A set cares about membership, not writing order or repetition. Therefore,

The last notation is redundant but does not create extra elements. All three sets have exactly the same members and are equal.

The number of elements in a set is its cardinality, written $|A|$. If $A=\{1,2,3\}$, then $|A|=3$. Repetition does not increase cardinality, so $|\{1,1,2,3\}|$ is still 3.

Use a reliable two-direction test for equality of finite sets:

• Check that every element on the left occurs on the right.

• Check that every element on the right occurs on the left.

The sets are equal only when both checks pass. Equal cardinality alone is insufficient: $\{1,2\}$ and $\{3,4\}$ have the same size but different members.

Two common ways to write sets

So far we have used roster notation, listing elements directly inside braces. When a collection is larger, a condition may be clearer. For example,

The vertical bar $\mid$ reads “such that.” The entire expression says: “$E$ is the set of all $x$ such that $x$ is even and lies from 1 through 8.” Checking the values gives $E=\{2,4,6,8\}$. This is called set-builder notation.

Elements, sets, and subsets

Do not confuse an element belonging to a set with one set being contained in another. If

then $a\in S$, while $\{a\}\subseteq S$. The object $a$ is an element; $\{a\}$ is a set containing one element. They are not the same object.

Treat the two symbols as answers to different kinds of questions:

When $S=\{a,b,c\}$, both $a\in S$ and $\{a\}\subseteq S$ are true, but $\{a\}\in S$ is false. The three elements of $S$ are $a,b,c$; the set $\{a\}$ is not one of them.

Set $A$ is a subset of $B$ when every element of $A$ also belongs to $B$. Write

To refute this claim, one witness is sufficient: an $x\in A$ with $x\notin B$. If $A\subseteq B$ and $A\ne B$, then $A$ is a proper subset of $B$, written $A\subset B$.

For finite sets, apply the definition mechanically:

• Take the first element from the left set.

• Search for it on the right. If it is absent, stop; this element is a counterexample.

• If it is present, continue with the next left-side element.

• If every left-side element passes, the subset claim is true.

For example, let $A=\{1,3\}$ and $B=\{1,2,3,4\}$. We find 1 in $B$, then find 3, so $A\subseteq B$. In the reverse test $B\subseteq A$, element 2 is missing from $A$, so 2 witnesses that the claim is false.

Every set is a subset of itself: each of its elements obviously belongs to it. Thus $A\subseteq A$ is always true, but $A\subset A$ is false because a proper subset must also be unequal to the larger set.

The forge turns the definition into a constraint system. Instead of merely reporting “wrong,” it searches for a witness that breaks $A\subseteq B$. This pattern will return throughout the course: proving a universal claim requires covering every case, while refuting it often needs only one counterexample.

Try the forge’s incomparable target. If $A$ contains something missing from $B$ and $B$ also contains something missing from $A$, both subset directions fail. Sets do not always nest neatly as one smaller collection inside another.

The empty set and power sets

The empty set contains no elements and is written $\emptyset$ or $\{\}$. It is a subset of every set. This is not because the empty set is physically hidden inside every collection. It is because no element of the empty set can violate the subset condition.

Apply the checking procedure: when testing $\emptyset\subseteq A$, there is no first left-side element and therefore no possible failure witness. The procedure finishes immediately, so the claim is true. Logic will later give this type of reasoning a formal explanation.

The power set of $S$ is the set containing every subset of $S$:

The elements of a power set are themselves sets. If $S=\{a,b\}$, then

Every original element has two independent choices: include it in a subset or leave it out. If $|S|=n$, then

Do not memorize the formula before constructing a small case. For $S=\{a,b\}$:

• Choose neither element to obtain $\emptyset$.

• Choose only $a$ to obtain $\{a\}$.

• Choose only $b$ to obtain $\{b\}$.

• Choose both to obtain $\{a,b\}$.

Represent include by 1 and exclude by 0:

Two positions with two choices each create $2\cdot2=4=2^2$ results. With $n$ elements there are $n$ binary positions, which explains the count $2^n$.

The constellation layers subsets by cardinality. Layer $k$ contains every subset of size $k$, for a total of $\binom{n}{k}$. Combining every layer must cover the entire power set:

For now, read the left side as grouping subsets by size and the right side as counting independent switches. Chapter 6 will develop these counting methods systematically.

The symbol $\binom{n}{k}$ is only a preview here. It means “the number of ways to choose exactly $k$ objects from $n$ distinct objects.” You do not yet need its general formula. In the lab, simply observe that subsets with equal cardinality occupy the same layer. Chapter 6 will derive the calculation from the beginning.

Bridge to the next section

We can now create sets, test membership, compare subsets, and enumerate every subset. Real questions often combine two lists: students attending course A or course B, or actions available to each user. The next section builds union, intersection, difference, and Cartesian products directly from the membership ideas $\in$ and $\subseteq$ learned here.