02 Sets and Set Operations

Sets, Elements, and Notation

A Set is a well-defined collection of objects called elements or members. Sets are usually named with capital letters and written with braces. For example, $A=\{1,2,3,4\}$.

The notation $x\in A$ means that $x$ is an element of $A$, and $x\notin A$ means that it is not. Sets ignore order and repetition:

The element relationship is different from the subset relationship discussed later. An object such as $a$ may satisfy $a\in A$, while the one-element set $\{a\}$ may satisfy $\{a\}\subseteq A$.

Two common descriptions

• Roster notation lists the elements explicitly, such as $E=\{2,4,6,8\}$.

• Set-builder notation specifies a property, such as $E=\{x\in\mathbb{Z}\mid x\text{ is even and }0<x<10\}$.

The symbol $\mid$ means “such that.” The empty set $\varnothing$ has no elements. A set is completely determined by its elements, a principle called extensionality.

Takeaway: Read a set by asking which objects belong to it; order and repeated listings do not change the set.

Subsets and Set Equality

A subset $A\subseteq B$ is a set for which every element of $A$ is also an element of $B$:

For example, if $A=\{1,3\}$ and $B=\{1,2,3,4\}$, then $A\subseteq B$. Every set has the two basic inclusions $\varnothing\subseteq A$ and $A\subseteq A$.

A proper subset $A\subsetneq B$ is a subset that is not equal to $B$:

Two sets are equal precisely when they include each other:

This is the double-inclusion method. For example, let

and

An integer is divisible by $6$ exactly when it is divisible by both $2$ and $3$, so every element of $A$ is in $B$, and every element of $B$ is in $A$. Therefore, $A=B$.

Takeaway: To prove equality of sets, prove both inclusions rather than relying on the way the sets are written.

Union, Intersection, Difference, and Complement

Assume that all sets under discussion are contained in a fixed universal set $U$. The main operations are defined by membership conditions.

• The union $A\cup B$ contains elements in at least one set:

  $$A\cup B=\{x\mid x\in A\text{ or }x\in B\}.$$

• The intersection $A\cap B$ contains elements common to both:

  $$A\cap B=\{x\mid x\in A\text{ and }x\in B\}.$$

• The difference $A\setminus B$ contains elements in $A$ that are not in $B$:

  $$A\setminus B=\{x\mid x\in A\text{ and }x\notin B\}.$$

• The complement $A^c$ contains elements of $U$ that are not in $A$:

  $$A^c=\{x\in U\mid x\notin A\}.$$

For $A=\{1,2,3\}$ and $B=\{3,4,5\}$, these operations give

The sets are disjoint when $A\cap B=\varnothing$. Difference is not generally commutative, so the order in $A\setminus B$ matters. If $U=\{1,2,3,4,5\}$ and $A=\{1,3\}$, then $A^c=\{2,4,5\}$.

Takeaway: Translate “or,” “and,” and “not” into union, intersection, and complement, while remembering that a complement requires a specified universal set.

Cartesian Products and Ordered Pairs

The Cartesian product $A\times B$ consists of all ordered pairs whose first coordinate comes from $A$ and whose second coordinate comes from $B$:

If $A=\{1,2\}$ and $B=\{x,y,z\}$, then

Order matters in an ordered pair, so $(a,b)$ is generally different from $(b,a)$, and $A\times B$ is generally different from $B\times A$. For finite sets with $|A|=m$ and $|B|=n$, the number of ordered pairs is

The product of a set with itself is written $A^2=A\times A$. More generally,

In particular, $\mathbb{R}^2=\mathbb{R}\times\mathbb{R}$ is the set of ordered pairs of real numbers and represents the coordinate plane.

Takeaway: A Cartesian product records position: the first set supplies the first component, and the second set supplies the second component.

Power Sets and Subset Counting

The power set $\mathcal{P}(A)$ is the set of every subset of $A$:

For $A=\{a,b\}$,

It is important to distinguish an element from a one-element subset. The statements $a\in A$ and $\{a\}\subseteq A$ can both be true, but $a$ and $\{a\}$ are different objects.

If $A$ is finite and $|A|=n$, then

Each element has two choices when forming a subset: include it or omit it. Thus, a three-element set has $2^3=8$ subsets. The empty set provides an important example:

The power set is therefore not empty, even though its only element is the empty set.

Takeaway: To count subsets of a finite set, give each element an include-or-omit choice, producing $2^n$ possibilities.

Indexed Families of Sets

An indexed family labels many sets using an index set $I$, written $\{A_i\}_{i\in I}$. If $I=\{1,2,3\}$, the family represents $A_1$, $A_2$, and $A_3$.

The indexed union contains an element if it belongs to at least one member of the family:

The indexed intersection contains an element only if it belongs to every member:

For

we obtain

The same notation extends to infinite families such as $\{A_n\}_{n\in\mathbb{N}}$. The union uses an “at least one” condition, whereas the intersection uses an “every” condition.

Takeaway: Indexed notation extends ordinary union and intersection to any labeled collection of sets, including infinite collections.

Fundamental Set Identities

Set identities can be checked by translating membership into logic. Important laws include commutativity,

associativity,

and distributivity,

Other useful laws are

De Morgan’s laws describe complements of compound sets:

Difference can also be rewritten using complements:

This form often makes additional identities easier to recognize, such as

Takeaway: Set identities behave like logical equivalences; rewrite membership conditions carefully and apply the matching law.

Proving Identities by Element Chasing

To prove an identity, use element chasing: choose an arbitrary element $x$, translate each membership statement into logic, simplify, and translate back. Consider

Begin with an arbitrary $x$ in the left-hand side:

The first equivalence uses the definition of intersection and union. The second uses the distributive law of logic. The final equivalence translates the logical statement back into set notation.

Because $x$ was arbitrary, the two sets have exactly the same elements, so the identity holds. The same strategy can prove equality by showing both inclusions: prove that an arbitrary element of the first set belongs to the second, then reverse the roles.

Takeaway: Set proofs become systematic when every step states an equivalent condition for membership.