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

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.

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

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.

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.

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.