7.1 Sets, Relations, Functions

Set theory provides a common language for modern mathematics. Many mathematical objects can be described as sets with additional structure, and many mathematical constructions can be described using membership, subsets, relations, and functions. In this section we introduce these basic notions carefully, since later parts of logic and foundations use them constantly.

Sets and Membership

A set is a collection of objects, called its elements or members. If an object $a$ is an element of a set $A$, we write:

If $a$ is not an element of $A$, we write:

The relation $\in$ is called membership. It is the most basic relation in set theory. The expression $a \in A$ is a statement, and it says that the object $a$ belongs to the set $A$.

For example, if:

then:

and:

A set is determined by its elements. This means that two sets are equal exactly when they have the same elements.

Definition 7.1 (Equality of Sets)

Two sets $A$ and $B$ are equal if and only if every object belongs to $A$ exactly when it belongs to $B$:

This principle is often called extensionality. It says that a set has no hidden structure beyond its elements. If two sets contain the same elements, then they are the same set.

Example 7.2

The sets:

and:

are equal, because they have exactly the same elements.

Also:

because repetition does not create new elements.

Thus order and repetition do not matter for sets.

Definition 7.3 (Subset)

Let $A$ and $B$ be sets. We write:

if:

In words, $A \subseteq B$ means that every element of $A$ is also an element of $B$.

If:

and:

then $A$ is called a proper subset of $B$.

Example 7.4

Let:

and:

Then:

because every element of $A$ is also an element of $B$.

But:

because:

and:

Lemma 7.5 (Set Equality by Double Inclusion)

For any sets $A$ and $B$:

if and only if:

Proof

Suppose first that $A = B$. Then every element of $A$ is an element of $B$, and every element of $B$ is an element of $A$, because the two sets are the same set. Hence:

and:

Conversely, suppose that:

Let $x$ be any object. If $x \in A$, then $x \in B$ because $A \subseteq B$. If $x \in B$, then $x \in A$ because $B \subseteq A$. Therefore:

for every object $x$. By extensionality:

Definition 7.6 (Empty Set)

The empty set is the set with no elements. It is denoted by:

A set $E$ is empty if:

The empty set is the unique set with this property.

Lemma 7.7 (Uniqueness of the Empty Set)

If $E$ and $F$ are empty sets, then:

Proof

Assume that $E$ and $F$ are empty sets. To show $E = F$, it is enough to show double inclusion.

First, let $x \in E$. Since $E$ is empty, this is impossible. Therefore the implication:

is true for every $x$, and hence:

The same argument shows:

By Lemma 7.5:

Lemma 7.8 (Empty Set Is a Subset of Every Set)

For every set $A$:

Proof

We must show:

Let $x$ be arbitrary. The statement $x \in \varnothing$ is false by definition of the empty set. Therefore:

is true. Since $x$ was arbitrary:

Definition 7.9 (Union)

The union of $A$ and $B$ is the set:

Thus:

The union contains everything that belongs to at least one of the two sets.

Definition 7.10 (Intersection)

The intersection of $A$ and $B$ is the set:

Thus:

The intersection contains exactly the elements common to both sets.

Definition 7.11 (Difference)

The difference of $A$ and $B$ is the set:

Thus:

The difference consists of the elements of $A$ that are not in $B$.

Example 7.12

Let:

and:

Then:

Lemma 7.13 (Commutativity of Union and Intersection)

For all sets $A$ and $B$:

and:

Proof

We prove the statement for union first. Let $x$ be arbitrary. Then:

if and only if:

which is equivalent to:

which is equivalent to:

Therefore:

The proof for intersection is similar. We have:

if and only if:

which is equivalent to:

which is equivalent to:

Therefore:

Lemma 7.14 (Associativity of Union and Intersection)

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

and:

Proof

We prove the statement for union. Let $x$ be arbitrary. Then:

if and only if:

if and only if:

if and only if:

if and only if:

if and only if:

By extensionality:

The proof for intersection is the same with “or” replaced by “and”. For every $x$:

if and only if:

if and only if:

if and only if:

Thus:

Lemma 7.15 (Distributive Laws)

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

