Lesson (I)

Table of contents

1. Set theory as a foundation for mathematics
2. Building Sets
3. Some Important Sets
4. Operations on Sets
5. Equality of Sets
6. Classical Sets

Set theory as a foundation for mathematics

Set theory is a foundation for mathematics. This means

• All abstract mathematical concepts can be expressed in the language of set theory.
• All concrete mathematical objects can be encoded as sets.
• We can write down our mathematical reasoning in set theory: true statements about mathematical objects can be deduced from the axioms of set theory and the rules of logic.

Georg Cantor, the founder of set theory, gave an informal definition of sets:

By a set we mean any collection $M$ of determinate, distinct objects (called the elements of $M$) of our intuition or thought into a whole.

Cantor defined sets to make the idea of infinity, which were objects of fascination for millennia, precise, but soon set theory took a much bigger role in mathematics: It became a foundation for the whole of mathematics. This was due to work of many brilliant set theorists and mathematicians, most notably Bourbaki. All mathematical objects you may see in any undergraduate mathematics course is a set: This includes geometric objects such as manifolds, vector bundles, etc as well as algebraic objects such as monoids, groups, rings, etc.

For us, a set is a collection of elements from a specified universe of discourse. The collection of everything in the universe of discourse is called the universal set, denoted by $\mathcal{U}$.

Given a set $A$ of objects in some universe and an object $a$, we write the proposition \[ a \in A \] to say that the element $a$ belongs to the set $A$. We write \[ a \not\in A \] as shorthand for the proposition $\neg (a \in A)$.

Building Sets

How to Form Sets

But it is not enough to just have a vague of idea of what sets are, we actually need to know how to form sets. Cantor’s informal characterization suggests that whenever we have some property (aka predicate), $P(x)$, of a domain $X$, we can form the set of elements that have the property $P(x)$. We denote this set by \[ \{ x \in X \mid P(x) \} \, . \] We read this as “the set of element $x$ of $X$ such that $P(x)$” or as “the set of element $x$ of $X$ which satisfy $P(x)$”.

The notation above is called the set-builder notation. We call the set \( \set{x \in X \mid P(x)} \) the extension of property/predicate $P$.

In above the predicate $P$ had only one variable (aka parameters), but in general it can have many variables. For instance consider the exmaple \[ P(x,y) = (x+y=0) \] over real numbers. The set \[ \{ (x,y) \in \RR \times \RR \mid P(x,y) \} \] is the set of all points in the 2-dim plane which lie on the line described by the equation $y = -x$.

Or we can have a predicate

\[ C(t,h) = (t < 25 ) \land (t > 15) \land (h > 40 ) \land (h < 60) \]

where $t$ is a temperature variable measured in centigrade and $h$ is a humidity variable measured in percentage. Now, we can form the set of all places in the world where the predicate $C(t,h)$ holds:

\[ \set{ x \in W \mid C(t(x),h(x)) } \]

Note that we substituted terms $t(x)$ and $h(x)$ for $t$ and $h$ in $C(t,h)$ (Recall how the substitution of terms in predicates works from the lesson on predicates).

When forming sets using predicates, we can think of the predicate $P(x)$ as a sort of filter or checking mechanism: it selects $x$’s according to the filtering criteria.

Here’s another example: Consider the set $\NN$ of natural numbers and the predicate $E$ over $\NN$, that is

\[ E(n) = n \text{ is even} .\]

We form the set of even numbers as follows:

\[ \EE = \set{n \in \NN \mid E(n) } \]

Sometimes in informal mathematical writing, you see the notation $\set{2,4,6,\ldots}$ for the same set $\EE$. This notation rely on the reader’s ability to infer the pattern being followed and correctly guess the intention of the writer, so use it with caution, or better yet, do not use it!

Here are more examples of sets written in the set builder notation:

