Vote for Sigmund’s Vienna Circle Book

Karl Sigmund has a book on the Vienna Circle (to accompany the wonderful Vienna Circle exhibition this Fall for the University of Vienna’s 650th anniversary).

Sie nannten sich Der Wiener Kreis:Exaktes Denken am Rand des Untergangs is an accessible introduction to the history and context of the Vienna Circle.  You may not need such an introduction, but you will appreciate the pictures!

The book is up for an award on scientific writing: vote for Sigmund’s book here (in the section “Naturwissenschaft und Technik”).

Remembering Aldo Antonelli

[The following remarks were delivered today by Andy Arana at the beginning of a joint Paris-Davis workshop on the philosophy of mathematics, and are posted here with his permission and that of Curtis Franks.  The photo above shows Aldo at a cook-off with Marco Panza at the last instalment of that workshop series in Davis, and is courtesy of Robert May.]

These days people are quick to take positions, “hot takes”. ZFC is the right foundation of mathematics, first-order logic is the true logic, the nature of mathematical knowledge is intuitionist, the axiom of projective determinism is true, nominalism is true. And so on. These are bold statements, and they draw attention. The result is a literature that moves quickly and as a result yields little change, little persuasion, little clarification, little wisdom. It comes to seem dogmatic: one’s reputation is connected with one’s intellectual position, and thus changing your mind comes with the loss of professional status.

Aldo was not like this. Aldo’s work was about exploring new possibilities, alternatives to views that could otherwise calcify into mere dogmas. One can think of them as playing a role in an intellectual infrastructure to which spaces are regularly wrongly closed off. “that approach won’t work, for such and such a reason”: Aldo would provide technical results that opened those approaches up again. Whether you take those approaches, that’s up to you. But it’s not their impossibility that should stop you.

I want to start briefly by discussing Aldo’s early work. He worked on the foundations of defeasible consequence and non-monotonic logics, of Quine’s New Foundations set theory, and of non-well founded set theory. Rather than try to summarize the results, I want to tell a story about why he worked on these things, a story that I think will illuminate an order to Aldo’s approach to problems. Indeed, here I want to quote his student Curtis Franks, who kindly shared some personal thoughts about Aldo with me. On this early work of Aldo’s, Curtis writes,

“One might say that there were some technical gimmicks to work out, and he had the relevant tools to discover and present these things. But this is wrong. Aldo was interested in the results that were the most beautiful, the ones that unpacked the most hidden connections, the ones that made us rethink the greatest number of our inhibiting preconceptions. Because he didn’t care much about, and possibly didn’t even understand, ideas about which set theories were correct, he was able to feel his way to the mathematical relationships that disclosed the greatest number of such insights.”

Aldo applied this method with particular focus to logicism and in particular to the thesis that arithmetic is logic. Frege’s logicist program had the following two stages: 1) to define numbers as extensions of concepts, and 2) to derive logically the theorems of arithmetic from that definition. That these two stages cannot both be carried out is more or less consensus today. Where there is consensus, though, there is need for light: for what possibilities are being closed out by the consensus? I want to talk about three projects of Aldo that opened such possibilities for logicism.

I want to begin with “Frege’s New Science”, written with Robert May. Aldo broke the question of whether Frege’s logic could carry out metatheory into two parts: 1) can metalogical questions about Frege’s logic be posed in Frege’s logic itself? and 2) is metatheory necessarily model theory, in which one varies the meanings of propositions in order to prove for instance independence results? Aldo and Robert answered “no” to 2), in light of Frege’s insistence that one cannot reinterpret the meanings (references) of non-logical terms of axioms, since axioms express thoughts. They argue that Frege saw, if not particularly clearly, a way to develop metatheory in which one replaces the reinterpretability of meanings with a kind of permutability of nonlogical vocabulary on which no meanings are changed. While the question of what vocabulary is nonlogical arises, Aldo and Robert sketch an argument (at least nearly) available to the Fregean that this question too can be handled by a permutability argument. Thus this article opens space for a new approach to understanding Frege’s metatheory by pursuing a technical development.

