G. Aldo Antonelli

A minimal set theoretic paradox

Apr 302013

There is a old paradox, originally due to Montague (JSL 20 (2), 1955, p.140) that only requires the most minimalist set theoretic apparatus, viz., the existence of singletons. It does not seem to be very well known, so here it is.

Let $A = \{ x | \forall k (x \in k \to \exists y \in k(k \cap y = \varnothing))\}$ . Intuitively, $A$ is the collection of all sets that only belong to well-founded sets. Clearly, $A$ is too big to be a set, but that is not the point. The point is that this can be shown in classical predicate logic using only existence of singletons:

$\forall x \exists y \forall z(z \in y \leftrightarrow z = x).$

We proceed by cases, and derive a contradiction in each.

$A \in A$ ; then $A$ only belongs to well-founded sets. Since $\{A\}$ exists and $A \in \{A\}$ , the latter must be well-founded, so $\exists y \in \{A \}(\{A\} \cap y = \varnothing)$ . But $y \in \{A\}$ is equivalent to $y=A$ , so $\{A\} \cap A = \varnothing$ , which is impossible if $A \in A$ (for then $A$ itself is in the intersection $\{A\} \cap A$ ).
$A \notin A$ . Then there must be a $k^*$ such that: $A \in k^*$ and $\forall y \in k^*(k^* \cap y \not= \varnothing)$ . In particular $k^* \cap A \not= \varnothing$ , so there is a $z$ which belongs to both $k^*$ and $A$ . Now, since $z\in A$ :
$\forall k (z \in k \to \exists y \in k(k \cap y = \varnothing)),$

and since $z\in k^*$ , we have $\exists y \in k^*(k^* \cap y = \varnothing)$ contradicting the choice of $k^*$ .

Whereabouts?

Travel No Responses »

Apr 142013

Hint: They do not speak French here.

And those are not the famous palm trees lining the Champ de Mars.

Universal Love

Logic, Research No Responses »

Feb 062013

A characteristic feature of natural languages such as English is that quantifiers can be plugged directly into a predicate’s argument places, thereby dispensing with the whole variable-binding machinery. The example we give students in introductory logic class is the statement of universal love:

Everybody loves everybody

or, as one California motorist efficaciously put it:

Of course, the price to pay for the economy of expression of natural language is potential ambiguity: we do not know, from the license plate above, whether the first quantifier has wide scope over the second or the other way around. The ambiguity is crucial, for instance, when different quantifiers occupy the two argument places:

Everybody loves somebody

is highly ambiguous (especially out of context), another lesson we teach our students. But in the case above, we think, it does not matter, because, as is well known:

Like quantifiers commute.

Or do they? This is another one of those universally known “facts” that are in fact only justified on the basis of a one-sided diet of examples. As pointed out in a previous post, there are non-standard interpretations of $\forall$ and $\exists$ on which the quantifiers do not commute, but we need not go to such lengths to appreciate the point.

Suppose humans are arranged in a countably infinite list $h_1, h_2, \ldots, h_n, \ldots$ where $h_i$ loves $h_j$ if and only if $i < j$ . Let $\mathsf{Q}$ be the quantifier “for co-finitely many,” then $\mathsf{Q}x\mathsf{Q}y \, Lxy$ is true (there are co-finitely many $x$ ‘s that love co-finitely many $y$ ‘s), but $\mathsf{Q}y\mathsf{Q}x \, Lxy$ is false (there aren’t co-finitely many $y$ ‘s that are loved by co-finitely many $x$ ‘s). So, like quantifiers do not always commute. (This is an adaptation of an example I learned from Thomas Forster.)

First-order Henkin semantics

Logic, Research No Responses »

Dec 112012

I finally have a complete draft of “On the general interpretation of first-order quantifiers,” which can be obtained here. From the abstract:

While second-order quantifiers have long been known to admit non-standard, or “general” interpretations, when properly viewed as predicates of predicates first-order quantifiers also turn out to allow a kind of interpretation that does not presuppose the full power-set of that interpretation’s first-order domain. This paper introduces such “general” interpretations for first-order quantifiers, exploring some of the consequences of the definition especially as regards the unary case, emphasizing the effects of imposing various further constraints that the interpretation is to satisfy.

Comments and other feedback always welcome.

Huw Price on Metaphysics

Philosophy, Research No Responses »

Nov 092012

