Tuples

I defined the ordered pair as

\[\langle x, y\rangle:=\{\{x\},\{x,y\}\}.\]

I might've used the notation \((x,y)\) in some places by accident, but let's be particularly careful of our notation in this post. Having defined an ordered pair \(\langle x,y\rangle\), we might wonder what an ordered triple \(\langle x,y,z \rangle\) would be. One way to approach this is to define \(n\)-tuple by recursion on \(n\). So we say:

\[\langle x_0 \rangle := x_0,\]

\[\langle x_0,\dots, x_n\rangle := \langle\langle x_0,\dots,x_{n-1}\rangle, x_n\rangle.\]

In this definition, we know what is a 1-tuple and we can easily see that a 2-tuple exactly corresponds to an ordered pair. From there, we can see that \(\langle x,y,z \rangle\) is actually \(\langle\langle x,y \rangle, z\rangle\), and so on. However, there is a subtle issue here and it has to do with the rigor that I'm suppressing from my posts. Very briefly, our definition would here go something like: "given sets \(x_0,\dots, x_{n-1}\), we define the \(n\)-tuple \(\langle x_0,\dots, x_{n-1}\rangle\) as ..." The problem, though, is that by just listing sets \(x_0,\dots, x_{n-1}\) at the beginning of the sentence, we've already implicitly used some notion of an \(n\)-tuple that we're trying to define! So if we're going to make this work properly, we have to define an \(n\)-tuple without listing its elements.

To know what is an \(n\)-tuple, we just need to say what is the set at the place 0, what is the set at the place 1, and so on, what is the set at the place \(n-1\). Well, this just a function with domain

\[\{0,\dots, n-1\}=n.\]

In fact, this is all there is to it: we define an \(n\)-tuple as a function with domain \(n\). If \(s\) is an \(n\)-tuple, we might write

\[s=(s(0),s(1),\dots,s(n-1))\]

to show which elements are being listed by \(s\). 

Note that I used here parentheses instead of angled brackets. This is not a typo. Let's say that \(n=2\) and \(s\) is a 2-tuple, with \(x:=s(0)\) and \(y:=s(1)\). We have that

\[(x,y)=s=\{\langle 0, x\rangle, \langle 1,y\rangle\}=\{\{\{0\},\{0,x\}\},\{\{1\},\{1,y\}\}\},\]

while 

\[\langle x,y \rangle = \{\{x\},\{x,y\}\}.\]

This is why I commented about my notation in the beginning: a 2-tuple is formally different from an ordered pair! We need the notion of an ordered pair to define functions, which we then use to define tuples. We can then work only with tuples, since they help avoid the issue mentioned above. There is no much danger in mentally identifying ordered pairs with 2-tuples, as long as we are aware of this subtle difference.

An \(n\)-tuple of elements of \(X\) is just an \(n\)-tuple whose coordinates (things listed) belong to \(X\). In other words, that's a function \(s:n\to X\). The class of all \(n\)-tuples of elements of \(X\) is denoted by

\[X^n:=\{ s : s:n\to X\}.\]

It turns out that this is in fact a set. How do we show this? By induction on \(n\). In the case \(n=0=\emptyset\), we have that

\[X^n=X^0=\{s : s: \emptyset\to X\}=\{\emptyset\},\]

which is a set. What we used here is that the only function from \(\emptyset\) to \(X\) is the empty set. Why is that? Well, because such a function is a subset of

\[X\times\emptyset=\{\langle x, y \rangle : x\in X, y\in\emptyset\}=\emptyset\]

