Tuples: The basics

  • sets (basic notation)

Like sets, tuples are collections of elements. Tuples also allow an element to be present multiple times, so they are not idempotent. And tuples also care about the order of the elements. This makes them very similar to strings, but tuples are more general because they can contain arbitrary objects, including other tuples.

Notation

An \(n\)-tuple \(u\) consists of exactly \(n\) elements. We also say that \(u\) has length \(n\) One also writes \(\left | u \right | = n\) to indicate that the tuple \(u\) has length \(n\), and in this case we say that \(u\) has \(n\) components. Tuples are usually written between pointy brackets, e.g. the pair \(\left \langle a,b \right \rangle\), the triple \(\left \langle a,b,c \right \rangle\), or the \(1\)-tuple \(\left \langle a \right \rangle\).

The pair \(\left \langle a,b \right \rangle\) is of length \(2\). Its first component is \(a\), its second component is \(b\).

The pair \(\left \langle a,a \right \rangle\) is also of length \(2\). Its first component is \(a\), and its second component is also \(a\).

Tuples may contain complex objects, including other tuples. The content of these objects is not considered when computing a tuples length.

Consider \(\left \langle a,b \right \rangle\) and \(\left \langle a,\left \{ b,c \right \} \right \rangle\). They are distinct tuples, but they are both of length 2.

For each one of the following tuples, compute its length.

  • \(\left \langle a,b,a \right \rangle\)
  • \(\left \langle a,\left \langle b \right \rangle,a \right \rangle\)
  • \(\left \langle a,\left \langle b,a \right \rangle \right \rangle\)
  • \(\left \langle \left \{ a,b \right \}, \left \langle a \right \rangle \right \rangle\)
  • \(\left \langle \left \langle a, b,\left \{ a,a \right \} \right \rangle \right \rangle\)

Sometimes we are only interested in a specific component of a tuple. In this case, we write \(\pi_i(u)\) for the \(i\)-th component of \(u\). Sometimes this is also called the \(i\)-th projection of \(u\).

Consider once more the pair \(\left \langle a,b \right \rangle\). Here \(\pi_1(\left \langle a,b \right \rangle) = a\) and \(\pi_2(\left \langle a,b \right \rangle) = b\).

For the pair \(\left \langle a,a \right \rangle\), \(\pi_1(\left \langle a,a \right \rangle)\) and \(\pi_2(\left \langle a,a \right \rangle)\) are both \(a\).

Note that \(\pi_i(u)\) is undefined if \(u\) is not a tuple or if \(i\) exceeds the length of \(u\).

There is no defined value for \(\pi_3(\left \langle a,b \right \rangle)\) because \(\left \langle a,b \right \rangle\) has only two components and thus cannot have a third component. Similarly, \(\pi_3(\left \{ a,b,c \right \})\) is undefined because sets only have elements, not components.

For each one of the formulas below, what is its value?

  • \(\pi_3(\left \langle a,b,c,d \right \rangle)\)
  • \(\pi_8(\left \langle a,b,c,d \right \rangle)\)
  • \(\pi_0(\left \langle a,b,c,d \right \rangle)\)
  • \(\pi_3(\left \langle a,b,\left \langle c,d \right \rangle \right \rangle)\)
  • \(\pi_1(\pi_3(\left \langle a,b,\left \langle c,d \right \rangle \right \rangle))\)

Identity

Two tuples \(u\) and \(v\) are identical iff they are of the same length \(n\) and agree on all their components: for all \(0 < i \leq n\), it must hold that \(\pi_i(u) = \pi_i(v)\).

The pair \(\left \langle a,a \right \rangle\) is distinct from the 1-tuple \(\left \langle a \right \rangle\), the triple \(\left \langle a,a,a \right \rangle\), or the \(4\)-tuple \(\left \langle a,a,a,a \right \rangle\) because all these tuples have distinct length.

The tuple \(\left \langle 3,5 \right \rangle\) is distinct from the tuple \(\left \langle 5,3 \right \rangle\). While they have the same length, they differ on their first component: \(\pi_1(\left \langle 3,5 \right \rangle) = 3 \neq 5 = \pi_1(\left \langle 5,3 \right \rangle)\). They also differ on their second component, but we don’t even need to consider this because disagreeing on a single component is enough to render tuples distinct.

Explain why \(\left \langle a,b \right \rangle = \left \langle b,a \right \rangle\) implies \(a = b\).

This definition of identity of tuples immediately implies two crucial properties:

  1. In contrast to sets, tuples are not idempotent.
  2. In contrast to sets, tuples care about order.

Fill in the gaps with \(=\) and \(\neq\) as appropriate, assuming that \(a\) and \(b\) are distinct elements:

  • \(\left \langle a \right \rangle \_ \left \langle b \right \rangle\)
  • \(\left \langle a,b,a \right \rangle \_ \left \langle a,b,b \right \rangle\)
  • \(\left \langle a,b,a,a \right \rangle \_ \left \langle a,b,a,a \right \rangle\)
  • \(\left \langle a,a,b,a \right \rangle \_ \left \langle a,b,a,a \right \rangle\)
  • \(\left \langle a,a,b,a \right \rangle \_ \left \langle a,a,\left \{ b \right \},a \right \rangle\)
  • \(\left \langle a,a,b,a \right \rangle \_ \left \langle a,\left \langle a,b \right \rangle,a \right \rangle\)

Note that just like \(a \neq \left \{ a \right \}\), it also holds that \(a \neq \left \langle a \right \rangle\). A container with \(a\) in it is not the same thing as \(a\) by itself.

Concatenation

Two tuples \(a\) and \(b\) can be concatenated into a single large tuple \(a \cdot b\) that contains all elements of \(a\) and \(b\), in the same order.

