MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Bourbaki’s epsilon-calculus notation

Bourbaki used a very very strange notation for the epsilon-calculus consisting of $\tau$s and $\blacksquare$. In fact, that box should not be filled in, but for some reason, I can't produce a \Box.

Anyway, I was wondering if someone could explain to me what the linkages back to the tau mean, what the boxes mean. Whenever I read that book, I replace the $\tau$s with Hilbert's $\varepsilon$s. I mean, they went to an awful lot of trouble to use this notation, so it must mean something nontrivial, right?

You can see it on the first page of the google books link I've posted. I'm not sure if it's supposed to be intentionally vague, but they never introduce any metamathematical rules to deal with linkages except for the criteria of substitution, which pretty much cannot interact with $\tau$ terms.

Also, of course, since it's a book written to be completely a pain in neck to read, they use a hilbert calculus, and even worse, without primitive equality for determining whether or not two assemblies are equivalent.

-
I've forced this question into wiki mode, because I'm afraid that it will be voted down for being about metamathematics rather than mathematics itself. – Harry Gindi Feb 6 2010 at 3:51
However, this is the first correct use of the tag [metamathematics]. This is literally about symbols on ticker tapes and such. – Harry Gindi Feb 6 2010 at 3:53
metamathematics is the mathematics of mathematics. It is a branch of mathematics that includes model theory, proof theory, etc. I don't understand your comment about being the only valid use of the 'metamathematics' tag. – Darsh Ranjan Feb 6 2010 at 5:24
Well, ya see, there's "real" metamathematics, and "applied" metamathematics... I hope someone catches that reference. – Harry Gindi Feb 6 2010 at 16:19
In the sense of Hardy. – Harry Gindi Feb 6 2010 at 16:19
show 1 more comment

Let me address the part of the question about "what the linkages back to the tau mean, what the boxes mean." The usual notation for using Hilbert's epsilon symbol is that one writes $(\varepsilon x)\phi(x)$ to mean "some (unspecified) $x$ satisfying $\phi$ (if one exists, and an arbitrary object otherwise)." If, like Bourbaki, one wants to avoid quantifiers in the official notation and use $\varepsilon$ instead (specifically, expressing $(\exists x)\phi(x)$ as $\phi((\varepsilon x)\phi(x))$), then any non-trivial formula will contain lots of $\varepsilon$'s, applied to lots of variables, all nested together in a complicated mess. To slightly reduce the complication, let me suppose that bound variables have been renamed so that each occurrence of $\varepsilon$ uses a different variable. Bourbaki's notation (even more complicated, in my opinion) is what you would get if you do the following for each occurrence of $\varepsilon$ in the formula. (1) Replace this $\varepsilon$ with $\tau$. (2) Erase the variable that comes right after the $\varepsilon$. (3) Replace all subsequent occurrences of that variable with a box. (4) Link each of those boxes to the $\tau$ you wrote in (1). So $(\varepsilon x)\phi(x)$ becomes $\tau\phi(\square)$ with a link from the $\tau$ to the boxes (as many boxes as there were $x$'s in $\phi(x)$).

One might wonder why Bourbaki does all this. As far as I know, the point of the boxes and links is that there are no bound variables in the official notation; they've all been replaced by boxes. So Bourbaki doesn't need to define things like free and bound occurrences of a variable. Where I (and just about everybody else) would say that a variable occurs free in a formula, Bourbaki can simply say the variable occurs in the formula.

I suspect that Bourbaki chose to use Hilbert's $\varepsilon$ operator as a clever way of getting the axiom of choice and the logical quantifiers all at once. And I have no idea why they changed $\varepsilon$ to $\tau$ (although, while typing this answer, I noticed that I'd much rather type tau than varepsilon).

-
 Adrian Mathias in "A term of length..." points out that $\epsilon$ "is visually too close to the sign $\in$ for the membership relation" and gives a hint to his Danish Lectures. To learn more about $\tau$, please read tauday.com/tau-manifesto.pdf ;-) – Hans Stricker Apr 1 2011 at 9:37 I didn't notice this answer when you posted it. I came back to this question because I was talking about it with someone, and this is fantastic. I've chosen this as the new 'best answer'. Thanks! – Harry Gindi Aug 1 at 21:06

Matthias' polemics are funny at points but also misleading in several respects:

1. ZFC also has enormous length and depth of deductions for trivial material. According to Norman Megill's metamath page, "complete proof of 2 + 2 = 4 involves 2,452 subtheorems including the 150 [depth of the proof tree] above. ... These have a total of 25,933 steps — this is how many steps you would have to examine if you wanted to verify the proof by hand in complete detail all the way back to the axioms." Megill's system is based on a formalism for substitutions so there may be an enormous savings here compared to the way in which Matthias performs the counts (i.e., the full expanded size in symbols) for Bourbaki's system. If I correctly recall other information from Megill about the proof length he estimated for various results in ZFC, the number of symbols required can be orders of magnitude larger and this is what should be compared to Matthias' numbers.

