What is a k-ary relation?

Question

Im reading the book Theory of Computation by Michael Sipser and I came across this part that's giving me some trouble.

"A property whose domain is a set of k-tuples A × · · · × A is called a relation, a k-ary relation, or a k-ary relation on A"

Does this mean that doing the Cartesian product on A itself k times, gives us k-tuples?

And another part that I don't understand at all is the last part of this paragraph:

"When writing an expression involving a binary rela- tion, we customarily use infix notation. For example, “less than” is a relation usually written with the infix operation symbol <. “Equality”, written with the = symbol, is another familiar relation. If R is a binary relation, the statement aRb means that aRb = TRUE. Similarly, if R is a k-ary relation, the statement R(a1,...,ak) means that R(a1,...,ak) = TRUE."

What does aRb even mean? and why are they saying aRb = TRUE? I'm so lost.

Answer 1

It seems you're having trouble understanding what a relation is. Let's take a look at a simple case in $\mathbb{R}$. What does the statement $x<y$ mean? Well, the symbol $"<"$ is a binary relation, where two numbers are related if and only if the first is less than the other. Thus, when we state $x<y$, it tells us that the statement "$x$ is less than $y$" is true.

But notice that $"<"$ is a bi-nary relation, meaning it only takes in two inputs. We can make a more general type of relation, which is what your "$k$-ary" relation is. If a relation relates $k$ elements of a set $A$, then its domain is $A^k=A\times A\times \dots\times A$ ($k$ times). For instance, suppose we make a relation $\sigma\subset A^k $, where all $k$ elements of $A$ are related by $\sigma$ if and only if all of them are equivalent. Then what $k$-tuples would $\sigma$ contain? All of the elements would look like this: $$\underbrace{(a_1,a_1,a_1,\dots,a_1)}_{\text{$k$ times}}\in \sigma$$ And to state that they are related, we might say something like: $\sigma(a_1,a_1,\dots,a_1)$.

Hope this all makes sense.

Answer 2

Yes. A $1$-ary relation is a set of $1$-tuples from $A$, so a subset of the $1$-fold cartesian product on $A$, which is just $A$, a $2$-ary relation is a set of $2$-tuples from $A$, so a subset of the $2$-fold cartesian product of $A$, which is $A \times A$, ..., and a $k$-ary relation a set of $k$-tuples from $\underbrace{A \times A \times ... A}_{k \text{ times}}$.

$aRb$ is precisely what is meant by the infix notation, so $aRb$ means the same as $R(a,b)$. For example, if the relation $R$ is $\leq$, then instead of wirting $\leq(a,b)$ (= prefix notation) we can write $a \leq b$ (= infix notation), beacuse that makes it just easier to read.
$R(a,b) = TRUE$ means that it is true that the relation $R$ holds between $a$ and $b$. For example, $\leq(a,b) = TRUE$ (or $a\leq b = TRUE$) means that it is true that $a$ is smaller than or equal to $b$ - of course it could also false. The bold faced part just says that if the relation does hold, then instead of writing $R(a,b) = TRUE$ (or $aRb =TRUE$) we can just write $R(a,b)$ for short, so instead of writing $R(a,b) = TRUE$ (or $a \leq b = TRUE$) we simply write $a \leq b$.