Given an \(m\)-tuple \(a \mathrel{\mathop:}=\left \langle a_1, \ldots, a_m \right \rangle\) and an \(n\)-tuple \(b \mathrel{\mathop:}=\left \langle b_1, \ldots, b_n \right \rangle\), their concatenation is the \(m+n\)-tuple \(a \cdot b \mathrel{\mathop:}=\left \langle a_1, \ldots, a_m, b_1, \ldots, b_n \right \rangle\).

Tuple concatenation is associative. This means that for any tuples \(a\), \(b\), and \(c\), it holds that \(a \cdot(b \cdot c) = (a \cdot b) \cdot c\).

The concatenation of \(\left \langle x,y \right \rangle\) and \(\left \langle z \right \rangle\) is \(\left \langle x,y,z \right \rangle\). If we concatenate \(\left \langle x,y,z \right \rangle\) and \(\left \langle y,y,y \right \rangle\), we get \(\left \langle x,y,z,y,y,y \right \rangle\).

We could have gotten the same result by proceeding in a different order. We first concatenate \(\left \langle z \right \rangle\) and \(\left \langle y,y,y \right \rangle\) into \(\left \langle z,y,y,y \right \rangle\). We then concatenate \(\left \langle x,y \right \rangle\) and \(\left \langle z,y,y,y \right \rangle\) to obtain \(\left \langle x,y,z,y,y,y \right \rangle\). That’s indeed the same output as before. Overall, then, \[(\left \langle x,y \right \rangle \cdot\left \langle z \right \rangle) \cdot\left \langle y,y,y \right \rangle = \left \langle x,y \right \rangle \cdot(\left \langle z \right \rangle \cdot\left \langle y,y,y \right \rangle) = \left \langle x,y,z,y,y,y,y \right \rangle.\]

Calculate the result of the following concatenations.

  • \(\left \langle a,b \right \rangle \cdot((\left \langle c \right \rangle \cdot\left \langle a,b \right \rangle) \cdot\left \langle a,c,e \right \rangle)\)
  • \((\left \langle a,b \right \rangle \cdot\left \langle c \right \rangle) \cdot(\left \langle a,b \right \rangle \cdot\left \langle a,c,e \right \rangle)\)

Write down all possible ways of obtaining \(\left \langle a,b,c,d \right \rangle\) via concatenation of tuples whose length is at least \(1\). For instance, one possible way is \(\left \langle a,b \right \rangle \cdot\left \langle c, d \right \rangle\), but there’s several more.

Tuple concatenation is not commutative. That is to say, for some tuples \(a\) and \(b\) it is not the case that \(a \cdot b = b \cdot a\). Illustrate this with an example.

Keep in mind that tuple concatenation is only defined for tuples.

None of the following are valid instances of tuple concatenation:

  • \(\left \langle a,b \right \rangle \cdot 5\)
  • \(\left \langle a,b \right \rangle \cdot\left \{ 5 \right \}\)

The empty tuple

Remember that strings had a special empty string \(\varepsilon\). The tuple-counterpart for this is the empty tuple \(\left \langle \right \rangle\). It is the only 0-tuple. With respect to concatenation, the empty tuple behaves like \(0\) with respect to addition. That is to say, concatenating a tuple with the empty tuple does not change said tuple.

Compute \(\left \langle a \right \rangle \cdot\left \langle \right \rangle\) and \(\left \langle \right \rangle \cdot\left \langle a,a,a \right \rangle\).

Difference to strings

Strings can be regarded as tuples over some fixed alphabet of symbols. For instance, the string \(\mathit{abc}\) can be viewed as the tuple \(\left \langle a,b,c \right \rangle\). However, tuples are more general because their elements do not need to be symbols of some alphabet. Just like sets (and multisets, if you have encountered those already), tuples can contain arbitrary objects. So a tuple may consist of sets, multisets, other tuples, functions, relations, any combination of those, and much, much more.

All of the following are valid tuples, but none of them are possible strings:

  • \(\left \langle \left \{ 5, -5 \right \}, 25 \right \rangle\) is a pair that consists of the set \(\left \{ 5, -5 \right \}\) and the number \(25\).
  • \(\left \langle \mathbb{N}, \mathbb{N}, \mathbb{N} \right \rangle\) is a triple where each component is the set of natural numbers.
  • \(\left \langle \mathbb{N}, \left \{ 3,7, \left \{ 112 \right \} \right \}, +, - \right \rangle\) is a \(4\)-tuple that consists of the set of natural numbers, the set \(\left \{ 3,7, \left \{ 112 \right \} \right \}\), and the operations of addition and subtraction.
  • \(\left \langle a, \left \langle b, \left \langle \right \rangle, \left \langle c \right \rangle, \left \langle d,e \right \rangle, b \right \rangle, \left \{ 1,2,3, \left \langle \right \rangle \right \} \right \rangle\) is triple that consists of \(a\), the 5-tuple \(\left \langle b, \left \langle , \right \rangle \left \langle c \right \rangle, \left \langle d,e \right \rangle, b \right \rangle\), and the set \(\left \{ 1,2,3, \left \langle \right \rangle \right \}\)

Does the concatenation of \(\left \langle a,b \right \rangle\) and \(\left \langle c \right \rangle\) yield the same result as the concatenation of \(\left \langle a,b \right \rangle\) and \(\left \langle \left \langle c \right \rangle \right \rangle\)? Justify your answer!

Recap

Two tuples \(u\) and \(v\) are identical iff all of the following hold:

  1. \(\left | u \right | = \left | v \right |\), and
  2. for all \(0 < i \leq \left | u \right |\), \(\pi_i(u) = \pi_i(v)\).
unordered idempotent can only contain symbols
sets Y Y N
multisets Y N N
tuples N N N
strings N N Y