and:

Proof

We prove the first identity. Let $x$ be arbitrary. Then:

if and only if:

if and only if:

if and only if:

if and only if:

if and only if:

Therefore:

The second identity is proved similarly. For every $x$:

if and only if:

if and only if:

if and only if:

Thus:

Definition 7.16 (Power Set)

The power set of $A$ is:

Thus:

Example 7.17

If:

then:

The power set contains sets as elements. The elements of $\mathcal{P}(A)$ are subsets of $A$, not usually elements of $A$.

Definition 7.18 (Ordered Pair)

An ordered pair is written:

and is characterized by the property:

This property is the essential feature of ordered pairs.

Definition 7.19 (Cartesian Product)

The Cartesian product of sets $A$ and $B$ is:

Thus an element of $A \times B$ is an ordered pair whose first coordinate belongs to $A$ and whose second coordinate belongs to $B$.

Example 7.20

If:

and:

then:

In general, $A \times B$ and $B \times A$ are different, because ordered pairs remember which coordinate comes first.

Definition 7.21 (Relation)

A relation from $A$ to $B$ is a subset:

If $A=B$, then a relation from $A$ to $A$ is called a relation on $A$.

If:

we often write:

A relation records which elements are related to which other elements.

Example 7.22

Let:

Define a relation $R$ on $A$ by:

Then:

The pair $(2,1)$ is not in $R$, because $2 < 1$ is false.

Properties of Relations

Let $R$ be a relation on a set $A$.

The relation $R$ is reflexive if:

It is symmetric if:

It is transitive if:

It is antisymmetric if:

These properties are used to define important classes of relations, especially equivalence relations and order relations.

Definition 7.23 (Equivalence Relation)

A relation $R$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.

Equivalence relations formalize the idea of treating objects as the same according to some chosen criterion.

Example 7.24

On the set of integers $\mathbb{Z}$, define:

This relation means that $a$ and $b$ have the same parity.

It is reflexive because:

is even.

It is symmetric because if $a-b$ is even, then:

is also even.

It is transitive because if $a-b$ is even and $b-c$ is even, then:

is even.

Therefore $R$ is an equivalence relation.

Definition 7.25 (Equivalence Class)

Let $R$ be an equivalence relation on $A$, and let $a \in A$. The equivalence class of $a$ is:

