Pairs

  • sets (basic notation)

Pairs are the simplest instance of tuples. We start with pairs because they are a very common use of tuples and still convey the central intuitions very clearly.

Notation and basic concepts

A pair consists of exactly two elements. We write \(\left \langle a, b \right \rangle\) to denote the pair that contains \(a\) and \(b\). We also call \(a\) the first component of the pair \(\left \langle a, b \right \rangle\), and \(b\) its second component. Crucially, the order of components matters.

Even though \(\left \{ 1,5 \right \} = \left \{ 5,1 \right \}\), the pair \(\left \langle 1,5 \right \rangle\) is distinct from the pair \(\left \langle 5,1 \right \rangle\).

In formal terms, \(\left \langle a,b \right \rangle = \left \langle c,d \right \rangle\) iff \(a = c\) and \(b = d\).

We have \(\left \langle 1,5 \right \rangle = \left \langle 1,5 \right \rangle\) because \(1 = 1\) and \(5 = 5\). This holds even if we write the pairs differently. For example, let \(f(x) = x - 1\). Then \(\left \langle 1,5 \right \rangle = \left \langle f(2), f(6) \right \rangle\) because \(1 = f(2)\) and \(5 = f(6)\).

It is also possible for pairs to contain the same object twice.

Continuing the previous example, the pair \(\left \langle 1, f(2) \right \rangle\) is identical to \(\left \langle 1, 1 \right \rangle\). This is a perfectly valid pair.

Pairs may contain complex objects, including other pairs.

The following is a pair: \(\left \langle \left \{ a \right \}, \left \langle a, \left \{ a \right \} \right \rangle \right \rangle\). Its two components are

  1. the set containing \(a\), and
  2. a pair that consists of
    1. \(a\) and
    2. the set containing \(a\)

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.

For each one of the following, say whether it is a pair.

  • \(\left \langle 3, a \right \rangle\)
  • \(\left \langle a, b \right \rangle\)
  • \(\left \langle a, b \right \rangle\) if \(a = b\)
  • \(\left \langle \mathit{pair} \right \rangle\)
  • \(\left \langle \left \langle 3, a \right \rangle, \left \langle a, b \right \rangle \right \rangle\) if \(a = b\)
  • \(\left \langle 3, a, a, b \right \rangle\)
  • \(\left \langle 3, \left \{ a, a \right \}, b \right \rangle\)
  • \(\left \langle \left \langle a,b \right \rangle \right \rangle\)
  • \(\left \langle \left \{ \left \langle a,b \right \rangle, \left \langle c,d \right \rangle \right \} \right \rangle\)
  • \(\left \langle \left \{ a \right \}, \left \{ a, a \right \} \right \rangle\)
  • \(\left \langle a, \left \langle b, \left \langle c, \left \langle d, \left \langle e, \left \langle f,g \right \rangle \right \rangle \right \rangle \right \rangle \right \rangle \right \rangle\)
  • \(\left \langle 1, \mathbb{N} \right \rangle\), where \(\mathbb{N}\) is the set of natural numbers (0, 1, 2, 3, …)

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

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

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

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

Sets VS pairs

Just like sets, pairs are containers that can contain objects of arbitrary complexity. But unlike sets, pairs care about order and the same object can be contained in a pair more than once. Also, every pair has exactly two elements.

Usually it is clear whether one should use sets or pairs. If order is crucial, a set won’t cut it. It it crucial to know whether we have an object once or twice, a set won’t cut it. But it is common to use pairs for mathematical convenience even in some cases where sets would suffice.

The unit on the mathematics of tiers defined an \(n\)-grammar with tiers as a set of tier-annotated \(n\)-grams, which is a pair \(\left \langle g, T \right \rangle\) such that \(g\) is an \(n\)-gram and \(T\) is a tier alphabet. A concrete example of this would be \(\left \langle \mathit{aa}, \left \{ a,b \right \} \right \rangle\), i.e. the bigram \(\mathit{aa}\) over the tier that only contains \(a\)s and \(b\)s.

Strictly speaking we do not need to use a pair here, a set would have been sufficient. That is because the two components of the pair are of different types: one is an \(n\)-gram, the other a set of symbols. If we write, say, \(\left \{ \left \{ a,b \right \}, \mathit{aa} \right \}\), it does not matter that there is no linear order, we can still infer right away that \(\mathit{aa}\) must be the bigram and \(\left \{ a,b \right \}\) the tier alphabet. And we don’t have to worry about duplicates either since we always have exactly one \(n\)-gram and one tier alphabet.

Nonetheless it is nicer to use pairs instead of sets in this case. Consider the tier-annotated \(n\)-gram \(\left \langle u, v \right \rangle\). Even though we used the arbitrary variables \(u\) and \(v\) here, you can still readily infer that \(u\) is the \(n\)-gram and \(v\) the tier alphabet. Sure, we could have chosen more helpful variable names, but we didn’t have to. On the other hand, \(\left \{ u, v \right \}\) would have been ambiguous as to which element is the \(n\)-gram and which is the tier alphabet. Crucially, this ambiguity would remain even if we use more meaningful variables names, as in \(\left \{ g, T \right \}\). You may well have intended for \(g\) to be the \(n\)-gram and for \(T\) to be the tier alphabet, but the math does not actually enforce that. Remember that mathematicians do not like to make extra assumptions: unless you explicitly say that \(g\) is the \(n\)-gram and \(T\) the tier alphabet, we also have to consider the interpretation where \(T\) is the tier alphabet and \(g\) is the \(n\)-gram. This will quickly become problematic. It is much nicer and explicit to use pairs instead because no matter whether you write \(\left \langle g, T \right \rangle\), \(\left \langle u, v \right \rangle\), it will always be the case that the first is the \(n\)-gram and the second the tier alphabet. No ambiguity, no unintended side effects.

Continuing the example above, consider the tier-annotated \(n\)-gram \(\left \langle \mathit{tier alphabet}, \mathit{ngram} \right \rangle\). Which one is the \(n\)-gram, and which one is the tier alphabet?

Pairs as sets

The Kuratowski definition defines pairs as a particular kind of set: the pair \(\left \langle a,b \right \rangle\) is equivalent to the set \(\left \{ \left \{ a \right \}, \left \{ a,b \right \} \right \}\). This definition is quite frequent in the linguistic literature, but the way it has been used is problematic for several reasons. If you are interested in this definition and why linguists should be careful in how they invoke it, check out the dedicated unit at the end of this chapter.

Recap