1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Laico
    Jun 3, 2019 at 11:17
  • $\begingroup$ 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.) $\endgroup$ Jun 3, 2019 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .