Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :)

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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!]

share|improve this answer
    
Hey, thanks for your help! –  badatmath Jan 1 '13 at 19:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.