Set, tuple, function #

Set #

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

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

For instance, if

then

Note. An alternative notation for the power set of $S$ is $2^S$.

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

Definition. The product $S_1 \times S_2$ of two sets $S_1$ and $S_2$ is the set of all pairs $(s_1, s_2)$ such that $s_1 \in S_1$ and $s_2 \in S_2$.

For instance, if

and

then

Notation. Similarly to $S_1 \times S_2$:

• $S_1 \times S_2 \times S_3$ denotes the set of all triples $(s_1, s_2, s_3)$ such that $s_1 \in S_1, s_2 \in S_2$ and $s_3 \in S_3$.
• $S_1 \times .. \times S_k$ denotes the set of all tuples $(s_1, .., s_k)$ such that $s_1 \in S_1, .., s_k \in S_k$.

Notation.

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

Tuple #

Definition. A tuple (or list) over a set $S$ is a finite sequence of (possibly repeated) element of $S$.

For instance:

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

-$\ (a)$ is a 1-tuple,

-$\ (b,a)$ is a 2-tuple or pair,

-$\ (a,b,a)$ is a 3-tuple or triple, etc.

Function #

A function (or map) $f\colon X \to Y$ maps each element $x$ of its domain $X$ to an element $f(x)$ of its codomain $Y$.

Definition. A function $f\colon X \to Y$ is:

• injective is no two elements in its domain have the same image, i.e. if for all $ x_1, x_2 \in X$,

$\qquad \qquad x_1 \neq x_2$ implies $f(x_1) \neq f(x_2)$

• surjective if every element in its codomain has a preimage, i.e. if

$\qquad \qquad$ for each $y \in Y$, there is a $x \in X$ such that $y = f(x)$.

• bijective if it is injective and surjective.

A function $f\colon X \to Y$ can equivalently be viewed as a set of “key-value” pairs, namely the set of all pairs $(x, f(x))$ such that$ x \in X$.

If $f$ has finite domain, then it can be (physically) represented as this set of pairs. For instance, the function

defined by

can be represented as the set:

We may also use the symbol $\mapsto$ to represent these pairs. For instance, we may represent the above function as

Multiset #

A multiset (or bag) is a finite collection of elements in no specific order, possibly with duplicates.

Square bracket are sometimes uses to distinguish a multiset from a set or a tuple. For instance:

and

are multisets (the latter is also a set).

Besides,

and

denote the same multiset.