Tuples

I defined the ordered pair as

$$⟨x,y⟩:=\{\{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 $⟨x,y⟩$, we might wonder what an ordered triple $⟨x,y,z⟩$ would be. One way to approach this is to define $n$-tuple by recursion on $n$. So we say:

$$⟨x_0⟩:=x_0,$$

$$⟨x_0,\dots ,x_n⟩:=⟨⟨x_0,\dots ,x_{n-1}⟩,x_n⟩.$$

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 $⟨x,y,z⟩$ is actually $⟨⟨x,y⟩,z⟩$, 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 $⟨x_0,\dots ,x_{n-1}⟩$ 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=\{⟨0,x⟩,⟨1,y⟩\}=\{\{\{0\},\{0,x\}\},\{\{1\},\{1,y\}\}\},$$

while 

$$⟨x,y⟩=\{\{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=\mathrm{\varnothing }$, we have that

$$X^n=X^0=\{s:s:\mathrm{\varnothing }\to X\}=\{\mathrm{\varnothing }\},$$

which is a set. What we used here is that the only function from $\mathrm{\varnothing }$ to $X$ is the empty set. Why is that? Well, because such a function is a subset of

$$X\times \mathrm{\varnothing }=\{⟨x,y⟩:x\in X,y\in \mathrm{\varnothing }\}=\mathrm{\varnothing }$$

(since there are no $y$'s such that $y\in \mathrm{\varnothing }$) 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=\{⟨s,x⟩:s\in X^n,x\in X\}.$$

By replacing $⟨s,x⟩$ with $s\cup \{⟨n,x⟩\}$, we get that

$$\{s\cup \{⟨n,x⟩\}: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^{\prime }:=s\cup \{⟨n,x⟩\}$, then $s^{\prime }$ is a function from $n+1=n\cup \{n\}$ to $X$ defined by

$$s^{\prime }(i)=\{\begin{array}{ll}s(i),& i<n\\ x,& i=n.\end{array}$$

In other words, $s^{\prime }=(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=\{⟨a_0,a_1⟩: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)=\{⟨0,a⟩\}\ne 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⟶X.$$

Naturally, a unary operation $f:X^1\to X$ is identified with the function $f^{\prime }:X\to X$ defined by $f^{\prime }(x):=f((x))$ for $x\in X$. We won't make a distinction between $f$ and $f^{\prime }$ 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. 😀