In ” Metaphysics After Carnap: the Ghost Who Walks?,” Huw Price asks us to imagine a philosopher who, in the 1950′s, falls asleep at the wheel while stuck in a traffic jam of the New Jersey turnpike, only to wake up sixty years later and find, much her astonishment, that metaphysics has become respectable again. Back in the days, after all, metaphysics (just like poverty) was supposed to be on its last legs. The fact that both have not only survived but prospered does not make the one any more palatable than the other. The following quote from Price is one for the ages:

What’s haunting the halls of all those college towns – capturing the minds of new generations of the best and brightest – is actually the ghost of a long-discredited discipline. Metaphysics is actually as dead as Carnap left it, but – blinded, in part, by these misinterpretations of Quine – contemporary philosophy has lost the ability to see it for what it is, to distinguish it from live and substantial intellectual pursuits.

Sunset over the Pacific

Travel No Responses »

Sep 232012

The last sunset of summer, 2012

The co-finite quantifier

Logic, Research No Responses »

Sep 052012

Thomas Forster came through town the other day, and we ended up chatting about the quantifier “there exist infinitely many” (written $\exists_\infty$ and studied by Yasuhara in the 1960′s) and its dual “for all but finitely many” (written $\forall_\infty$ , and sometimes abbreviated as “a.e.” for “almost every”). Thomas has a clever gloss for $\forall_\infty x \lnot \phi(x)$ as “hardly ever $\phi$ ,” which of course expresses the fact that there are at most finitely many $x$ such that $\phi(x)$ .

It is clear that adjoining the co-finite quantifier $\forall_\infty$ to first-order logic results in a dramatic increase of expressive power, for then one can characterize the standard model $(\mathbb{N},<)$ up to isomorphism. All one has to say is that $<$ is a strict linear order with first but no last element (which is expressible in first-order logic) with the additional property that for each $x$ there are at most finitely many $y$ ‘s such that $y<x$ .

It is remarkable, though, that things are quite different in the case of a first-order language in which the ordinary quantifier symbols $\forall$ and $\exists$ receive the above mentioned interpretation for the co-finite quantifier and its dual. In other words, the language built up from predicates (including identity) by means of connectives and the co-finite quantifier seems to be quite weak. For instance, Marker and Slaman prove that it is decidable whether a closed formula of such a language is true in the standard model of arithmetic. The proof shows that the language so interpreted cannot distinguish between satisfaction in $\mathbb{N}$ and satisfaction in $\mathbb{R}^+$ , and since the latter is decidable by Tarski’s famous result, so is the former. And of course it also follows that the ordinary first-order quantifiers are not definable from the co-finite one.

Links to papers

Logic, Site Admin No Responses »

Jul 102012

I noticed that some of the links to the PDF versions of the articles (under “Papers,” to the right) are broken. I plan to check them all soon, but in the meanwhile, if you notice any broken links, just shoot me an email using the “Contact” form. Thanks!

C2P2L: new! improved!

Logic, Teaching, Uncategorized No Responses »

Apr 212012

I finally got around to fixing up a bunch of small typos and adding a few clarification to $\mathsf{C^2P^2L}$ . The latest version is available here. From the initial blurb:

Kurt Gödel’s completeness theorem for the first-order predicate calculus (1929–30) is one of the deepest classical results in metalogic, perhaps of deeper foundational significance than Gödel’s own incompleteness theorem for arithmetic (1931). The theorem establishes the extensional equivalence of two very different notions of consequence for first-order formulas, validity and provability, the first one of which involves an unbounded universal quantification over the class of possible interpretations, while the second one merely asserts the existence of certain finite sequences of formulas. The purpose of these notes is to chart a direct and self-contained route to a proof of the completeness theorem for first-order logic. Since the heart of the combinatorial argument is already present in the proof of the propositional case, the propositional case is treated independently. Once the proof strategy for the propositional case is laid out, the further complications required to handle existential witnesses in the predicate case are introduced. Thus, the completeness proof takes up the first two parts of what follows. The third part is devoted to further results and applications, while the last part collects some problem sets that introduce further material and might be useful for classroom use. It should be mentioned that where proofs are routine they have been merely sketched or even omitted (the full details to be supplied at the chalkboard), but any unexpected steps are explicitly mentioned.

Comments and any other feedback are welcome!

Schola Logicae

Logic, Travel No Responses »

Apr 072012

I know it’s a bit of a cliché, but I had to have this picture taken while seemingly coming out of the door marked “School of Logic” at the Bodleian.

Older Entries