# I don't understand P-Q system in GED

Up front some apologies since I am not a mathematician and English is not my native language so it might be that I am missing some basics here. If so please don't flame me but just point me to some place where I might read up on basics first.

I am currently trying to read the GEB book to get some better understanding of mathematics and formal systems and so far I have found it quite readable. Now I expected that my lack of mathematical knowledge and English language might stop me at some point and unfortunately it has when I came up to the PQ chapter of the book.

I hope it is ok if I quote the relevant chapter in the book:

The pq-System

The formal system of this Chapter is called the pq-system. It is not important to mathematicians or logicians-in fact, it is just a simple invention of mine. Its importance lies only in the fact that it provides an excellent example of many ideas that play a large role in this book. There are three distinct symbols of the pq-system:

p q -

The letters p, q, and the hyphen.

The pq-system has an infinite number of axioms. Since we can't write them all down, we have to have some other way of describing what they are. Actually, we want more than just a description of the axioms; we want a way to tell whether some given string is an axiom or not. A mere description of axioms might characterize them fully and yet weakly-which was the problem with the way theorems in the MIU-system were characterized. We don't want to have to struggle for an indeterminate-possibly infinite length of time, just to find out if some string is an axiom or not. Therefore, we will define axioms in such a way that there is an obvious decision procedure for axiomhood of a string composed of p's, q's, and hyphens.

DEFINITION: xp-qx is an axiom, whenever x is composed of hyphens only.

Note that 'x' must stand for the same string of hyphens in both occurrences For example, - -p-q---is an axiom. The literal expression xp-qx-' is not an axiom, of course (because 'x' does not belong to the pq-system); it is more like a mold in which all axioms are cast-and it is called an axiom schema. The pq-system has only one rule of production:

RULE: Suppose x, y, and z all stand for particular strings containing only hyphens. And suppose that x py qz is known to be a theorem. The 'xpy-qz-' is a theorem.

For example, take x to be'--', y to be'---', and z to be'-'. The rule tells us:

If --p---q- turns out to be a theorem, then so will --p----q--.

After that the author asks the reader if he can come up with the decision procedure. One paragraph later the author states:

The criterion for theoremhood is that the first two hyphen-groups should add up, in length, to the third hyphen-group.

Again, I am not a mathematician so if I am missing some basic knowledge to understand how author came up with this ... please tell me where I can find it. I just don't understand how he came up with that.

If i take the following axiom: -----p-q-- and apply the given rule, I come up with -----p--q---

AFAIK ----- + -- do not equal ---.

-
It seems the axioms should be xp-qx- and not xp-qx as in your displayed "DEFINITION". In the note immediately following the definition this is made clear, and also in the intent given by theormhood. We need x hyphens plus the one hyphen between p,q to equal the string x- having one more hyphen than x. –  coffeemath Jan 28 '13 at 16:38

The axioms then should be of the form $xp*qx*$ where both instances of x represent the same number of *'s. For example: $***p*q****$ is an axiom, saying that 3+1=4 (to get what an axiom or theorem is "saying", count the number of * before the p, add the number of * between the p and q, and that should equal the number of * after the q.

Your example (in * notation) of a proposed axiom is then $*****p*q**$. But this isn't an axiom because it has five * before the p and two * after the p.

Note that there's nothing wrong with the authors statement that "If $**p***q*$ turns out to be a theorem, etc" because in fact $**p***q*$ will not turn out to be a theorem. The author is just giving that as an example of applying the "rule" to get another theorem from one that already exists, and for $**p***q*$ that particular string will not turn out to be a theorem in the first place.

You can translate the rule :If $xpyqz$ is a theorem then $xpy*qz*$ is also a theorem, to mean that if x *'s plus y *' s equal z *' s, then also x *'s plus (y+1) *' s will equal (z+1) *' s.

At least that's how it looks like it goes.

-
Thank you. I was being blind and did not see that the axiom schema is xp-qx. I was looking at it and constantly seeing xp-qy. Duh, I feel stupid. Thank you for taking the time to write up an answer. –  dcarapic Jan 28 '13 at 20:56
Be sure to check, but as I note I think the axiom schema should be xp-qx- (note the extra - at the end), and not what you have in this comment (or in main display of "DEFINITION", which was xp-qx (without the extra - at the end). It may be that in GEB there was a typo in the statement of the "DEFINITION" but it definitely needs the extra - at the end to be the correct definition of the axiom schema, which you can see by the author's example after the DEFINITION. –  coffeemath Jan 28 '13 at 22:01
Thanks. I will check it. –  dcarapic Jan 29 '13 at 7:49
I have been trying to figure out what I was missing for half an hour then I understood xp-qx was missing a hyphen. We are probably reading the same pdf which seems to be a OCR judging by the typos (like MI' system` on IV). –  Rnhmjoj Mar 1 at 21:47