0
$\begingroup$

I am trying to decipher page 68 of Hermes' book on computability theory. One paragraph I am having trouble with is

Let $Q$ be an n-ary predicate ($n \geq 2$). Let $1 \leq i < k \leq n$. Then $P$ [a predicate] is called the $(i, k)$ identification of $Q$, if $P$ is $(n-1)$-ary and if for all $x_1, \dots, x_{k-1}, x_{k+1}, \dots, x_n$, $P x_1 \dots x_{k-1} x_{k+1} \dots x_n \iff Q x_1 \dots x_{k-1} x_i x_{k+1} \dots x_n.$

What does "identification" mean intuitively and what does it correspond to in more concrete terms?

There's also another paragraph I don't understand,

Let $Q$ be an n-ary predicate. Let $1 \leq i \leq n$. The (n-1)-ary predicate $P$ is called the ith generalization of $Q$, if for all $x_1 \dots x_{i-1}, x_{i+1}, \dots, x_n$, $P x_1 \dots x_{i-1} x_{i+1} \dots x_n \iff \wedge_{x_i} Q x_1 \dots x_n.$

On the right hand side, what is different between different terms of the conjunction? Isn't $Q x_1 \dots x_n$ the same no matter what the value of $x_i$ is? Also, what does "generalization" mean in intuitive terms?

Thanks :)

1 Answers 1

1

For the first, here are three simple cases. Suppose we define $P(x) \Leftrightarrow Q(x, x)$ or $P'(x,y,z) \Leftrightarrow Q'(x,y,z,y)$ or $P''(x,y,z,w) \Leftrightarrow Q''(x,y,z,x,w)$ So in each case we get an $n-1$-place predicate from an $n$-place predicate by filling two slots in the $n$ place predicate in the same way. Hermes is just giving a general description of this operation.

For the second, that isn't a conjunction in Hermes but a universal quantification. In more familiar notation, examples would be where we define $P(x) \Leftrightarrow \forall yQ(x, y)$ or $P(x, y) \Leftrightarrow \forall zQ(z, x, y)$ getting an $n-1$-place predicate by quantificationally binding one place in an $n$-predicate.

[It is nice to see a mention of Hermes's old book: it taught me a lot when I read it as a student when the English translation was newly published -- so I could reach for it still on my shelves!]

  • 0
    Hey, thanks for your help!2013-01-01