2.1 Sets and set operations

Sets are the basic objects that let us talk about collections without constantly repeating the same description. In this course, sets are not a side topic. They are the language behind logic, functions, relations, and the later number constructions.

Sets, membership, and equality

Definition 2.1.1

(A set)

A set is a collection of things.

If $x$ is an element of a set $A$, we write $x ∈ A$. If $x$ is not an element of $A$, we write $x ∉ A$.

Examples:

• $\{1, 2, 3\}$ is a set.
• {Hong Kong Island, Kowloon, New Territories} is a set.
• $\varnothing$ is the empty set, the set with no elements.

The same object may be written in different ways, but a set is determined only by its elements.

Theorem 2.1.2

(Extensionality)

Two sets are equal if and only if they have exactly the same elements.

In symbols:

$$A = B \iff \forall x\, (x \in A \leftrightarrow x \in B).$$

This is the rule that makes set equality practical. To prove $A = B$, the standard method is to prove both inclusions:

1. show $A \subset B$;
2. show $B \subset A$.

Common mistake

(Do not confuse equal sets with equal descriptions)

$\{1, 2, 3\}$ and $\{3, 2, 1\}$ are the same set, because they have the same elements. The order of listing does not matter.

Common mistake

(Subset notation varies across books)

This course uses $A \subset B$ to mean “every element of $A$ is in $B$”. Some books write $A \subseteq B$ for that idea and reserve $A \subset B$ for strict subset. Always check the local convention.

Set-builder notation and bounded predicates

After predicate logic, the most common way to define a set is to start with a known set and then keep exactly the elements satisfying a condition:

$$\{x \in S \mid P(x)\}.$$

This notation should be read carefully. The symbol before the vertical bar tells you where the variable is allowed to live; the predicate after the bar tells you which of those allowed elements survive. For example,

$$\{n \in \mathbb{Z} \mid n \text{ is even}\}$$

is the set of even integers.

Common mistake

(Do not ignore the ambient set)

The expression $\{x \mid P(x)\}$ is often convenient shorthand, but the rigorous version is bounded inside a set already under discussion. This prevents the definition from pretending that every verbal description automatically creates a safe mathematical object.

Common mistake

(Sets are not multisets)

A set remembers whether an object is present, not how many times it was listed. Thus $\{1,1,2,3\}$ and $\{1,2,3\}$ describe the same set, even though they would be different multisets.

Building new sets

Once we know some sets, we usually want to build more. The standard operations do exactly that.

The complement depends on a universal set $E$. In this unit we usually assume all sets live inside some fixed $E$, so $A^c$ means $E \setminus A$.

Worked example 2.1.3

(Track elements through several set operations)

Let

$$A = \{1, 2, 4\}, \qquad B = \{2, 3, 4\},$$

and take the universal set

$$E = \{1, 2, 3, 4, 5\}.$$

Then:

• $A \cup B = \{1, 2, 3, 4\}$
• $A \cap B = \{2, 4\}$
• $A \setminus B = \{1\}$
• $B \setminus A = \{3\}$
• $A^c = \{3, 5\}$
• $(A \cup B)^c = \{5\}$

$A^c$ is not an intrinsic property of $A$ alone. It depends on what counts as “everything” in the current discussion. That is why the universal set has to be understood first.

Why the identities are true

For a fixed element $x$, membership in a union is a disjunction and membership in an intersection is a conjunction. The identities of propositional logic therefore become set identities when they hold for every $x$.

Theorem 2.1.4

(Basic algebra of sets)

For sets $A$, $B$, and $C$:

• $A \cup \varnothing = A$
• $A \cup B = B \cup A$
• $A \cup (B \cup C) = (A \cup B) \cup C$
• $A \cup A = A$
• $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
• $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
• $(A \cup B)^c = A^c \cap B^c$
• $(A \cap B)^c = A^c \cup B^c$
• $(A^c)^c = A$
• $A \cap A^c = \varnothing$
• $A \cup A^c = E$
• $A \subset B$ if and only if $A \cup B = B$
• $A \subset B$ if and only if $A \cap B = A$
• $A \subset B$ if and only if $B^c \subset A^c$

