Naive Set Theory

Definition 39: Set and Set Membership

A set is a mathematical object completely defined by its elements or members. If an object $𝑥$ is an element of a set $𝐴$ , then we say that $𝑥$ is an element of $𝐴$ and denote that $𝑥 \in 𝐴$ .

Notation: Set Roster Notation

A set can be defined by explicitly listing its elements, separated by commas and enclosed in curly braces. For example, the set of natural numbers less than 5 can be defined as $𝐴 = {0, 1, 2, 3, 4}$ .

Since a set is defined by the objects that belong to it, the following principles hold:

The order in which we denote elements of a set does not matter.
Repeated elements in a set do not affect the set’s identity.

Example.

Define the sets

𝐴 = {1, 2, 3}

𝐵 = {3, 2, 1}

, and

𝐶 = {1, 2, 2, 3}

. Then

𝐴

𝐵

, and

𝐶

are all the same set.

Definition 40: Subset and Proper Subset

A set $𝐴$ is a subset of a set $𝐵$ , denoted $𝐴 \subseteq 𝐵$ , iff $𝑥 \in 𝐴$ implies $𝑥 \in 𝐵$ . Furthermore, $𝐴$ is a proper subset of $𝐵$ , denoted $𝐴 \subset 𝐵$ or $𝐴 ⊊ 𝐵$ , iff $𝐴 \subseteq 𝐵$ and there exists some element in $𝐵$ that is not in $𝐴$ . Formally:

\begin{matrix} 𝐴 \subseteq 𝐵 & iff \forall 𝑥 (𝑥 \in 𝐴 \Rightarrow 𝑥 \in 𝐵) \\ 𝐴 \subset 𝐵 & iff 𝐴 \subseteq 𝐵 and \exists 𝑥 (𝑥 \in 𝐵 and 𝑥 \notin 𝐴) . \end{matrix}

Definition 41: Superset and Proper Superset

A set $𝐴$ is a superset of a set $𝐵$ , denoted $𝐴 \supseteq 𝐵$ , iff $𝐵 \subseteq 𝐴$ . Furthermore, $𝐴$ is a proper superset of $𝐵$ , denoted $𝐴 \supset 𝐵$ or $𝐴 ⊋ 𝐵$ , iff $𝐵 \subset 𝐴$ .

Example.

Define the sets

𝐴 = {1, 2}

𝐵 = {1, 2, 3}

, and

𝐶 = {1, 2}

. Then

𝐴 \subset 𝐵

𝐵 \supset 𝐴

, and

𝐴 = 𝐶

Definition 42: Empty Set

The empty set $\emptyset$ or ${}$ is the unique set that has no elements.

Theorem 11: Universality of the Empty Set

For all sets $𝐴$ , $\emptyset \subseteq 𝐴$ .

Notation: Set Builder Notation

A set can also be defined by specifying a property that its elements must satisfy. This is called set builder notation.

If $𝑆$ is the set of all elements $𝑥$ such that $𝑃 (𝑥)$ is true, we can write:

𝑆 = {𝑥 | 𝑃 (𝑥)} .

If we want to specify the universe of objects $𝑈$ we are considering, we can write:

𝑆 = {𝑥 \in 𝑈 | 𝑃 (𝑥)} .

If $𝑥$ needs to satisfy multiple predicates $𝑃_{1} (𝑥), 𝑃_{2} (𝑥), \dots, 𝑃_{𝑘} (𝑥)$ , we can write:

𝑆 = {𝑥 \in 𝑈 | 𝑃_{1} (𝑥), 𝑃_{2} (𝑥), \dots, 𝑃_{𝑘} (𝑥)} .

Corollary 3

If $𝑆$ is defined using set builder notation over a universe $𝑈$ , then $𝑆 \subseteq 𝑈$ .

Corollary 4

If $𝑆$ is defined using set builder notation with predicate $𝑃$ , then $𝑥 \in 𝑆$ if and only if $𝑃 (𝑥)$ is true.

Definition 43: Standard Numeric Sets

The following sets of numbers are commonly used in mathematics:

The natural numbers $ℕ$ are the set of non-negative

¹ integers:
$ℕ = {0, 1, 2, 3, \dots} .$
The integers $ℤ$ are the set of whole numbers and their negatives:
$ℤ = {\dots, - 3, - 2, - 1, 0, 1, 2, 3, \dots} .$
The positive integers $ℤ^{+}$ are the set of integers greater than $0$ :
$ℤ^{+} = {1, 2, 3, \dots} .$
The rational numbers $ℚ$ are the set of numbers that can be expressed as a fraction of two integers (with a nonzero denominator):
$ℚ = {\frac{𝑝}{𝑞} | 𝑝 \in ℤ \land 𝑞 \in ℤ \land 𝑞 \neq 0} .$
The real numbers $ℝ$ are the set of all points on the number line, including both rational and irrational numbers.

Definition 44: Principle of Extensionality

Two sets $𝐴$ and $𝐵$ are equal, denoted $𝐴 = 𝐵$ , if and only if they have the same elements. Formally:

𝐴 = 𝐵 iff \forall 𝑥 (𝑥 \in 𝐴 \Leftrightarrow 𝑥 \in 𝐵) .

Theorem 12: Double Containment Theorem

Two sets $𝐴$ and $𝐵$ are equal if and only if $𝐴 \subseteq 𝐵$ and $𝐵 \subseteq 𝐴$ . Formally:

