Nonfirstorderizability is a concept from philosophy in which some argue that particular natural-language sentences cannot be captured in particular first-order theories. One example sentence they look at is "Some critics admire only one another". As a concept, nonfirstorderizability doesn't really apply to mathematical theories, only to English sentences. Virtually all of mathematics can be directly formalized in first-order set theory, and in particular this is how topology is usually formalized.
There are a few difficulties with the argument about nonfirstorderizability as it is often presented, including the argument on the Wikipedia page [2]. The main one is that that page refers to a particular sentence as a second-order sentence. However, there is nothing in the syntax of a sentence that ties it to any particular semantics: the same sentence could be studied in one-sorted second-order logic or two-sorted first-order logic. I would argue that anything that can be expressed in second-order logic can be expressed in two-sorted first-order logic. (This leads to a discussion of what it means to "express" something formally, which is for another day.) My point is that you have to take these claims critically, because the philosophical issues that are being discussed may or may not have much relevance to a working mathematician.
* First-order theory of topological spaces *
Before I make more comments about nonfirstorderizability, I want to explain how to make a first-order theory of topological spaces. The technique I am describing here is familiar to many logicians - it's routine, not novel.
The signature of the language includes three sorts of variables, no function symbols, no constant symbols, and the following relation symbols:
- $=^0$, $=^1$, $=^2$: equality relation symbols for each of the three sorts
- A unary relation $U(x^1)$ that takes an object of sort 1
- $R(x^0,x^1)$: a binary relation that takes an object of sort 0 and an object of sort 1
- $S(x^1,x^2)$: a binary relation that takes an object of sort 1 and an object of sort 2
Note that this is, so far, just an uninterpreted signature $\sigma$ which is unarguably a first-order three-sorted signature. We could use it to study various things, but in particular it is useful for topology. The use of three sorts is not essential; many-sorted first-order logic can be interpreted in one-sorted first-order logic, so there is no gain in expressiveness. It's simply more concise to use many-sorted logic.
Every topological space $X$ gives rise to a $\sigma$-structure $M_X$, as follows:
- The objects of $M_X$ of sort 0 are the points of $X$
- The objects of $M_X$ of sort 1 are the sets of points of $X$
- The objects of $M_X$ of sort 2 are the sets of sets of points of $X$
- $U$ is interpreted so that $U(a^1)$ holds in $M_X$ if and only if $a^1$ is an open set in $X$
- $R$ is interpreted so that $R(a^0, a^1)$ holds in $M_X$ if and only if $a^0 \in a^1$.
- $S$ is interpreted so that $S(a^1,a^2)$ holds in $M_X$ if and only if $a^1 \in a^2$.
- All the equality relation symbols are interpreted in $M_X$ as the actual equality relations on the three sorts
Let $T$ be the set of all $\sigma$-sentences $\phi$ such that for every topological space $X$, $\phi$ is true in $M_X$. Then, in the usual jargon, $T$ is the first order theory of topological spaces in signature $\sigma$. $T$ will include, for example, this first-order sentence which expresses the fact that the union of an arbitrary collection of open sets is open:
$$
(\forall x^2)((\forall z^1)(S(z^1,x^2)\to U(z^1)) \to (\exists x^1)(U(x^1) \land (\forall x^0)(x^0 \in x^1 \leftrightarrow (\exists z^1)(R(x^0,z^1)\land S(z^1,x^2)))
$$
More examples: $T$ will contain sentences expressing the axiom of extensionality for sorts 1 and 2; it will contain a sentence saying that the empty set is an open set, and it will contain a sentence saying the intersection of two open sets is open. All of these can be naturally expressed as first-order sentences in the signature $\sigma$.
As I mentioned, the use of three sorts is not necessary here, they can be simulated by adding three additional unary predicates to the structure. So we could do the same thing in one-sorted first-order logic.
* Analysis *
Any argument that something is "not first order" has to be made with the awareness of this sort of construction. There may be some sense in which the theory $T$ I have just constructed is a not a "first order theory", but that sense appears to be very subtle, and disagrees with the usual terminology. It seems more natural to accept that $T$ is indeed a first-order theory and ask what "nonfirstorderizability" could mean given the existence of examples such as this. I am confident that philosophers who look at nonfirstorderizability must be aware of examples such as this, so when we read their remarks we have to take into account that "cannot be expressed in first-order logic" might not have its literal meaning.
A key fact to note is there is no set of first-order axioms, in the signature $\sigma$, such that every model of these axioms is of the form $M_X$ for some topological space $X$. The model-theoretic way of saying this is that the collection of models that correspond to actual topological spaces is not an "elementary class". But there are many other objects that we study in first-order logic that do not form elementary classes; the question of which classes of structures are elementary was a central motivation of classical model theory. If all that we meant by "nonfirstorderizable" was "not an elementary class" then we would just use the established terminology. So I think that "nonfirstorderizable" has to be read as meaning something other than "not an elementary class".
In light of examples like the one above, though, I'm not sure what a rigorous definition of "nonfirstorderizable" would be. It seems to be related to the ability to express a theory in a particularly limited signature. But, for example, the axioms of a topology mention points, sets of points, and sets of sets of points, and the theory I constructed above seems like a pretty minimal theory, syntactically, for expressing propositions about these three sorts of objects.
In the case of the sentence "Some critics admire only one another", the philosophical question is whether the sentence necessarily involves sets (in which case we would expect to use sets to formalize it) or whether it can be understood without reference to sets. This is a good philosophical question. But mathematical theories such as topology or the theory of complete ordered fields explicitly mention sets, so it is not obvious to me why we would expect to be able to axiomatize them without sets.
The question that Terence Tao described in his blog post [2] is a little different. The issue there is not with sets directly, it's with tracking the dependence of quantified variables deep within a formula on variables quantified farther out in the formula. I think this is also qualitatively different than the question about topology.
1: http://en.wikipedia.org/wiki/Nonfirstorderizability
2: http://terrytao.wordpress.com/2007/08/27/printer-friendly-css-and-nonfirstorderizability/
