Set, list, tuple #

Set #

A set can be (informally) viewed as a collection of elements with no duplicate and in no specific order.

Examples.

• $\{2,5\}$ and $\{5,2\}$ are the same set,
• $\{2,5,2\}$ is not a set.

Power set #

Definition. The power set $\mathcal{P}(X)$ of a set $X$ is the set of all subsets of $X$.

Example.

$\qquad\qquad \mathcal{P}(\{a,b,c\}) = \Big\{ \{\}, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \Big\} $

If $X$ is finite with size $n$, then $\mathcal{P}(X)$ has size $2^n$.

Notation. $2^X$ is an alternative notation for $\mathcal{P}(X)$.

Product of sets #

Definition. The product $X_1 \times X_2$ of two sets $X_1$ and $X_2$ is the set of all pairs $(x_1, x_2)$ such that $x_1 \in X_1$ and $x_2 \in X_2$.

Example.

$\qquad\qquad \{a,b\} \times \{1,2,3\} = \{ \ (a,1), (a,2), (a,3), (b,1), (b,2), (b,3)\ \} $

Notation. Similarly to $X_1 \times X_2$:

• $X_1 \times X_2 \times X_3$ denotes the set of all triples $(x_1, x_2, x_3)$ such that $x_1 \in X_1,\ x_2 \in X_2$ and $x_3 \in X_3$.
• $X_1 \times .. \times X_k$ denotes the set of all tuples $(x_1, .., x_k)$ such that $x_1 \in X_1,..,\ x_k \in X_k$.

Notation.

• $X^2$ is sometimes used for $X \times X$,
• $X^3$ is sometimes used for $X \times X \times X$,
• etc.

Set comprehension #

Example. If $X$ is a set of numbers, then the expression

$\qquad\{x^2 \mid x \in X,\ x \ge 5\}$

means

$\qquad$ all $x^2$ such that $x \in X$ and $x \ge 5$.

This is the set that consists of all numbers greater or equal to $5$ in $X$, each squared.

For instance, if $X = \{2,3,5,7\}$, then

$\qquad\{x^2 \mid x \in X,\ x \ge 5\} = \{25, 49\}$

Syntax and meaning. A set comprehension is an expression of the form

$\qquad \{\alpha \mid \varphi_1, \ldots, \varphi_n \}$

where:

• $\alpha$ is a expression (e.g. $x^2$), and
• each $\varphi_i$ is a Boolean condition (e.g. $x \in X$).

It describes the set of all $\alpha$’s such that the conditions $\varphi_1, \ldots, \varphi_n$ hold (altogether).

Terminology. In a set comprehension, the symbol $|$ means “such that”.

List, Tuple #

List #

Definition. A list is a (possibly infinite) sequence.

As opposed to a set, a list may contain duplicates, and the position of its elements matters.

Example. The following three lists are different:

• $1,1,4$
• $1,4,1$
• $1,4$

Terminology. In programming languages, the term “list” is often reserved to those whose elements have the same type. For instance, a list of integers or a list of strings.

Tuple #

Definition. A tuple is a finite list.

A tuple is often written in parentheses.

Example.

• $\ ()$ is the 0-tuple or empty tuple,

• $\ (5,3)$ is a 2-tuple or pair,

• $\ (\mathit{“banana”},5)$ is another pair,

• $\ (\mathit{“tomato”},5,\mathit{“tomato”})$ is a 3-tuple or triple, etc.

An $n$-tuple can also be viewed as an element of a product of $n$ sets.

Examples.

• $ (5,3) \in \mathbb{N}\times \mathbb{N}$
• $ (5,3) \in \mathbb{Z}\times \mathbb{N}$
• $ (5,\sqrt{3}) \not\in \mathbb{N}\times \mathbb{N}$
• $ (5,\sqrt{3}) \in \mathbb{N}\times \mathbb{R}$
• $ (\mathit{“tomato”},5,\mathit{“tomato”}) \in \mathsf{String} \times \mathbb{N} \times \mathsf{String} \\$