Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it the right point of view to say, that topology is nonfirstorderizable (only) because the union of arbitrarily many open sets has to be open? And if "arbitrarily many" was relaxed to "finitely many", topology would be firstorderizable?

I can imagine two versions of the relaxed theory: one whose models must be powersets, and another one whose models may be arbitrary boolean lattices (both with an extra predicate "open").

Has one of these relaxed first-order theories been found worth being studied in its own right?

share|improve this question
    
If it you limit topology to union of finitely many open sets, then you can write a sentence for every $n$ saying that the union of $n$ open sets is open. However you will severely damage the properties of topologies, for example a countable base will not span uncountably many open sets. –  Asaf Karagila Jun 21 '11 at 6:51
2  
You might also be interested in jstor.org/stable/2274362 –  Asaf Karagila Jun 21 '11 at 7:01
    
@Asaf: Thank you for the reference. –  Hans Stricker Jun 21 '11 at 7:04
    
@Hans Stricker: There is not an awful lot of literature, but there is some, as a search will reveal. Lately some Comp. Sci. people have taken an interest. –  André Nicolas Jun 21 '11 at 7:09
7  
That is a really ugly word... –  Mariano Suárez-Alvarez Jun 21 '11 at 12:52
show 4 more comments

1 Answer

up vote 19 down vote accepted

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/

share|improve this answer
2  
+1, this is just the reason people use set theory to base mathematics upon, the ability to write second-order sentences as first-order ones. –  Asaf Karagila Jun 21 '11 at 12:17
1  
@Hans: You misunderstand. The theory itself has second-order sentences, yes. However within the confines of set theory (e.g. ZFC) second order logic is just first order logic, so the theory of topological spaces when it is nested within a set theory is a first order theory. On the other hand, in many-sorted logic it can also be expressed as first order (adding a type of subsets of the universe as well). –  Asaf Karagila Jun 21 '11 at 12:52
2  
@Asaf: I also hesitate to say second-order logic is the same as first-order logic in set theory. The key point of set theory is that it does not have a type hierarchy: everything is of type "set" instead of being stratified as in type theory. –  Carl Mummert Jun 21 '11 at 13:03
3  
Hi Hans and Carl. Nice answer! In Hans's previous question I commented that to say that a class of structures is first-order means that it is elementary (without actually using the word "elementary"). I would say this is standard usage but Carl disagrees, so I'm probably wrong. Anyway, the class of topological spaces is not an elementary class. It was my understanding that Hans was trying to capture this class in a first order fashion, rather than trying to isolate its first-order consequences. –  Andres Caicedo Jun 21 '11 at 14:58
2  
@Mariano: if $X$ is finite, then $M_X$ has a finite domain (in all three sorts). If $X$ is infinite, them $M_X$ has an uncountable domain in sorts 2 and 3. But by the Lowenheim-Skolem theorem from logic, $T$ has models in which all three domains are countably infinite, and so these are not of the form $M_X$ for any space $X$. –  Carl Mummert Jun 22 '11 at 2:01
show 19 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.