Next, I want to turn to “Frege’s Other Program”, also written with Robert May. Here Aldo and Robert explore a different possibility for reckoning the two logicist stages of defining numbers as extensions of concepts, and of deriving logically the theorems of arithmetic from that definition. As Aldo and Robert put it, one can attempt “to show in a nonlogical theory of extensions, where numbers are concepts, not objects, that Peano Arithmetic can be derived”. In doing so they identify a non-logicist but still broadly Fregean program for deriving arithmetic. This program clarifies the causes of the contradiction entailed by Basic Law V, providing a new counterexample to Hume’s Principle. Here again new spaces are opened, by investigating a extensional theory of arithmetic without supposing Hume’s Principle. One can then consider to what extent such a theory could be judged a vindication of logicism.

Next, I want to turn to Aldo’s 2010 article “The Nature and Purpose of Numbers”, notable not least because it appeared in one of American philosophy’s top journals, the Journal of Philosophy. This article investigates a possible version of Fregean logicism, one that differs from other developments in that it does not reduce arithmetic to set theory. Aldo takes cardinal properties of the natural numbers as the starting point, and derives structural properties of the natural numbers from them, rather than the other way around as is done in typical set-theoretic reductions of arithmetic. Aldo’s idea is that “in keeping with the broadest and most general construal of logicism, cardinality notions… deal directly with properties and relations of concepts—rather than matters of existence of objects such as numbers—cardinality notions properly can be regarded as having a logical character.” They are logical notions, Aldo argues, because relations of concepts are quantifiers: more precisely, they are, Aldo argues, generalized quantifiers. The ordinary existential and universal quantifiers can be thought of as relations of concepts: the existential quantifier as the collection of all nonempty subsets of the domain of quantification, and the universal quantifier as the collection of all subsets of the domain that contain the domain as their only member. But these are not the only two relations that yield quantifiers, on the theory of generalized quantifiers, and in particular one can consider the Frege quantifier, which holds between two concepts F and G when there are no more Fs than Gs. In fact, these are all first-order quantifiers, Aldo argues. He then shows how the Frege quantifier can be taken as logically basic, and shows how one can derive the basic features of the natural numbers from such a logic.

I want to note in particular Aldo’s way of characterizing his accomplishment in this article. “Accordingly, we take the logicist claim that cardinality is a logical notion at face value, and rather than arguing for it (perhaps by providing a reduction to some other principle), we set out to explore its consequences by introducing cardinality, in the form of the Frege quantifier, as the main building block in the language of arithmetic.”

This passage illustrates beautifully the idea that Aldo’s approach to problems was to prescind from particular theoretical stances, and to explore the consequences of these stances. With a clearer understanding of these consequences, of their fruits, one can better evaluate the costs and benefits of particular positions. The job of the logician is to explore these consequences. And Aldo was a logician.

In this 2010 article, Aldo also noted how the Frege quantifier, a first-order quantifier, can be given a generalized Henkin interpretation. In Henkin’s work, one restricts the range of quantification to just a subset of the power set of the full domain. Models for second-order logic can then be specified by giving both the domain and a universe of relations over the domain. Aldo’s novel insight was that such an interpretation can also be given for first-order quantifiers. Within the context of Fregean logicism, this permits one to prescind from concerns about whether second-order logic is logic (another one of those dogmatic debates).

His 2013 article in the Review of Symbolic Logic, “On the general interpretation of first-order quantifiers”, expanded on this novel insight. In the words of Curtis Franks: “60 years or so after Henkin’s groundbreaking work on generalized models, Aldo observed what no one else ever noticed, namely, that the notion of a generalized model can be formulated already for first order languages. The irony is sharp: The “first-order case” of the Henkin construction becomes an extension (not a restriction) of the familiar second order case, where the notion of models given by filters over the full power set construction is more intuitive.” Curtis judges this to be Aldo’s deepest work.

In an article entitled “Life on the Range: Quine’s Thesis and Semantic Indeterminacy”, published this summer, Aldo pursued the consequences of this technical development for the evaluation of Quine’s dictum that to be is to be the value of a bound variable. As Aldo notes, this dictum flows from Quine’s view that second-order logic is “set theory in sheep’s clothing”. Since second-order logic on Quine’s view has ontological commitments, it is not really logic. Aldo observes that his work on generalized models puts pressure on Quine’s views. Since the first-order quantifiers can be interpreted to be extensions of second-order quantifiers, the ontological commitments of second-order logic are also ontological commitments of first-order quantifiers. In the closing sentence of this article, Aldo writes that “this last realization can contribute to the establishment of second-order logic on the same safe footing as first-order logic.”

