2 Definition and notation

An N-tuple is a list with N values such that the value and order of these values are important. The notation of a tuple with $n$ values is as follows:

$(a_1, a_2, a_3, \ldots a_n)$

Note that we use round parantheses instead of curly braces. This helps to distinguish sets from tuples.

Furthermore, two tuples with $n$ values each are the same based on the following rule:

$(a_1,\ldots a_n) = (b_1,\ldots b_n) \leftrightarrow (a_1 = b_1 \wedge \ldots a_n = b_n)$

Also, there is an empty tuple (0-tuple) that is the identity of tuple concatination: $(a_1) = (a_1, ())$ .

By definition, an $n$ tuple (where $n \ge 2$ ) can be rewritten as follows:

$(a_1,\ldots a_n) = (a_1,(a_2,\ldots a_n))$

Note that the same value can appear multiple times in a tuple. By comparison, duplicate values are not permitted in sets.

Also, note that a tuple can be an element in a set, and a set can be a value in a tuple. The significance of this statement leads to a method to transform a tuple into a set as follows:

• $()$ is represented by $\{\}$
• $(a, l)$ ($a$ is a value, $l$ is a tuple) is represented by $\{a, \{a, l\}\}$

This translation makes it possible to translate a tuple into a set, even though a set does not permit duplicate values! Let us observe an example:

$$(a, a) = (a, (a))$$ (1)

$$= (a, (a, ()))$$ (2)

$$= (a, (a, \{\}))$$ (3)

$$= (a, \{a, \{a, \{\}\}\})$$ (4)

$$= \{a, \{a, \{a, \{a, \{\}\}\}\}\}$$ (5)

Here is an explanation of the transformation:

• Step 1: a tuple consists of the first value, and the rest of it can be seen as a smaller tuple.
• Step 2: any tuple concatinated with $()$ is itself.
• Step 3: this is the base case, an empty tuple is represented by an empty set.
• Step 4: this is the first step to replace $(a, \{\})$ with $\{a, \{a, \{\}\}\}$
• Step 5: this is the second step to replace $(a, s)$ with $\{a, \{a, s\}\}$ , where $s = \{a \{a, \{\}\}\}$