FOM: The ineffable name of 1

[Andrian-Richard-David Mathias]

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