FOM: The ineffable name of 1
Andrian-Richard-David Mathias
Andrian-Richard-David.Mathias at univ-reunion.fr
Tue Nov 2 02:06:55 EST 1999
BOURBAKI REVISITED: the number 1 and ordered pairs.
[Abstract of a paper written under the
stimulus of the kind invitation of Professor Stig Andur Pedersen
to speak at a meeting devoted to Bourbaki held at Roskilde in October 1998.
It will appear, under the title "A term of length 4,523,659,424,929",
in the proceedings of a conference on Foundations of the Formal Sciences held
at the Humboldt Universitaet zu Berlin in May 1999.]
We examine Bourbaki's definition of the number 1
(as given in a footnote on page 55 of Bourbaki's Chapter III
of "La Th'eorie des Ensembles", first published
by Hermann of Paris in 1956; Chapters I and II appeared in 1954).
In that first edition, there is a symbol (a reverse letter C)
with the intention that (reverse C)xy mean the ordered pair
of x and y. Using the syntax of the first edition, we have
PROPOSITION Bourbaki's abbreviated structuralist definition of the number 1,
when fully expanded, comprises
4,523,659,424,929 symbols together with
1,179,618,517,981 disambiguatory links between certain of those symbols.
REMARKS 1. The explosion in length is caused by the definition of quantifiers
in terms of a Hilbertian epsilon-operator (which they call tau).
2. A curiosity of this syntax is that two trivially equivalent formulae might
have markedly different lengths. Thus if R has 2 occurrences
of x, 5 of y and 3 of z, and is of length 50, the
formula (exists x)(exists y)R will be of length 3900, with
234 occurrences of z, whereas the formula
(exists y)(exists x)R will be of length 2400 with 144 occurrences
of z.
In the 1970 edition, ordered pair is introduced by definition, following
Kuratowski, with the consequence that the length of their term denoting
the number 1 increases from 4 times (10 exp 12) to 2 times (10 exp 54).
A program written by Solovay in Allegro Common Lisp yields these
exact figures:
PROPOSITION If the ordered pair of x and y is introduced by definition
rather than taken as a primitive, the term defining 1 will have
2409875496393137472149767527877436912979508338752092897 symbols,
with
871880233733949069946182804910912227472430953034182177 links.
At 80 symbols per line, 50 lines per page, 1,000 pages per book, the shorter
version would occupy more than a million books, and the longer,
6 times (10 exp 47) books. I believe that the non-structuralist
approach customary among set-theorists is simpler, whereby
one defines 0 as the empty set and 1 as the singleton of the empty set.
Solovay remarks that Bourbaki's definition of 1 as given will not generalise
satisfactorily to higher cardinals as it omits a clause stating that the
function u with graph U is 1-1.
If one seeks an ad hoc definition of the number 1 in Bourbaki's
dialect of set theory, a shorter one --- perhaps *the* shortest~? ---
would be "some Z such that there is a member of Z which equals all
members of Z", which runs to 176 symbols with 56 links.
Rough calculations suggest that for large n, a Bourbachiste
definition of n as "some object a for which exists x_1 ... exists x_n
with a = {x_1, ... x_n} and the x's all distinct"
will have over n exp (2 exp (n+1)) symbols, whereas
von Neumann's definition of n as the set of all m less than n,
when written in the symbolism of a standard set-theoretic
formalism with quantifiers taken as primitive, has of the order of 2 exp n
symbols, whilst a yet shorter definition of von Neumann's n as
"the union of the class of all b such that ((b is a transitive set of
transitive sets) and (exists x_1 ... exists x_n
with b = {x_1, ... x_n} and the x's all distinct))" has O(n exp 2)
symbols. I learn from Solovay that
that can be improved to O(log n loglog n)$ or even
$O(log n)$ with "recycling of variables".
A. R. D. Mathias
More information about the FOM
mailing list