Discrete Mathematics: Sets

(Up)

This is intended to be a recap of notation as covered in an introductory discrete mathematics course.

The elementship-relation

The basic statement about a set

$A$ we can make is that it contains an element

$a$, which is written as

$$a\in A.$$

The subset-relation

We also need to be able to say that

$A$ is a subset of

$B$, which can be written in set-theoretic notation as (read

$\mathrm{\forall }$ as "for all")

$$A\subseteq B\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{\iff }\mathrm{\forall }a(a\in A\Rightarrow a\in B).$$

The "braces notation"

We also need to review different ways of defining sets. The simplest one is just to list the elements of a set as in

$$\{1,2,3\}$$

To illustrate the notation reviewed so far, we have

$1\in \{1,2,3\}$ and

$\{1,2,3\}\subseteq \mathbb{N}$, where

$$\mathbb{N}=\{0,1,2,3,4,\dots \}$$

is the standard notation for the natural numbers.

Inductive definitions

Above, I am taking

$\mathbb{N}$ for granted, but we can also define it ourselves by saying that

$0\in \mathbb{N}$ and if

$n\in \mathbb{N}$ then also

$n+1\in \mathbb{N}$. Note that this definition avoids the "

$\dots$" and instead uses only two rules. We then say that

$\mathbb{N}$ is the smallest set closed under the rules. This style of defining sets is called definition by induction and we will see more about this in a later lecture.

Defining infinite sets inductively is very common. For example, the syntax of programming languages is defined inductively and this inductive definition in turn allows us to generate parsers automatically from the language definition.

Set-comprehension

Another way of defining sets is called comprehension. A definition by comprehension has the form

$$A\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{x\in X\mid \dots \}$$

For example, we may define the set of even numbers as

$$Even\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{n\in \mathbb{N}\mid \mathrm{\exists }m\in \mathbb{N}.2\cdot m=n\}.$$

Here

$\mathrm{\exists }m.\dots$ is short for "there is

$m$ such that

$\dots$"

Exercise: Define the set of odd numbers in the same style.

Cartesian Product

We can use comprehension to define the so-called cartesian product ^[1]

$$A\times B\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\{(a,b)\mid a\in A,b\in B\}$$

which is just the set of pairs that can be built by taking elements of

$A$ in the first component and elements of

$B$ in the second.

Example: Fractions

$n/m$ are pairs

$(n,m)$ where we use the special notation "

$/$" just to indicate that we want to think of this pair of numbers as a fraction and not, eg, as the coordinates of a point in the plane.

More Notation (not so important now, but useful later): If in the above definition we have

$A=B$ then we may abbreviate

$A\times A$ as

$A^2$. Similarly, we abbreviate

$(A\times A)\times A$, usually written just as

$A\times A\times A$, by

$A^3$. This notation extends to

$A^n$ for any

$n\in \mathbb{N}$. The set

$A^0$ is called the empty product and has exactly one element, often called the empty word. The empty word has not standardized notation and one may find different symbols for it such as

$()$ and

$[]$ and

$⟨⟩$ and

$0$ and

$ϵ$ (epsilon). The set

$A^0$ always has exactly one element, whatever

$A$ is. For this reason,

$A^0$ is sometimes written just as

$1$. We then obtain the equation

$A^0=1$, which is similar to a familiar equation for numbers, namely that

$a^0=1$ for all numbers

$a$ (possibly restricted to

$a\ne 0$).

---

1. This is called "cartesian" product in honour of Descartes, who, in his "Geometry", about which we talked already, invented the represenation of points in the plane by

   $x$ and
   $y$-coordinates, that is, the representation of points as elements of
   $\mathbb{R}\times \mathbb{R}$. ↩︎