Take an arbitrary element $x$ and translate membership into logical conditions. To prove an inclusion, start with $x$ in the left-hand set and derive membership in the right-hand set. To prove equality, establish both directions. For example:

$$x \in A \cap (B \cup C) \iff x \in A \text{ and } (x \in B \text{ or } x \in C)$$

which is equivalent to

$$(x \in A \text{ and } x \in B) \text{ or } (x \in A \text{ and } x \in C),$$

and therefore to

$$x \in (A \cap B) \cup (A \cap C).$$

Proof: why $A \subset B$ implies $A \cup B = B$

Assume $A \subset B$.

To show $A \cup B = B$, it is enough to show both inclusions.

First, if $x \in A \cup B$, then $x \in A$ or $x \in B$. If $x \in A$, then $x \in B$ because $A \subset B$. So in either case $x \in B$, which gives $A \cup B \subset B$.

Conversely, if $x \in B$, then automatically $x \in A \cup B$. So $B \subset A \cup B$.

Hence $A \cup B = B$.

Proof: a conditional distributive identity

The statement

$$(A \cap B) \cup C = A \cap (B \cup C)$$

holds if and only if $C \subset A$.

For sufficiency, assume $C \subset A$. If $x$ belongs to the left side, then either $x \in A \cap B$, or $x \in C$. In the second case the inclusion $C \subset A$ gives $x \in A$, so in either case $x \in A$ and $x \in B \cup C$. Thus the left side is contained in the right side. Conversely, if $x \in A \cap (B \cup C)$, then $x \in A$ and either $x \in B$ or $x \in C$. In the first case $x \in A \cap B$; in the second case $x \in C$. Hence $x$ is in the left side, proving equality.

For necessity, assume the displayed equality and take any $c \in C$. Then $c \in (A \cap B) \cup C$, so equality puts $c$ in $A \cap (B \cup C)$. In particular $c \in A$. Therefore every element of $C$ belongs to $A$, which is exactly $C \subset A$. Equivalently, if one had $c \in C \setminus A$, that element would belong to the left side but not the right side, giving a counterexample to the equality.

Proof: symmetric difference is associative

The symmetric difference is

$$A \mathbin{\triangle} B=(A\setminus B)\cup(B\setminus A).$$

For every element $x$,

$$x\in A\mathbin{\triangle}B \iff (x\in A\text{ and }x\notin B)\text{ or }(x\notin A\text{ and }x\in B).$$

Thus membership means that exactly one of $A$ and $B$ contains $x$. Applying the same rule once more, $x$ belongs to $(A\mathbin{\triangle}B)\mathbin{\triangle}C$ exactly when an odd number of the three statements $x\in A$, $x\in B$, and $x\in C$ is true: the first symmetric difference records whether the first two statements have odd parity, and the second toggles that parity when $x\in C$. The expression $A\mathbin{\triangle}(B\mathbin{\triangle}C)$ has the same odd-parity condition, with the grouping reversed. Therefore

$$(A\mathbin{\triangle}B)\mathbin{\triangle}C =A\mathbin{\triangle}(B\mathbin{\triangle}C).$$

This is a membership proof, so it does not depend on a particular Venn diagram.

Proof: complement reverses inclusion

Let $A,B\subseteq E$ and assume $A\subseteq B$. For $x\in E\setminus B$, if $x\in A$ then the inclusion would imply $x\in B$, a contradiction. Thus $x\in E\setminus A$ and $B^c\subseteq A^c$. The common universe $E$ ensures that both complements compare elements of the same ambient set.

Counterexample mode

Union cannot be cancelled