I want to finish by drawing from Curtis Franks’ remarks one last time. Curtis writes, in closing,

“I cannot enumerate the ways that Aldo influenced me, but the one that I am the most aware of is pretty simple. It seems to me that most professional philosophers spend more time advancing their own research programs than they spend learning. To me this is completely unreasonable, and I am pretty sure that my attitude about this derives from Aldo’s influence. Why would I, or anyone really, care more about what I have to say than about what some 20 or so brilliant historical figures have already said. Do I love logic, math, and philosophy, or do I love professional credits? Everyone in our world initially loved the former, and it is a disgrace, Aldo taught, to abandon this idea. And, he taught me, if you persevere in your love for the most beautiful ideas in mathematics, philosophy, and logic, your own contributions will trickle in at the right time. Those ideas will not come close to being the most interesting things you have to talk about. But they will not only be true, they will be beautiful.”

De Morgan on Ada Lovelace

My Dear Lady Byron

I have received your note and should have answered no further than that I was very glad to find my apprehension (of being a party to doing mischief if I assisted Lady Lovelace’s studies without any caution) is unfounded in the opinion of yourself and Lord Lovelace, who must be better judges than I am, on every point of the case but one, and may be on that one. But at the same time it is very necessary that the one point should be properly stated.

I have never expressed to Lady Lovelace my opinion of her as a student of these matters: I always feared that it might promote an application to them which might be injurious to a person whose bodily health is not strong. I have therefore contented myself with very good, quite right, and so on. But I feel bound to tell you that the power of thinking on these matters which Lady L. has always shewn from the beginning of my correspondence with her, has been something so utterly out of the common way for any beginner, man or woman, that this power must be duly considered by her friends, with reference to the question whether they should urge or check her obvious determination to try not only to reach, but to get beyond, the present bounds of knowledge.  If you or Lord L. only think that it is a fancy for that particular kind of knowledge, which, though unusual in its object, may compare in intensity with the usual tastes of a young lady, you do not know the whole. And the same if you think that desire of distinction is the motive, science one of many paths which might be chosen to obtain it. There is easily seen to be the desire of distinction in Lady L’s character but the mathematical turn is one which opportunity must have made her take independently of that.

Had any young beginner, about to go to Cambridge, shewn the same power, I should have prophesied first that his aptitude at grasping the strong points and the real difficulties of first principles would have very much lowered his chance of being senior wrangler, secondly, that they would have certainly made him an original mathematical investigator, perhaps of first rate eminence.

The tract about Babbage’s machine is a pretty thing enough, but I could I think produce a series of extracts, out of Lady Lovelace’s first queries upon new subjects, which would make a mathematician see that it was no criterion of what might be expected from her.

All women who have published mathematics hitherto have shewn knowledge, and power of getting it, but no one, except perhaps (I speak doubtfully) Maria Agnesi, has wrestled with difficulties and shewn a man’s strength in getting over them. The reason is obvious: the very great tension of mind which they require is beyond the strength of a woman’s physical power of application.  Lady L. has unquestionably as much power as would require all the strength of a man‘s constitution to bear the fatigue of thought to which it will unquestionably lead her. It is very well now, when the subject has not entirely engrossed her attention: by and bye when, as always happens, the whole of the thoughts are continually and entirely concentrated upon them, the struggle between the mind and body will begin.

Perhaps you think that Lady L. will, like Mrs. Somerville, go on in a course of regulated study, duly mixed with the enjoyment of society, the ordinary cares of life &c &c. But Mrs. Somerville’s mind never led her into other than the details of mathematical work: Lady L. will take quite a different route. It makes me smile to think of Mrs. Somerville’s quiet acquiescence in ignorance of the nature of force, saying “it is \(dv/dt\)” (a math. formula for it) “and that is all we know about the matter”–and to imagine Lady L. reading this, much less writing it.

Having now I think quite explained that you must consider Lady L’s case as a peculiar one I will leave it to your better judgment, supplied with facts, only begging that this note may be confidential.

All here pretty well; I hope your house is free from illness and

