Introduction to Set Theory, Hrbacek and Jech exercises 3.5.7 and 3.5.8

Question

I am working on the exercises in chapter 3, section 5, of Introduction to Set Theory by Hrbacek and Jech. I wanted to check and see if my proofs of the following exercises are valid. I will list the problem statement, the relevant definitions, and then my proof for each.

Definition: Define an $n$-tuple as a sequence of length $n$ where for every $0\leq i<n$, we denote $a_i$ as the $(i+1)$st coordinate.

Definition: $A^n$ is the set of all sequences of length $n$ of elements of $A$.

Definition: An $n$-ary relation, R, in $A$ is a subset of $A^n$. We write $R(a_0,a_1,\ldots,a_{n-1})$ instead of $\langle a_0,a_1,\ldots,a_{n-1}\rangle\in R$.

Defintion: Define an $n$-ary operation $F$ on $A$ as a function on a subset of $A^n$ to $A$. We denote it as $F(a_0,a_1,\ldots,a_{n-1})$ instead of as $F(\langle a_0,a_1,\ldots,a_{n-1}\rangle)$.

Exercise 3.5.7: Let $R$ be a set whose elements are $n$-tuples. It follows that $R$ is an $n$-ary relation in $A$ for some set $A$.

Proof: We will denote an arbitrary element of $R$ by $a_i$ where $i\in\mathbb{N}$. It follows that if $a_i\in R$, then $a_i$ is a sequence of length $n$ of elements of arbitrary set which we will denote respectively as $A_i$. Thus, if $a_i\in R$, it follows that $a_i\in\bigcup_{i\in\mathbb{N}} A_i^n$ and, subsequently, that $R\subseteq\bigcup_{i\in\mathbb{N}} A_i^n$. Finally, since $\bigcup_{i\in\mathbb{N}} A_i^n\subseteq (\bigcup_{i\in\mathbb{N}} A_i)^n$, we have $R\subseteq(\bigcup_{i\in\mathbb{N}} A_i)^n$ so $R$ is an $n$-ary relation of elements of $\bigcup_{i\in\mathbb{N}} A_i$.

Exercise 3.5.8: For any $n$-ary operation $F$ on $A$, there is a unique $(n+1)$-ary relation $R$ in $A$ such that $F(x_0,x_1,\ldots,x_{n-1})=x_n$ if and only if $R(x_0,x_1,\ldots,x_n)$ holds.

Proof: Consider the set $R=\{x\cup y\ |\ x\in dom\ F\mbox{ and }y=\{(n,F(x))\}\}$. It follows that $x\cup y$ is a sequence of length $n+1$ of elements of $A$ so $x\cup y\in A^{n+1}$ and $a_n=F(a_0,a_1,\ldots,a_n)$. Therefore, it follows that $R\subseteq A^{n+1}$ so $R$ is an $(n+1)$-ary relation in $A$, and $F(x_0,x_1,\ldots,x_{n-1})=x_n$ if and only if $R(x_0,x_1,\ldots,x_n)$ holds.

In the last proof, if the reasoning is valid, is there a better way to denote the formation of a sequence of length $n+1$ from a sequence of length $n$? Any other pointers for clearer notation and stronger proof writing would be appreciated as well.

Answer 1

You have the right idea for $3.5.7$ but either your notation or your reasoning isn't quite right. I wouldn't use $a_i$ to denote an arbitrary element of $R$ because elements of $R$ are $n$-tuples and we've been using $a_i$ to denote a component of such an $n$-tuple. Here's how I'd write the proof:

For each $0 \leq i \leq n-1$, define:

$$A_i=\{a_i|~\exists x_0, x_1, \ldots x_{i-1}, x_{i+1}, \ldots x_{n-2}, x_{n-1}~(\langle x_0, x_1, \ldots x_{i-1}, a_i, x_{i+1}, \ldots x_{n-2}, x_{n-1} \rangle \in R) \}.$$

Define

$$A=\bigcup_{i=0}^{n-1} A_i.$$

Then $R \subseteq A^n$.

For $3.5.8$, clearly the relation defined by $\langle a_0, a_1, \ldots a_{n-1}, a_n \rangle \in R \iff F(a_0, a_1, \ldots a_{n-1})=a_n $ is an $n$-ary relation on $A$ that satisfies the required condition, so all that's left is to show that it's unique; in other words, that any other $n$-ary relation $S$ on $A$ that satisfies this condition is in fact equal to $R$.

But if $\langle a_0, a_1, \ldots a_{n-1}, a_n \rangle \in S$, then the $\Rightarrow$ direction of our implication on $S$ tells us $f(a_0, \ldots a_{n-1}) = a_n$, so $\langle a_0, a_1, \ldots a_{n-1}, a_n \rangle \in R$ by the definition of $R$, and $S \subseteq R$.

Conversely, if $\langle a_0, a_1, \ldots a_{n-1}, a_n \rangle \in R,$ then by the definition of $R, f(a_0, \ldots a_{n-1}) = a_n$ and the $\Leftarrow$ implication of our condition on $S$ then tells us $\langle a_0, a_1, \ldots a_{n-1}, a_n \rangle \in S,$ so $R \subseteq S$, equality follows, and we have proved $R$ is unique.