• $\set{ n \in \ZZ \mid n \text{ is odd} }$
• $\set{n \in \NN \mid n \text{ is prime} }$
• $\set{n \in \ZZ \mid n \text{ is prime and greater than } 2 }$
• $\set{ n \in \NN \mid n \text{ can be written as a sum of its proper divisors} }$
• $\set{ a \in \RR \mid a \text{ is equal to } 1, 2, 3, \text{ or } \pi }$
• $\set{a \in \RR \mid (a < 0) \lor (a > 0)}$

But the following expressions do not form a set:

• $\set{n \in \ZZ \mid \frac{n}{2} }$
• $\set{z \in \CC \mid (z < 0) \lor (z > 0)}$

✏️ Challenge

Suppose $P$ is a predicate on natural numbers. In below, we are defining sets $A$, $B$, $C$ using the set builder notation. Determine which of the following expressions correctly determines a set, and which ones are incorrect/illegal?

• $A = \set{n \in A \mid \neg P(n)}$
• $B = \set{n \in \ZZ \mid n \in \NN}$
• $C = \set{x \in \RR \mid \sqrt{x} < 2}$
• $D = \set{n \in \NN \mid n \text{ is sum of four squares} \lor \exists n P(n)}$

Different Notations

Sometimes a set is formed without the domain of the predicate being (explicitly) specified. In such a case, we can think of the domain being the universal set $\mathcal{U}$. Therefore the set

\[ \set{n \mid n \text{ is a natural number}} \]

is a shorthand for the set

\[ \set{n \in \U \mid n \text{ is a natural number}} \]

This sets pick all the elements in the universe which are natural numbers.

An alternate form of set-builder notation uses an expression involving one or more variables to the left of the vertical bar, and the range of the variable(s) to the right. The elements of the set are then the values of the expression as the variable(s) vary: \[ \set{ \mathsf{expr}(x) \mid x \in X } \text{ is defined to mean } \set{ y \mid \exists x \in X (y = \mathsf{expr}(x) )} \]

For example, the expression $\set{2n \mid n \in \NN }$ denotes the set $\EE$ of even numbers. It is shorthand for $\set{n \in \mathbb{N} \mid \exists k \in \mathbb{N},\, n=2k }$.

We can even use a mix of the two notations: The set \[ \set{ p^2 + 1 \mid p \text{ is prime} } \] consists of all numbers whose predecessor is a square of a prime number.

Some Important Sets

Using set-builder notation, we can define a number of common and important sets.

• The empty set: $\emptyset = \set{ x \mid \bot } \, . $
• The universe: $ \U = \set{ x \mid \top } \, .$
• Singleton sets: for an object $a$, the singleton set $\set{a}$ is formed as $ \set{ x \mid x = a }$.
• For distinct objects $a$ and $b$, $\set{ x \in \mathcal U \mid (x = a) \lor (x = b) }$ gives the set $\set{a , b}$.
• Similarly, \[ \set{ x \in \mathcal U \mid (x = a_1) \lor (x = a_2) \lor \ldots \lor (x=a_n) } \] describes the set contaning $n$ elements $a_1, \ldots, a_n$.

We say that a set $X$ is inhabited if it has at least one element. Formally, a set $X$ is inhabited if the sentence $\exists x \in X. \top $ or equivalently the sentence $\exists x \, (x \in X) )$ is true.

We say that a set $X$ is empty if it is not inhabited, that is the sentence $ \neg \exists x \, (x\in X) $ is true. A set is non-empty if it is not empty.

✏️ Challenge

Give a constructive proof that the set $\emptyset$ is empty.

✏️ Challenge

Give a natural deduction proof of the fact that that every inhabited set is non-empty.

We say that a set $A$ is decidable if the sentence \[ \forall x. x \in A \lor x \notin A \] holds.

Operations on Sets

Using the set-builder notation, we can define a number of primary operations on sets.