Dear Lady Bryon
Yours very truly
A De Morgan

69 G. S.
Janry. 21/44

(Quoted from Velma Huskey, and Harry Huskey, “Lady Lovelace and Charles Babbage,” in Annals of the History of Computing 2(4), pp.299-329, 1980)

Ada Lovelace is 200

Ada Lovelace was born 200 years ago today.  Here’s a roundup of articles:

Meet Countess Ada Lovelace, The World’s First Computer Programmer (MTV)

Remembering Ada Lovelace, computer-music prognosticator (Boston Globe)

Die Zahlenzauberin (Neue Zürcher Zeitung, German)

An Undecidable Quantum Physics Problem

This is cool: In today’s Nature, Toby Cubitt, David Perez-Garcia, and Michael Wolf published a paper, “Undecidability of the spectral gap.” A short writeup is in Nature News, and an extended paper is on arXiv. It shows a problem in quantum physics–the spectral gap problem–to be undecidable by reducing the halting problem to it.

In the Nature News story, the first author is quoted as saying, “I think it’s fair to say that ours is the first undecidability result for a major physics problem that people would really try to solve.” Is that true?

Note that the article also links the undecidability result to an independence result: “Our results imply that for any consistent, recursive axiomatisation of mathematics, there exist specific Hamiltonians for which the presence or absence of a spectral gap is independent of the axioms.” In order to get this consequence, you’d reduce the problem to provability/refutability in your favorite axiom system \(T\): Give a computable function \(F\) with the following property: If \(i\) is an instance of the problem, \(F(i)\) is a formula in the language of \(T\) such that if \(T \vdash F(i)\) then \(i\) is a positive instance, and if \(T \vdash \lnot F(i)\) then it is a negative instance.  If \(T\) decided all the \(F(i)\), searching through all theorems of \(T\) will eventually yield either \(F(i)\) or \(\lnot F(i)\), and so provide a decision procedure for the problem. If the problem is undecidable, that can’t happen, so at least one \(F(i)\) must be independent of \(T\). (In fact, infinitely many must be, for any finite number could be treated as special cases before running the infinite search.)  But you do have to give this coding of instances of the problem. (Just for a couple of simple examples, for the halting problem and a sound arithmetical theory, \(F(i)\) would be the standard description of “Turing machine with index \(i\) halts on input \(i\)”; for Hilbert’s 10th problem, given a Diophantine equation \(p(\vec x) = 0\), \(F(p)\) would be \(\exists \vec x p(\vec x) = 0\).  See also the paper by Björn Poonen they cite in support of their claim, esp. p. 2.)

Unless I missed something, the authors haven’t done this. So in what sense have they shown that “there exist specific Hamiltonians for which the presence or absence of a spectral gap is independent”? To use the argument above, when you have the halting problem reduced to your new decision problem, you could just take the description of “TM \(i\) halts on input \(i\)” as your \(F(i)\).  This will have the required property for whichever instances of your decision problem the halting problem instances reduce to.  But this isn’t quite like actually giving a method for directly coding the physical problems in arithmetic, or exhibiting a sentence of arithmetic that says “quantum many-body model \(i\) is gapped.”

Note also that the coding \(F(i)\) depends on the axiom system, so the order of the quantifiers matters: for each axiom system, there will be possibly different encodings of the decision problem with the required property; and it’s not the case that there are instances of the decision problem that are independent of (and hence unsolvable by) any axiom system.  You can always add \(F(i)\) to your \(T\) for a true instance \(i\), or \(\lnot F(i)\) for a false instance, and this will yield a new axiom system which decides that instance in the sense given above.  In fact you can even add \(\lnot F(i)\) for a true instance (if \(F(i)\) is independent and doesn’t happen to be \(\Sigma^0_1\))!  Then you’ll get an unsound axiom system that will decide that instance incorrectly, and you’ll have to find a different coding.

I of course have no idea if the problem shown undecidable, or the features of the problem used in the reduction of the halting problem, are actually physically interesting.  It may well be that the physically interesting cases of the problem are decidable. Certainly one can decide at least some specific instances, and perhaps all instances that “occur in nature.” But IANAP.

tl;dr interesting “real-world” example of undecidability result physicists actually care about, not an interesting independence result.