Sequences

A sequence is a mathematical datatype that bears similarities to sets. A sequence $S$ also contains some elements, but we usually refer to them as components. There are two major differences between sets and sequences:

1. Components of a sequence are ordered. There is either $0$, or $1$ or $2$, or … $n$ components, when the sequence if finite or it could be an infinite sequence that has an $i$‘th component for any non-zero natural number $i$.

2. Different components of a sequence could be equal. For example $(a,b,a)$ has $a$ repeating, and this is a different sequence compared to $(a,b,b)$ even though they both have 3 componetns. If we interprete them as sets, then they will be equal sets with $2$ elements each.

Cartesian Product

We can use set products to get new sets whose elements are sequences. Cartesian product is a very useful way of doing it.

Set Products. A Cartesian product of sets $S_1, S_2, \cdots, S_n$ is a set consisting of all possible sequences of $n$ elements where the $i$\textsuperscript{th} element is chosen from $S_i$.

$$ S_1 \times S_2 \times \cdots \times S_n = { (s_1, s_2, \cdots, s_n) | s_i \in S_i } $$

How many elements are in $A \times B$?

Relations and Binary Relations

A relation between some elements from set $A$ and some elements from set $B$ could be represented by putting all such pairs $(a,b)$ in a set $P$. As you can see, this way, $P$ would be a subset of the cartesian product $A \times B$, namely $P \subseteq A \times B$. More formally we have the following definition.

A binary relation, $P$, is defined with respect to a domain set, $A$, and a codomain set, $B$, and it holds that $P$ is $P \subseteq A \times B$. When we draw $P$ by connecting elements of $A$ to $B$ based on their membership in $P$, we call this the graph of $R$.

The notion of relations could be generalized to having relations between elements coming from multiple sets $A,B,C$, and we can also talk about relations of the form $P \subseteq A \times B \times C$, but the binary relation remains a very important data type as it allows us to define functions.

Functions

The concept of a function $F$ models is a special form of a binary relation $R$ between $A$ and $B$ where for every element $a \in A$ there is at most one element in $b \in B$ that is in relation with $a$ (i.e. $(a,b) \in R$). More formally, we use a direct new notation just reserved for working with functions.

A function is a mathematical datatype that associates elements from one set, called the domain, with elements from another set, called a codomain.

$$ f: \textrm{\em domain} \rightarrow \textrm{\em codomain} $$

Defining a function. To define a function, we need to describe how elements in the domain are associated with elements in the codomain.

#

What are the (sensible) domains and codomains of each function below:

$$ f(n) ::= |n| \qquad \qquad f(x) ::= x^2 \qquad\qquad f(n) ::= n + 1 \qquad\qquad f(a, b) ::= a / b $$

$$ f(x) ::= \sqrt{x} \qquad \qquad \qquad f(S) ::= \textrm{minimum}_{<}(S) $$