• Union of sets $A$ and $B$ is given by the set $A \cup B = \set{ x \mid x \in A \lor x \in B }$
• Intersection of sets $A$ and $B$ is given by the set $A \cap B = \set{ x \mid x \in A \land x \in B } $
• Complement of a set $A$ is given by the set $\compl{A} = \set{ x \mid \neg (x \in A) }$
• Relative complement of set $A$ with respect to set $B$ is given by the set $A \setminus B = \set{ x \mid x \in A \land \neg x \in B }$

One can define many more operations on sets, but they can be derived from these primary operations. This is similar to the situation with logical connectives. An important example is the disjoint union of two sets, say $A$ and $B$, defined as follows: \[ A \sqcup B \defeq (A \times \set{0}) \cup (B \times \set{1}) \]

Sometimes we denote the disjoint union with a different notation, namely “$+$”. For instance, \[ \set{🥕} + \set{⛄} = \set{🥕,⛄} \quad \text{ and } \quad \set{🥕} + \set{🥕} = \set{ (🥕, 0), (🥕, 1)} \]

Challenge

What is $\NN + \NN$?

Challenge

Describe the elements of $(A + B) + C$ and $A + (B + C)$.

By their definition, the primary operations on sets are intimately related to the logical connectives. In fact one can prove that

• \( \forall x \; (x \in \emptyset \leftrightarrow \bot) \)
• \(\forall x \; (x \in \mathcal U \leftrightarrow \top) \)
• \( \forall x \; (x \in A \cup B \leftrightarrow x \in A \vee x \in B) \)
• \( \forall x \; (x \in A \cap B \leftrightarrow x \in A \wedge x \in B) \)
• \( \forall x \; (x \in \compl A \leftrightarrow \neg x \in A) \)
• \( \forall x \; (x \in A \setminus B \leftrightarrow x \in A \wedge \neg x\in B) \)

The connection between logic and set theory runs even deeper; we make this more clear once we are equipped with the notion of function between sets.

Equality of Sets

A mathematical principle is that whenever we introduce a mathematical concept, we should ask ourselves what it means for two instances/realizations of that concept to be identified (aka equal). For instance, for the concept of natural number, this is intuitively clear to us: we know without a moment of reflection that $2=2$ but $\neg(2=3)$. However when the concepts we introduce get more complicated judging whether there is an identification (aka an equality) between instances of those concepts becomes less obvious.

Here, we ask ourselves when two sets are equal?

1. Are the sets \[ \set{n \in \NN \mid \exists k \in \NN,\, n = 2k } \quad \text{and} \quad \set{n \in \QQ \mid \exists k \in \NN,\, n = 2k } \] equal?

2. How about “the set of prime numbers less than $2$” and “the set of even prime numbers greater than $2$”?

3. How about \[ \set{x \in \QQ \mid x^2 < 2} \quad \text{and} \quad \set{x \in \QQ \mid x^2 \leq 2} \, ? \]

We define two sets $A$ and $B$ to be equal precisely when they have the same elements, in other words, every element of $A$ is an element of $B$ and vice versa. We write $A=B$ to denote the equality of $A$ and $B$.

The formal sentence expressing $A=B$ is
\[ \forall x \, (x \in A \Leftrightarrow x \in B) \, .\] Let us define predicate $P_A$ and $P_B$ by \[ P_A (x) = (x \in A) \quad \text{and} \quad P_B (x) = (x \in B) \, . \] Therefore, the definition of equality of sets says that $A$ and $B$ are equal sets if and only if $P_A$ and $P_B$ are equivalent predicates. Conversely, starting from equivalent predicates $P$ and $Q$, ranging over a domain $X$, we obtain the equality \[ \set{x \in X \mid P(x)} = \set{x \in X \mid Q(x)} \, .\]

We say that this notion of equality is extensional since although two predicates $P(x)$ and $Q(x)$ can have different intensions they can have the same extension and therefore giving rise to the same sets. Consider for instance the example above where $P(n)$ is defined to be “$n$ is a prime numbers less than $2$” and $Q(n)$ is defined to be “$n$ is an even prime number greater than $2$”.