𝐴 = 𝐵 iff 𝐴 \subseteq 𝐵 and 𝐵 \subseteq 𝐴 .

Set Operations

It may be useful to define new sets in terms of existing sets using set operations.

Definition 45: Intersection of Two Sets

The intersection of two sets $𝐴$ and $𝐵$ , denoted $𝐴 \cap 𝐵$ , is the set of all elements that are in both $𝐴$ and $𝐵$ . Formally:

𝐴 \cap 𝐵 = {𝑥 | 𝑥 \in 𝐴 \land 𝑥 \in 𝐵} .

Terminology: Disjoint Sets

Two sets $𝐴$ and $𝐵$ are disjoint if their intersection is the empty set, i.e. $𝐴 \cap 𝐵 = \emptyset$ .

Definition 46: Power Set

The power set of a set $𝐴$ , denoted $𝒫 (𝐴)$ , is the set of all subsets of $𝐴$ . Formally:

𝒫 (𝐴) = {𝐵 | 𝐵 \subseteq 𝐴} .

Lists, Cartesian Products, Strings

A list, sequence, or tuple, is a collection of objects where the order of the objects matters and repetition is allowed. In the world of sets, it would be beneficial if lists were not “separate” objects, but rather could be represented as sets. This way, the theory of sets would be sufficient to define and reason about lists, sequences, tuples, and other ordered collections without needing to introduce new primitive objects.

In general, let $(𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛})$ be an ordered $𝑛$ -tuple. Fix the following properties:

Order. $(𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}) \neq (𝑦_{1}, 𝑦_{2}, \dots, 𝑦_{𝑛})$ if there exists some $𝑖$ such that $𝑥_{𝑖} \neq 𝑦_{𝑖}$ .
Repetition. $(𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}) \neq (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}, 𝑥_{𝑛 + 1})$ for any $𝑥_{𝑛 + 1}$ .

The following is a way to represent ordered pairs as sets:

Definition 47: Kuratowski Pairing Function

The Kuratowski pairing $𝜋 (𝑥, 𝑦)$ of two objects $𝑥$ and $𝑦$ is:

𝜋 (𝑥, 𝑦) = {{𝑥}, {𝑥, 𝑦}} .

We can extend the Kuratowski pairing function to represent ordered triples, quadruples, and in general $𝑛$ -tuples as sets:

𝜋 (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}) = 𝜋 (𝜋 (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛 - 1}), 𝑥_{𝑛}) .

Thus, the Kuratowski pairing function can be generalized:

Definition 48: Kuratowski List

The Kuratowski list $𝜋 (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛})$ of a finite sequence of objects $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}$ is the set defined as:

𝜋 (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}) = {\begin{matrix} \emptyset & if 𝑛 = 0 \\ 𝑥_{1} & if 𝑛 = 1 \\ 𝜋 (𝜋 (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛 - 1}), 𝑥_{𝑛}) & otherwise \end{matrix}

The set of all lists can be denoted using a Cartesian product of sets. For two sets, it is defined as follows:

Definition 49: Cartesian Product

The Cartesian product of two sets $𝐴$ and $𝐵$ , denoted $𝐴 \times 𝐵$ , is the set of all pairings of an element from $𝐴$ and an element from $𝐵$ . Formally:

𝐴 \times 𝐵 = {𝜋 (𝑎, 𝑏) | 𝑎 \in 𝐴, 𝑏 \in 𝐵} .

Example.

Let $𝐴 = {1, 2}$ and $𝐵 = {𝑥, 𝑦}$ . Then the Cartesian product $𝐴 \times 𝐵$ is:

\begin{matrix} 𝐴 \times 𝐵 & = {𝜋 (1, 𝑥), 𝜋 (1, 𝑦), 𝜋 (2, 𝑥), 𝜋 (2, 𝑦)} \\ = {{{1}, {1, 𝑥}}, {{1}, {1, 𝑦}}, {{2}, {2, 𝑥}}, {{2}, {2, 𝑦}}} . \end{matrix}

Notation

In the context of sets, let the standard notation for an ordered sequence $(𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛})$ represent the Kuratowski list $𝜋 (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛})$ .

Definition 50: Alphabets and Strings

A string $𝑠$ is a sequence of characters from a given alphabet $Σ$ .

Definition 51: Finite Strings

A finite string $𝑠$ of length $𝑛$ over an alphabet $Σ$ is an element of the catesian product of $Σ$ with itself $𝑛$ times:

𝑠 is a string of length 𝑛 over Σ iff 𝑠 \in \underset{𝑛 times}{\underset{⏟}{Σ \times Σ \times \dots \times Σ}} .

The set of all finite strings over $Σ$ of length $𝑛$ is denoted $Σ^{𝑛}$ .

Example.

The set of all 2D coordinates can be interpreted as the set of all strings of length 2 over the alphabet

ℝ

, i.e.

ℝ^{2}

Definition 52: Set of All Finite Strings

The set of all finite strings over an alphabet $Σ$ is denoted $Σ^{*}$ and is defined as the union of $Σ^{𝑛}$ for all $𝑛 \in ℕ$ :

Σ^{*} = ⋃_{𝑛 \in ℕ} Σ^{𝑛} .

Exercises

Exercise 7.

Show that the empty set

\emptyset

is unique.

Exercise 8.

Let

ℒ

be the Kuratowski list for a list of

𝑛

elements. How many pairs of braces are needed to express

ℒ

in set roster notation?

¹Sometimes, $ℕ$ is defined to exclude $0$ . Use the definition that includes $0$ for these notes.