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.

If the notation here feels unfamiliar, that is normal. The point of this unit is to make the language precise enough that later chapters can use it freely.

Sets, membership, and equality

Definition

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

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

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

The set laws in this unit are not memorized by magic. They are proved by tracking one element at a time.

Theorem

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$

The key proof method is element chasing. 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 the forward direction, 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 the reverse direction, 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

The course also uses a few larger constructions that are still built from the same language.

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.

Informally, $A \sqcup B$ is “$A$ with tag 1” together with “$B$ with tag 2”.

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

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

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

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

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.

A checklist for subset proofs

Subset proofs are common enough that they should become routine.

To prove $A \subseteq B$, start with an arbitrary element $x$ in $A$. Then use the definition of $A$ to deduce enough information to show that the same $x$ lies in $B$. Because $x$ was arbitrary, the conclusion applies to every element of $A$.

This direct-proof pattern is exactly what later chapters reuse for relations, orders, and equivalence classes.

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

Checkpoint

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.

Checkpoint

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

Use the absorption laws from the theorem above.

Solution · Answer

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

Checkpoint

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

Why this matters later

This unit is the first place where the course starts building the later number systems in a disciplined way.

• $N^2$ is used to construct the integers.
• Equivalence classes are later used to construct the rationals.
• Relations on one set become the language for orders and classes.
• Power sets and products reappear whenever we talk about families of subsets or tuples.