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

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, 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.

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.

• Just to clarify for exercise 3.5.7, you are defining the set $A_i$ as the set of elements which are the $(i+1)$-st coordinate for some $n$-tuple in $R$?. Also, just after the quantifier, shouldn’t there be an $x_i$? It goes $x_{i-1}$ to $x_{i+1}$. I’m pretty sure it is a typo just want to make sure! Jun 3, 2019 at 11:17
• That is how I'm defining $A_i$. And the omission of $x_i$ from the quantifiers is deliberate. $A_i$ is the set of elements for which, when you "fill in the blank" for the other coordinates (not including $x_i$), get you an element of $R$. (Upvotes as well as acceptances for answers you find useful are always appreciated.) Jun 3, 2019 at 16:41