2. The proof sizes are enormously implementation dependent. Bourbaki proof length could be a matter of inessential design decisions. Matthias claims at the end of the article that there is a problem using Hilbert epsilon-notation for incomplete or undecidable systems, but he gives no indication that this or any other problem is insurmountable in the Bourbaki approach.

3. Indeed, Matthias himself appears to have surmounted the problem in his other papers, by expressing Bourbaki set theory as a subsystem of ZFC. So either he has demonstrated that some reasonably powerful subsystems of ZFC have proofs and definitions that get radically shorter upon adding Replacement, or that the enormous "term" he attributes to the Theorie des Ensembles shrinks to a more ZFC-like size when implemented in a different framework.

EDIT. A search for Norman Megill's calculations of proof lengths in ZFC found the following:

"even trivial proofs require an astonishing number of steps directly from axioms. Existence of the empty set can be proved with 11,225,997 steps and transfinite recursion can be proved with 11,777,866,897,976 steps."

and

"The proofs exist only in principle, of course, but their lengths were backcomputed from what would result from more traditional proofs were they fully expanded. ..... In the current version of my proof database which has been reorganized somewhat, the numbers are:

empty set = 6,175,677 steps

transf. rec. = 24,326,750,185,446 steps"

That's only the number of steps. The number of symbols would be much, much higher.

-
Why does it take so many steps to prove the empty set exists? If $B$ is any set, then the Comprehension axiom says {$x\in B | x \neq x$} exists, and this is empty. I understand that a formal version of this argument would be longer, filling in all the logical steps, but what are most of those 6 million steps in Megils' proof about? – Joel David Hamkins Jul 14 2010 at 11:06
I don't know, but both Megill's and Matthias' numbers seem to indicate that when you deliberately strip away the higher-level interface that we implicitly use to handle the (also implicit, or unspecified) lower-level proof language, things balloon. – T. Jul 14 2010 at 15:48
Also, Megill's work is downloadable from his Metamath (Proof Explorer) web site. – T. Jul 14 2010 at 15:49
The outline is: Separation Axiom instance $\forall A\exists B\forall z(z\in B\iff z\in A\wedge \neg z= z)$. Universal instantiation strips off A quantifier. Existential instantiation produces $\forall z(z\in B\iff z\in A\wedge \neg z=z)$. State a tautology and apply MP to get $\forall z(z=z\to z\notin B)$. Equality axiom $\forall z\, z=z$. Another tautology and MPs give $\forall z\, z\notin B$. Existential generalization yields $\exists B\forall z\, z\notin B$, as desired. – Joel David Hamkins Jul 15 2010 at 2:41
Another issue is that Mathias was computing the size of the term defining $1$, not the proof that it exists (or that it is the multiplicative identity). So the relevant comparison would be the fact that in ZFC, the empty set is defined by the formula $\forall z\, \neg z\notin x$, which has 6 symbols. The natural number $1$ (usually taken to be {0}) is defined by $\forall y\, (y\in x \iff \forall z\, \neg z\in y)$, which has 14 symbols. – Joel David Hamkins Jul 15 2010 at 2:50

You must read the charming essay lampooning this notation, while also giving a thorough logical analysis of it, by Adrian Mathias.

He describes it thus:

A calculation of the number of symbols required to give Bourbaki's definition of the number 1; to which must be added 1,179,618,517,981 disambiguatory links. The implications for Bourbaki's philosophical claims and the mental health of their readers are discussed.

-
Brilliant! Great Job! – Harry Gindi Feb 6 2010 at 4:15
I knew it! Those first few sections are pretty much unreadable. – Harry Gindi Feb 6 2010 at 4:21
Adrian taught me set theory! I don't think he ever forgave Bourbaki for eschewing the axiom(-scheme) of replacement. He seems to have been having little swipes at them ever since :-) – Kevin Buzzard Feb 6 2010 at 7:30
Adrian is great, I agree. But this article is more than a little swipe---it makes them look completely ridiciulous about math logic. He has another article called "The ignorance of Bourbaki", if you follow the link on his name, which is directly critical of this particular Bourbaki volume, as well as some follow-up articles. – Joel David Hamkins Feb 6 2010 at 14:14
Those are some impressive articles. I had no idea Bourbaki was so set on pretending Godel's work didn't exist. – S. Carnahan Feb 6 2010 at 23:06
show 1 more comment