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

Examples:

• {1, 2, 3} is a set.
• {Hong Kong Island, Kowloon, New Territories} is a set.
• $∅$ 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.

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

Building new sets

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

| Operation | Symbol | Definition | | --- | --- | --- | | Union | $A \cup B$ | elements in $A$ or in $B$ | | Intersection | $A \cap B$ | elements in both $A$ and $B$ | | Difference | $A \setminus B$ | elements in $A$ but not in $B$ | | Complement | $A^c$ | elements outside $A$ in a chosen universal set |

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

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.

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

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

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.

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

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

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

Quick checks

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.