The implication $A\subseteq B\Rightarrow A\cup C\subseteq B\cup C$ holds, but its converse fails. Take $A=\{1\}$, $B=\varnothing$, $C=\{1\}$. Then both unions equal $\{1\}$ while $A\nsubseteq B$. Adding $C$ conceals the witness 1. One valid repair is to assume also $A\cap C=\varnothing$: every $x\in A$ then belongs to $B\cup C$ but not to $C$, so it belongs to $B$.

Other set constructions

Set operations select or combine elements already present. Other constructions let us treat ordered pairs, tuples, and subsets as objects in their own right. These are the objects on which functions and relations will be defined.

Cartesian products

$A \times B$ is the set of ordered pairs $(a, b)$ with $a \in A$ and $b \in B$. Order matters: $(a, b)$ and $(b, a)$ are different unless $a = b$.

If $|A| = 5$ and $|B| = 3$, then $|A \times B| = 15$.

$R \times R = R^2$ is the Cartesian plane.

Finite products

The $n$-fold product $A^n$ is the set of all $n$-tuples with entries in $A$. This is just the repeated Cartesian product of $A$ with itself.

Power sets

$P(A)$ is the set of all subsets of $A$.

If $A$ has $n$ elements, then $P(A)$ has $2^n$ elements. A useful way to think about this is the indicator-function viewpoint: every subset of $A$ can be encoded by a function $A → \{0, 1\}$.

For example,

$$P(\{a, b\}) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}.$$

Disjoint union

Sometimes two sets may overlap as raw collections, but we still want to keep track of where each element came from. The disjoint union does that by tagging the elements with their origin.

A concrete realization is

$$A \sqcup B=(A\times\{1\})\cup(B\times\{2\}).$$

If an element belongs to both $A$ and $B$, its two tagged copies are still distinct.

Counterexample: product distributivity can fail

There need not be a bijection between

$$A \cup (B \times C) \quad\text{and}\quad (A \cup B) \times (A \cup C).$$

Take $A = \{0,1\}$ and $B=C=\varnothing$. The left set is $A$, so it has two elements. The right set is $A \times A$, so it has four ordered pairs. Their cardinalities differ, and therefore no bijection exists in this example.

How to prove a set identity carefully

At this stage of the course, a set identity should be read as a statement about membership, not as a picture to be memorized.

The standard proof pattern is:

1. take an arbitrary element $x$;
2. rewrite $x \in$ each side into logical conditions;
3. simplify those conditions until both sides say the same thing.

Worked example 2.1.5

(Prove $A \cap (B \setminus C) = (A \cap B) \setminus C$)

Start with

$$x \in A \cap (B \setminus C).$$

This means:

• $x \in A$,
• $x \in B$,
• $x \notin C$.

But that is exactly the condition for

$$x \in (A \cap B) \setminus C.$$

Since the reasoning can be read in either direction, the two sets are equal.

This is the same idea used for De Morgan’s laws, distributive laws, and later proofs about relations and number constructions.

Reading Venn diagrams correctly

Venn diagrams are useful for organizing a situation, but the proof still comes from membership conditions. A diagram can suggest that a region is empty, inside another region, or split into several pieces; the written argument must then say which inclusion, disjointness condition, or counting equation that picture represents.

For three sets, a statement such as $A \subset (B \cup C)$ means every element of $A$ lies in at least one of $B$ or $C$. It does not say that $A \subset B$, and it does not say that $A \subset C$. Keeping those possibilities separate is a good test of whether the diagram is being read logically rather than visually only.

Worked example 2.1.6

(Translate four Venn conditions into regions)

Assume $A$, $B$, and $C$ are non-empty sets. The following common practice conditions are best read as region instructions, not as vague pictures.