The equivalence class of $a$ consists of all elements equivalent to $a`.

Lemma 7.26 (Equivalence Classes Are Equal or Disjoint)

Let $R$ be an equivalence relation on $A$. For any $a,b \in A$, either:

or:

Proof

Suppose:

Then there exists an element $x$ such that:

Thus:

and:

Since $R$ is symmetric, from $xRa$ we get:

Since $aRx$ and $xRb$, transitivity gives:

We show that $[a]\subseteq [b]$. Let $y \in [a]$. Then:

Since $aRb$, transitivity gives:

Therefore:

So:

Similarly, since $aRb$, symmetry gives:

The same argument shows:

Hence:

Therefore, if two equivalence classes meet, they are equal. If they do not meet, they are disjoint.

Definition 7.27 (Partial Order)

A relation $\leq$ on a set $A$ is a partial order if it is reflexive, antisymmetric, and transitive.

That is, for all $a,b,c \in A$:

A set together with a partial order is called a partially ordered set, or poset.

Example 7.28

Let $A$ be any set. The subset relation:

is a partial order on $\mathcal{P}(A)$.

It is reflexive because:

for every $X \subseteq A$.

It is antisymmetric because:

imply:

It is transitive because:

imply:

Definition 7.29 (Linear Order)

A partial order $\leq$ on $A$ is a linear order if every two elements are comparable:

Linear orders are also called total orders.

Example 7.30

The usual order on the natural numbers:

is a linear order, because any two natural numbers can be compared.

The subset order on a power set is usually not a linear order. For example, if:

then:

and:

Thus $\{1\}$ and $\{2\}$ are not comparable under $\subseteq$.

Definition 7.31 (Function)

A function from $A$ to $B$ is a relation:

such that for every $a \in A$, there exists a unique $b \in B$ with:

We write:

and we write:

when:

The set $A$ is called the domain of $f$, and the set $B$ is called the codomain of $f$.

Example 7.32

Let:

and:

The relation:

is a function from $A$ to $B$, because every element of $A$ appears exactly once as a first coordinate.

The relation:

is not a function from $A$ to $B$, because $1$ has two outputs and $3$ has no output.

Definition 7.33 (Image and Preimage)

Let:

If $X \subseteq A$, the image of $X$ under $f$ is:

If $Y \subseteq B$, the preimage of $Y$ under $f$ is:

The image moves subsets of the domain forward into the codomain. The preimage moves subsets of the codomain backward into the domain.

Lemma 7.34 (Basic Image Properties)

Let $f:A\to B$, and let $X,Y\subseteq A$. Then:

Also:

Proof

First we prove:

Let $b \in f[X\cup Y]$. Then there exists $a \in X\cup Y$ such that:

Since $a \in X\cup Y$, either $a \in X$ or $a \in Y$. If $a \in X$, then $b \in f[X]$. If $a \in Y$, then $b \in f[Y]$. Hence:

Thus:

Conversely, let $b \in f[X]\cup f[Y]$. Then either $b \in f[X]$ or $b \in f[Y]$.

If $b \in f[X]$, then there exists $a \in X$ such that $f(a)=b$. Since $X\subseteq X\cup Y$, we have $a \in X\cup Y$, so $b \in f[X\cup Y]$.

If $b \in f[Y]$, the same argument shows $b \in f[X\cup Y]$.

Therefore:

By double inclusion:

Now we prove:

Let $b \in f[X\cap Y]$. Then there exists $a \in X\cap Y$ such that:

Since $a \in X\cap Y$, we have $a \in X$ and $a \in Y$. Therefore $b \in f[X]$ and $b \in f[Y]$. Hence:

So:

The reverse inclusion does not hold for arbitrary functions, because two different elements may have the same image.

Definition 7.35 (Injective, Surjective, Bijective)

Let:

The function $f$ is injective if distinct inputs have distinct outputs:

The function $f$ is surjective if every element of the codomain is hit by the function:

The function $f$ is bijective if it is both injective and surjective.

Injective functions are also called one to one functions. Surjective functions are also called onto functions.

Example 7.36

The function:

defined by:

is bijective.

It is injective because if:

then:

It is surjective because for every $k\in\mathbb{Z}$, the integer:

satisfies:

The function:

defined by:

is injective but not surjective if $0\in\mathbb{N}$, because no natural number maps to $0$.

Lemma 7.37 (Inverse of a Bijection)

Let:

be a bijection. Then there exists a unique function:

such that:

for all $a\in A$, and:

for all $b\in B$.

Proof

Since $f$ is surjective, for every $b\in B$ there exists at least one $a\in A$ such that:

Since $f$ is injective, this element $a$ is unique. Indeed, if:

and:

then:

and injectivity gives:

Therefore, for each $b\in B$, there is a unique $a\in A$ satisfying $f(a)=b$. Define:

where $a$ is this unique element.

This defines a function:

By construction, if $b=f(a)$, then the unique element mapping to $b$ is $a$, so:

Also, for any $b\in B$, the definition of $f^{-1}(b)$ gives:

Uniqueness follows because any function satisfying these two identities must send each $b\in B$ to the unique element of $A$ that maps to $b$ under $f$.

Definition 7.38 (Composition)

Let:

and:

The composition of $g$ with $f$ is the function:

defined by:

for all $a\in A$.

The function $f$ is applied first, and then $g$ is applied.

Lemma 7.39 (Associativity of Composition)

Let:

Then:

Proof

To prove equality of functions, it is enough to show that they have the same value at every input.

Let $a\in A$. Then:

By definition of composition:

On the other hand:

Again by definition of composition:

Thus:

for every $a\in A$. Therefore:

Definition 7.40 (Identity Function)

For a set $A$, the identity function on $A$ is:

defined by:

for all $a\in A$.

Lemma 7.41 (Identity Laws)

Let:

Then:

and:

Proof

Let $a\in A$. Then:

Thus:

Also:

Thus: