A permutation metatheoremThis is one of a series of draft papers on set theory that I did in the late 1960's. None were ever published. This one covers a small hole in Gödel's axiomatization of abstract set theory. by Richard Harter Boston Massachusetts January 31, 1967
In Gödel's system of abstract set theory [1] propositional
functions are represented by classes of ordered n-tuple. One of the first
things shown in the development is a general existence theorem to the effect
that every primitive propositional function has a representation; i.e if
α(x_{1},...,x_{n}) is a primitive propositional function in which
∈ is the only primitive predicate, then
It is clear from the way that the proof is carried out that it could be extended to a more general representation theorem. This theorem says that if α is a propositional function such that the only primitive predicates in α are predicates that have representations and that are one or two place predicates, then α has a representation. The restriction that the predicates be one or two place cannot be removed; the permutation axioms that Gödel gives (axioms 1-3 below) are not strong enough to fulfill the third requirement for m place predicates when m is greater than 2. This paper shows that a single axiom may be added that is equivalent to a general permutation metatheorem that does not have this restriction. (But see below What is proved.)
The result we shall prove is independent of everything in Gödel's axiomization
except the recursive definiton of ordered n-tuples and the axioms given below. In particular
it is independent of what definition of the ordered pair [x,y] is used, provided that it
is one that meets the usual requirements. We will assume that ordered n-tuples are defined
recursively by:
From definition (1) it can easily be shown by induction that We shall assume the following four axioms:
Theorem: If π is any permutation on n letters then
Proof: The proof is by complete induction on n. The cases n=2 and n=3 follow immediately from
axioms 1-3. The general case depends on the fact that an ordered n-tuple is also an
ordered pair, triple, etc. Hence, if x is a class of ordered n-tuples and A is a theorem
about classes of ordered pairs then A applies to x considered as a class of ordered pairs.
For example, it follows from axiom 1 and (2) that If n=4 there are 24 permutations. It can be shown by a direct enumeration that applying (2) and axioms 1-3 to a class x of ordered quadruples yields 40 classes, (see below for a listing) of which eight are classes of ordered quadruples corresponding to the eight permutations of the subscripts for which the first two subscripts are 1 and 2 (in either order) or are 3 and 4 (in either order), these being the only classes of ordered 4-tuples produced by applying (2) and axioms 1-3. Adding axiom 4 permits us change which two subscripts are first and hence provides for the remaining 16 permutations. Hence axiom 4 is necessary for the theorem. To prove the general case suppose that the theorem is true for all m less then n where n is greater than 4. Depending on how the permutation π action on the last two letters we can classify it as being one of three cases: Case a: π(n-1),π(n) = (n-1),n
By the inductive hypothesis the theorem holds for n-1. Hence , closing brackets around
the last two elements, there is a set y_{1} such that Case b: π(n-1)=i, π(n)=j, i,j ≠ (n-1),n In this case we may close brackets around the last two elements and form the set y_{1} with elements x_{i} and x_{j} permuted to the right. We can then close brackets around them and form the set y_{2} with the element [x_{n-1},x_{n}] back at the right. We can then open the brackets around [x_{n-1},x_{n}], permute all elements to the desired positions and finally open the brackets around [x_{i} and x_{j}] to get y. Case c: Precisely one of π(n-1), π(n) is a member of {n-1,n} Let i be the integer such that i is either π(n-1)or π(n) and is neither n-1 nor n. Since is n is greater than 4 there are two distinct integers j and k such that j,k ≠ i,n-1,n. We may then close brackets on x_{n-1} and x_{n} and then get a set y_{1} that has x_{j} and x_{k} permuted to the right. We may then close brackets on them and get a set y_{3} that has [x_{n-1},x_{n}] on the right. We may then open brackets and get a set y_{4} that has x_{π(n-1)} and x_{π(n)} on the right. We may then close brackets on them and get as set y_{5} with [x_{j},x_{k}] on the right. Finally we may open brackets and permute all elements to the desired position to get the set y. Q.E.D Gödel, K: "The consistency of the Continuum Hypothesis," Annals of Matheamtics Studies, No. #, Princeton University Press, Princeton, N.J., 1940
Corrections, addenda, and commentsAll that this paper actually proves is the permutation metatheorem. The claim is made that (a) without axiom 4 primitive propositional functions that contain a primitive predicate with more than two places are not guaranteed a representation, and (b) with axiom 4 they are. The claim relies on Gödel's construction. This would be all right if only sufficient detail were given to outline the argument. As it is, the argument for the broader claim is too vague. The original paper did not list the 40 classes; the predicates for them are listed in the table below: [x_{1}[x_{2}[x_{3}x_{4}]]] [x_{3}[x_{4}[x_{1}x_{2}]]] [x_{4}[x_{3}[x_{2}x_{1}]]] [x_{2}[x_{1}[x_{4}x_{3}]]] [x_{2}[x_{1}[x_{3}x_{4}]]] [x_{4}[x_{3}[x_{1}x_{2}]]] [x_{3}[x_{4}[x_{2}x_{1}]]] [x_{1}[x_{2}[x_{4}x_{3}]]] [x_{1}[[x_{3}x_{4}]x_{2}]] [x_{3}[[x_{1}x_{2}]x_{4}]] [x_{4}[[x_{2}x_{1}]x_{3}]] [x_{2}[[x_{4}x_{3}]x_{1}]] [x_{2}[[x_{3}x_{4}]x_{1}]] [x_{4}[[x_{1}x_{2}]x_{3}]] [x_{3}[[x_{2}x_{1}]x_{4}]] [x_{1}[[x_{4}x_{3}]x_{2}]] [[x_{3}x_{4}][x_{1}x_{2}]] [[x_{1}x_{2}][x_{3}x_{4}]] [[x_{2}x_{1}][x_{4}x_{3}]] [[x_{4}x_{3}][x_{2}x_{1}]] [[x_{3}x_{4}][x_{2}x_{1}]] [[x_{1}x_{2}][x_{4}x_{3}]] [[x_{2}x_{1}][x_{3}x_{4}]] [[x_{3}x_{4}][x_{1}x_{2}]] [[x_{2}[x_{3}x_{4}]]x_{1}] [[x_{4}[x_{1}x_{2}]]x_{3}] [[x_{3}[x_{2}x_{1}]]x_{4}] [[x_{1}[x_{4}x_{3}]]x_{2}] [[[x_{3}x_{4}]x_{2}]x_{1}] [[[x_{1}x_{2}]x_{4}]x_{3}] [[[x_{2}x_{1}]x_{3}]x_{4}] [[[x_{4}x_{3}]x_{1}]x_{2}] [[[x_{3}x_{4}]x_{1}]x_{2}] [[[x_{1}x_{2}]x_{3}]x_{4}] [[[x_{2}x_{1}]x_{4}]x_{3}] [x_{1}[[x_{4}x_{3}]x_{2}]] [[x_{1}[x_{3}x_{4}]]x_{2}] [[x_{3}[x_{1}x_{2}]]x_{4}] [[x_{4}[x_{2}x_{1}]]x_{3}] [[x_{2}[x_{4}x_{3}]]x_{1}]3. Miscellaneous comments. Although the paper is framed in terms of a particular axiomatic set theory the theorem proved can be considered as a theorem in graph theory. As defined an ordered n-tuple is a binary tree that forms a right-handed vine, e.g. o--o--o...o--x_{n} | | | | x_{1} x_{2} x_{3} x_{n-1}The four axioms correspond to four operations than one can perform on a binary tree. Using all four a vine can be sorted; it cannot be sorted using only the first three. The result has no particular importance in the context of Gödel's set/class theory in which the only primitive predicate is ∈. However it is of interest in theories that have a generality of primitive predicates. This page was last updated August 1, 2006. |