Therefore, using the extensional definition of equality of sets, the answers to the questions (1)-(3) of the previous slide are all positive.

As an example we prove the distributivity of intersection ($\cap$) over union ($\cup$) of sets.

Theorem. Let $A$, $B$, and $C$ denote sets of elements of some domain. Then \[ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \, .\]

Proof. Let $x$ be an arbitrary element of $A \cap (B \cup C)$. Then $x$ is in $A$, and either $x$ is in $B$ or $x$ is in $C$. In the first case, $x$ is in $A$ and $x$ is in $B$, and hence $x$ is in $A \cap B$. In the second case, $x$ is in $A$ and $C$, and hence $x$ is in $A \cap C$. Therefore, $x$ is in $(A \cap B) \cup (A \cap C)$.

Conversely, suppose $x$ is in $(A \cap B) \cup (A \cap C)$. There are now two cases:

• First, suppose $x$ is in $A \cap B$. Then $x$ is in both $A$ and $B$. Since $x$ is in $B$, it is also in $B \cup C$, and so $x$ is in $A \cap (B \cup C)$.
• The second case is similar: suppose $x$ is in $A \cap C$. Then $x$ is in both $A$ and $C$, and so also in $B \cup C$. Hence, in this case also, $x$ is in $A \cap (B \cup C)$, as required. $\qed$.

You should be able to translate the proof above into a natural deduction proof, although it may look a bit unruly.

Challenge

Construct a natural deduction proof of the sentence \[ \forall x \; (x \in A \cap (B \cup C) \leftrightarrow x \in (A \cap B) \cup (A \cap C)) \, . \]

Challenge

1. Prove the following equalities of sets, possibly using the Law of Excluded Middle. Identify the statements whose proof require invoking LEM. Explain why.

1. How do you describe the resemblance between the columns?

For sets $A$ and $B$, the set $A$ is said to be a subset of $B$, written \[ A \subseteq B \, , \] if every element of $A$ is an element of $B$. In contrast to equality of sets we can think of $\subseteq$ as “inequality” of sets. It is similar to the inequality $2 \leq 3$ (We make this idea more precise later when we will talk about partial orders.)

Formally, $A \subseteq B$ is expressed by the sentence [ \forall x \; (x \in A \To x \in B) \, . ]

Challenge

Do you think that $\varnothing \subseteq \varnothing$? Justify your answer by providing a proof or a counter-example.

Theorem. For any two sets $A$ and $B$ we have $A=B$ if and only if $A \subseteq B$ and $B \subseteq A$.

Challenge

Prove the following facts about the subset relationship:

• For all sets $A$ we have $A \subseteq A$.
• For all sets $A$, $B$ and $C$, if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$.
• For all sets $A$ we have $\emptyset \subseteq A$.
• For all sets $A$, $B$, if $A \cup B = B$ then $A \subseteq B$.
• For all sets $A$, $B$, if $A \cap B = A$ then $A \subseteq B$.

Challenge

Which of the following statements are true regardless of the choice of sets $A,B,C$? Justify your answer.

• $A \subseteq B \cup C \implies A \subseteq B \lor A \subseteq C$
• $A \subseteq B \cap C \implies A \subseteq B \land A \subseteq C$
• $A \cap B \subseteq C \implies A \subseteq C \land A \subseteq C$
• $A \cap B \subseteq C \implies A \subseteq C \lor A \subseteq C$
• $A \cup B \subseteq C \implies A \subseteq C \lor A \subseteq C$

Challenge

Constructively prove the following inequlities of sets.

Classical Sets

We can show constructively that for any set $A$, \[ A \subseteq \compl{\compl{A}} \]

✏️ Challenge

Show that the Law of Excluded Middle is equivalent to the statement that for every set $A$, \[ \compl {\compl{A}} \subseteq A \, .\]

De Morgan for Sets

Since sets are formed as extension of predicates we expect to have the following equalities of sets if we reason classically.