Condition	What the diagram must show
$A \subset B$, $C \subset B$, and $A \cap C = \varnothing$	Both $A$ and $C$ sit inside $B$, but they do not overlap each other. The set $B$ may still have points outside both of them.
$A \cap B \ne \varnothing$, $A \cap C \ne \varnothing$, $B \cap C \ne \varnothing$, and $A \cap B \cap C = \varnothing$	Each pair overlaps, but the central triple-overlap region is empty. The three pairwise overlaps must be separate regions.
$A \subset (B \cap C)$ and $B \subset C$	Since $B \subset C$, the intersection $B \cap C$ is just $B$. Thus $A$ lies inside $B$, and $B$ lies inside $C$.
$A \subset (B \cup C)$, not $A \subset B$, and not $A \subset C$	No point of $A$ is outside $B \cup C$, but $A$ must have at least one point in $C \setminus B$ and at least one point in $B \setminus C$.

The fourth line is the easiest one to misread. It does not merely say that $A$ touches both circles. It says that $A$ is completely covered by $B$ and $C$, while still failing to be contained in either one alone.

Counting finite sets

The language of sets also controls counting.

For finite sets:

• $|A \times B| = |A|\,|B|$,
• $|P(A)| = 2^{|A|}$,
• $|A \cup B| = |A| + |B| - |A \cap B|$.

The last formula matters because elements in the intersection are counted twice if you simply add $|A|$ and $|B|$.

Worked example 2.1.7

(Count a union and a power set)

Suppose $|A| = 6$, $|B| = 5$, and $|A \cap B| = 2$.

Then

$$|A \cup B| = 6 + 5 - 2 = 9.$$

Now let $S = \{a,b,c\}$. Each element either belongs to a subset or does not, so there are

$$2 \cdot 2 \cdot 2 = 2^3 = 8$$

possible subsets. Hence $|P(S)| = 8$.

Worked example 2.1.8

(A Venn-diagram count without drawing the diagram)

Ten students go hiking. Seven use sunscreen, six wear a hat, and two use no sun protection.

Let $S$ be the sunscreen set and $H$ the hat set. Since two students use neither form of protection,

$$|S \cup H| = 10 - 2 = 8.$$

By inclusion-exclusion,

$$|S \cap H| = |S| + |H| - |S \cup H| = 7 + 6 - 8 = 5.$$

So five students use both sunscreen and a hat.

Common mistakes

Common mistake

(A complement is a difference relative to the universe)

For $A\subseteq E$, the complement $A^c=E\setminus A$ consists of the elements inside the chosen universe $E$ but outside $A$. In contrast, $A\setminus B$ consists of the elements inside $A$ but outside $B$. A complement is therefore a set difference whose left operand is the universe, not the part outside the universe.

Common mistake

(The universal set cannot be ignored)

If you write a complement, you must know what universe you are working in. Otherwise the symbol $^c$ is ambiguous.

Common mistake

(Order matters in products)

$A \times B$ and $B \times A$ usually contain different ordered pairs. This is why products are the correct language for functions and relations.

Quick checks

Quick check

(Why is $A^c$ not defined until a universal set is chosen?)

Ask what the complement is supposed to be taken inside.

Solution · Answer

Because the same set has different complements in different universes.

Quick check

(If $A \subset B$, what do $A \cup B$ and $A \cap B$ simplify to?)

Use the subset characterizations from the theorem above.

Solution · Answer

$A \cup B = B$ and $A \cap B = A$.

Quick check

(Suppose $A \subset (B \cup C)$, but $A$ is not a subset of $B$ and not a subset of $C$. Which two parts of $A$ must be non-empty?)

Turn each failed subset statement into an existential statement.

Solution · Answer

There must be at least one element of $A$ in $C \setminus B$, and at least one element of $A$ in $B \setminus C$. The condition $A \subset (B \cup C)$ rules out any element of $A$ outside both $B$ and $C$.

From pairs to number systems

A Cartesian product supplies pairs; a relation specifies which pairs are connected. Functions and relations shows how an equivalence relation partitions a set into classes. The integer construction then applies this to pairs of natural numbers, and the rational construction uses classes to identify different representations of the same number. At each stage, the proof of set equality returns to the same question: which elements belong to each side?