(since there are no \(y\)'s such that \(y\in\emptyset\)) and the only subset of the empty set is the empty set.

This was the base of the induction. For the inductive step, let's assume that \(X^n\) is a set and let us show that \(X^{n+1}\) is a set. Since \(X^n\) is a set, so is

\[X^n\times X=\{\langle s,x \rangle : s\in X^n, x\in X\}.\]

By replacing \(\langle s,x \rangle\) with \(s\cup\{\langle n,x \rangle\}\), we get that

\[\{s\cup\{\langle n,x \rangle\} : s\in X^n, x\in X\}=X^{n+1}\]

is a set (we are using here Axiom of Replacement). The point here is that if \(s:n\to X\) and if \(s':=s\cup\{\langle n,x \rangle\}\), then \(s'\) is a function from \(n+1=n\cup\{n\}\) to \(X\) defined by

\[s'(i)=\begin{cases} s(i), & i<n\\ x, & i=n. \end{cases}\]

In other words, \(s'=(s(0),s(1),\dots,s(n-1),x)\).


If \(s=(A_0,\dots,A_{n-1})\) is an \(n\)-tuple (of sets), we can define the product

\[\prod_{i<n}A_i\]

of the listed sets as the set of all \(n\)-tuples \(s\) such that for all \(i<n\), we have that \(s(i)\in A_i\). The point is that the \(i^\mathrm{th}\) coordinate of \(s\) belongs to \(A_i\). This class is a set because it is contained in a set: it is contained in

\[\left(\bigcup_{i<n}A_i\right)^n.\]

In the case \(n=2\), we have that

\[\prod_{i<2}A_i=\{(a_0,a_1) : a_0\in A_0, a_1\in A_1\},\]

which, again, is not literally the same as

\[A_0\times A_1=\{\langle a_0,a_1 \rangle: a_0\in A_0, a_1\in A_1\},\]

but we might use sometimes the notation \(A_0\times A_1\) when we really mean \(\prod_{i<2}A_i\). When we have that \(A_0=A_1=X\), we get that

\[\prod_{i<2}X=\{(a_0,a_1) : a_0, a_1\in X\}=X^2.\]


Now that we understand \(n\)-tuples, I can finally tell you what are \(n\)-ary relations. Of course, they are just sets of \(n\)-tuples! An \(n\)-ary relation on a set \(X\) is  just a subset of \(X^n\). A bit of a formal point is in order. Master defined binary relations as sets of ordered pairs. As I pointed it out, this is not exactly the same as the set of two-tuples, so for the sake of precision and coherence, by a binary relation we will mean from now on "a set of two-tuples". A similar issue arises with unary relations: before, a unary relation on a set \(X\) was a subset of \(X\) itself, whereas this new definition says that it's a subset of the set

\[\{(a) : a\in X\}.\]

This is different because \((a) = \{\langle 0,a \rangle\}\not=a\). However, this "fine print" is not really important for doing math, so we shall push it under the rug.

There is also a notion of an \(n\)-ary function. We also call them \(n\)-ary operations. An \(n\)-ary operation on set \(X\) is just a function

\[f:X^n\longrightarrow X.\]

Naturally, a unary operation \(f:X^1\to X\) is identified with the function \(f':X\to X\) defined by \(f'(x):=f((x))\) for \(x\in X\). We won't make a distinction between \(f\) and \(f'\) from now on. In general, if \(f\) is an \(n\)-ary operation on \(X\) and if \((a_0,\dots, a_{n-1})\in X^n\), instead of

\[ f((a_0,\dots,a_{n-1})),\]

we write 

\[f(a_0,\dots,a_{n-1}).\]


There is a certain correspondence between operations and relations. Let \(f\) be an \(n\)-ary operation on \(X\). For the sake of simplicity, let us assume that \(n=2\). We then have that

\[f=\{((x,y),f(x,y)) : x,y\in X\}\subseteq X^2\times X.\]

This set is just a "formalism away" from the set 

\[R_f:=\{(x,y,f(x,y)) : x,y\in X\}=\{(x,y,z)\in X^3 : f(x,y)=z\}\subseteq X^3.\]

What I'm getting at is that \(f\) and \(R_f\) are essentially the same object. However, the operation \(f\) is binary, whereas the relation \(R_f\) is ternary! In general, an \(n\)-ary operation on \(X\) gives rise to an \((n+1)\)-ary relation on \(X\).

One might be tempted to reverse the above correspondence. So, starting from a ternary relation \(R\) on \(X\), they might try defining

\[f_R:=\{((x,y), z) : (x,y,z)\in X^3\}\subseteq X^2\times X.\]

This is binary relation between \(X^2\) and \(X\), but in order for it to be a binary operation on \(X\), it would need to satisfy \(f_R:X^2\to X\). Remember, this requires that for all \((x,y)\in X^2\), there exists a unique \(z\in X\) such that \(((x,y),z)\in f_R\), or, which is the same, \((x,y,z)\in R\). However, there is no reason in general for this to be true. In fact, for a given two-tuple \((x,y)\in X^2\),

  1. there might not be any \(z\in X\) such that \((x,y,z)\in R\),
  2. there might be two different \(z_0,z_1\in X\) such that \((x,y,z_0)\in R\) and \((x,y,z_1)\in R\).
Here is an example of both of these things occurring. Say \(X=2=\{0,1\}\) and say
\[R=(2\times 1)\times 2.\]
Now for each \((x,y)\in X^2\), one of the above points fails. I'll let you convince yourself of this. 😀

Comments

Post a Comment

Popular posts from this blog

Axiom of Powerset

So far, I listed Axioms of the Empty Set, Extensionality, Pairing, Union, Comprehension, Induction, Replacement, and Infinity. This is not the complete list making up the Mathematical Theory of Everything, we have to add two more axioms to the list. These axioms are called Powerset  and Choice . Axiom of Powerset is relatively easy to state: for every set \(x\) in the universe, there exists a set whose elements are exactly all subsets of \(x\) . As usual, Extensionality implies that such object must be unique and we denote it by \(P(x)\). So, the defining characteristic of the set \(P(x)\) is that a given set \(y\) belongs to \(P(x)\) if and only if \(y\) is a subset of \(x\). The other axioms don't imply existence of the powerset. More precise explanation of this will have to wait, but for now, we can kind of see that the set \(P(x)\) is "larger" than \(x\). If \(a\) is an element of \(x\), than \(\{a\}\) is a subset of \(x\), so an element of \(P(x)\). But there are oth...
Read more

Wellorderings

I've already told you what is an ordering, but let me give a quick reminder. A ( strict) ordering  on some set \(X\) is a a binary relation, usually denoted by some variation on the symbol \(<\), which is  irreflexive,  that is for all \(x\in X\), it is not  the case that \(x<x\), transitive, that is for all \(x,y,z\in X\), if \(x<y\) and \(y<z\), then \(x<z\). One very important example is the standard ordering on natural numbers. In that case, we have that \(X=\omega\) and \(<=\in\). To understand the second thing, recall that in Set Theory, natural numbers are coded as \(0=\emptyset\), \(1=\{0\}\), \(2=\{0,1\}\), \(3=\{0,1,2\}\), and so on. Hence, for example, \(1<3\) because \[1\in \{0,1,2\}=3.\] In addition to the irreflexivity and transitivity, this relation satisfies some other important properties. One of them is being total, that is for all \(x,y\in X\), one of the options is true: \(x<y\) or \(x=y\) or \(x>y\). The orderings which...
Read more

Relations

I'll write this post in form of a dialogue between Master (M) and Apprentice (A). A: Say, O Noble Teacher, what are those "relations" that mathematicians always talk about? M: Why, my dear Apprentice, you have already seen one kind of relations! A: How so, O Exalted One? M: Well, \(\in\) is a relation and \(V\) is also a relation! These are class-sized relations. A: Oh, I see! But how does their "relation-ness" manifest? M: In the case of \(\in\), it divides pairs of sets \((x,y)\) into those for which \(x\) belongs to \(y\) and into those for which \(x\) does not belong to \(y\). So, it tells us whether the statement ''\(x\in y\)" is true or false for any particular pair of sets \((x,y)\). In this sense, they are no different from predicates or classes. Class-sized relations are the same thing as predicates. A: I seem to understand now! \(\in\) is a binary predicate, so a class-sized relation. \(V\) is a class, which is the same thing as a unary pr...
Read more