User john goodrick - MathOverflow

Answer by John Goodrick for Independence from Set Theory Axioms

2009-11-11T06:02:55Z

As for what "theoretical framework" is needed, you can think of the independence theorems as statements about finite sequences of formulas, so the "metatheory" doesn't need to assume the existence of any uncountable sets.

In more detail: first, assign different natural numbers to each formula (via Gödel coding), and then define a formal proof to be a finite sequence of such numbers where each one encodes a formula that follows logically from the previously-encoded formulas. Consistency means that that the formula $x \neq x$ is not logically derivable in any finite number of steps. This converts "ZFC is consistent" into a combinatorial statement about finite sequences of natural numbers.

With this reductive approach, you don't have to worry about assuming the existence of large infinite sets a priori. In fact, I think that all the relative consistency results gotten using Cohen's forcing technique could, in principle, be formalized just in Peano arithmetic.

Kunen's Set Theory: An Introduction to Independence Proofs contains nice clear discussions of these foundational issues.

Answer by John Goodrick for Most interesting mathematics mistake?

2009-10-17T15:21:19Z

Frege's proposed axioms in Die Grundgesetze der Arithmetik.

Frege was trying to derive the concept of "number" from more basic concepts, and he tried to axiomatize higher-order logic (essentially, a kind of set theory), but his intuitive-seeming axioms were logically inconsistent. Russell first found the inconsistency, which we now call Russell's Paradox.

When does a transitive action of a profinite group have an infinite orbit?

2009-10-13T14:30:11Z

That is: suppose G is a profinite group acting 1-transitively (but maybe not regularly) on a set X. Is there a reasonable criterion for when there is a g in G and a point a in X such that the g-orbit of a is infinite?

I wonder if it's enough to have a family (g_i, a_i) of pairs in G times X such that the g_i-orbit of a_i has size at least i.

Also, does anybody study these things much? A google search for "profinite group action" yields only a few hits; "profinite permutation group(s)" yields none.

Answer by John Goodrick for Heuristic argument that finite simple groups _ought_ to be "classifiable"?

2010-09-17T16:49:30Z

I can't tell you much about finite groups, but I can tell you that unfortunately there is no general model-theoretic result along the lines of "If a collection of objects has a simple axiomatization, then it must be easy to classify." In fact, considering some examples, I believe that no such general result could exist even in principle.

Finitely axiomatizable, but hard to classify: The class of all linearly-ordered sets. There are many ways to make precise the idea that these are "hard to classify:" for any uncountable cardinal $\kappa$, there are many (i.e. $2^\kappa$) pairwise nonisomorphic orderings of size $\kappa$; there is no way to characterize arbitrary linear orderings up to isomorphism by a fixed set of cardinal-number invariants; and there are many large families of linear orderings which "look similar" but are nonisomorphic (where "looks similar" could be mean various things: bi-embeddable by maps preserving the truth of all first-order formulas, or "there is a forcing extension of the universe of set theory that preserves all cardinal numbers, adds no new subsets of $\mathbb{R}$, and in which the two structures are isomorphic," etc...)

Easy to classify, but not finitely axiomatizable: For example, the set of all algebraically-closed fields. These are axiomatizable by an infinite list of axioms: take all the field axioms, plus, for each natural number $n > 0$, an axiom saying "every degree-$n$ polynomial has at least one root." However, a simple argument using the compactness theorem shows that this class cannot be finitely axiomatizable. Also, these structures are "very easy to classify" in the sense that they are characterized, up to isomorphism, by just two cardinal numbers: the characteristic and the transcendence degree (over the prime subfield). (And hence any two such fields that ``look similar'' in the senses I mentioned above must actually be isomorphic.)

In fact, it's worse than these examples suggest. There is a theorem in model theory due to Cherlin, Harrington, and Lachlan saying that any axiomatizable class that is ``easy to classify'' in the sense that there is just one member (up to isomorphism) of size $\kappa$ for any infinite cardinal $\kappa$ cannot be finitely axiomatizable!

There is a well-studied notion of "classifiability" in model theory which concerns how hard it is to characterize all the models of a given theory by a "reasonable set of invariants." The main reference is Shelah's monograph Classification Theory. In general, classifiability of a theory has no logical relation with how hard it is to axiomatize the theory (e.g. whether it is finitely axiomatizable, computably axiomatizable, etc.). But Shelah's classification theory only treats theories with only infinite models, so I'm not sure that it can answer your question about finite simple groups.

Answer by John Goodrick for Which graphs are elementarily equivalent to their own disjoint sums?

2010-09-01T15:31:45Z

EDIT: This is now a two-part answer to respond to two of Joel's sub-questions. (I still don't know about his main question, which seems quite difficult to me.)

Part I: I claim that for any two cardinals $\gamma, \delta \geq 2$, a graph $G$ is $\gamma$-self-similar if and only if $G$ is $\delta$-self-similar.

The idea is to use Ehrenfeucht-Fraisse games to show that $m$-self-similarity for a finite $m \geq 2$ is equivalent to $\gamma$-self-similarity for every cardinal $\gamma$.

First, suppose $G$ is elementarily equivalent to $m$ disjoint copies of itself for some finite $m$. Then for any finite $k$, $G$ is elementarily equivalent to the disjoint union of $m^k$ copies of itself. (Why? You can do an induction on k; if $G$ is equivalent to $G^{m^k}$, then you can show that $G^m$ is equivalent to $G^{m^{k+1}}$ by thinking of the latter as a sum of $m$ copies of $G^{m^k}$, and then get a winning strategy for the verifier for an EF game on $(G^m,G^{m^{k+1}})$ by thinking of the game as a sum of $m$ simultaneous games between each copy of $G$ in $G^m$ and each copy of $G^{m^k}$ in $G^{m^{k+1}}$, using the verifier's winning strategy for $(G, G^{m^k})$ on each subgame.) It follows that for any infinite $\gamma$, $G$ is elementarily equivalent to a disjoint sum of $\gamma$ copies of itself: to show that the length-$n$ EF game against $G$ and $G^\gamma$ has a winning strategy for the verifier, we simply pick $k$ with $m^k \geq n$ and use the winning strategy for the verifier for $G$ and $G^{m^k}$.

Second, suppose $G$ is elementarily equivalent to $G^\gamma$ for some infinite $\gamma$. Then for any finite $k$, $G^k$ is also elementarily equivalent to $G^\gamma$: this is because we can write $G^\gamma$ as a disjoint sum of $k$ copies of $G^\gamma$ (since $\gamma$ is infinite), and to get a winning strategy for the verifier for the $n$-step EF game, simply imagine that you are playing $k$ separate games between each copy of $G$ in $G^k$ and each of the $k$ copies of $G^\gamma$.

So if $k$ and $\ell$ are finite and $G^k$ is elementarily equivalent to $G^\omega$, then $G^\ell$ is also elementarily equivalent to $G^\omega$, so by transitivity, $G^k$ is equivalent to $G^\ell$. Putting all of this together, my claim follows.

Part II: It is possible to give a nice characterization of self-similarity for abelian groups.

Szmielew showed that two abelian groups G and H are elementarily equivalent if and only if they have all the same "Szmielew invariants," where the Szmielew invariants of G are the following (which are defined to be either natural numbers 0, 1, ... or $\infty$):

The exponent of G, the least positive n (if it exists) such that nG = 0, or else $\infty$;
For each prime p and $n \geq 0$, $\dim {p^n G[p]}/{p^{n+1} G[p]}$, where $G[p]$ is the subgroup of all $p$-torsion elements of $G$ and the dimension is as an $\mathbb{F}_p$ vector space;
For each prime p, $\lim_{n \rightarrow \infty} \dim {p^n G}/{p^{n+1} G}$;
For each prime p, $\lim_{n \rightarrow \infty} \dim p^n G[p]$.

Since $G \oplus G$ has the same exponent as $G$ and invariants 2 through 4 commute with direct sums (the invariant of $G \oplus H$ is the sum of the invariants of $G$ and of $H$), it follows that an abelian group $G$ is self-similar if each of its invariants of type 2 through 4 is either $0$ or $\infty$.

(See Hodges' Model Theory or Prest's Model Theory and Modules for nice explanations of Szmielew invariants.)

I don't know how far this generalizes -- i.e. are there many other natural categories with coproducts such that elementary equivalence is determined by such a list of cardinal invariants which commute with taking coproducts? For graphs, this seems like too much to hope for, but at least maybe for theories of modules over nice rings (like Dedekind domains) you could do something similar.

Answer by John Goodrick for Model theory stressing order type of universe.

2010-08-18T19:57:46Z

I don't think many model theorists have worked on this. Granted, I'm a little unclear what Chang and Keisler were asking here, but here's one possible precisification:

Question: Suppose we are given a (complete?) theory T in a language with a binary relation < such that T proves "< is a strict linear ordering." Try to develop a theory of the "order-type spectrum" $I(\alpha, T)$, which is defined as the number of nonisomorphic models $M$ of $T$ such that $(M, <^M)$ has order type $\alpha$.

You could start by trying to think about what it means for $T$ to be "$\alpha$-categorical" for some order type $\alpha$, meaning, what are necessary and sufficient conditions for $I(\alpha, T)$ to equal $1$? (I have no idea whether anybody has investigated this before.) For example, if $T$ proves that the ordering is dense without endpoints and $\eta$ is the order type of the rationals, then $I(\eta, T) = 1$ if and only if $T$ is $\omega$-categorical, since the complete theory of $(\mathbb{Q}, <)$ itself is $\omega$-categorical.

An immediate complication I see to this project is that I don't know if there is any good analogue of the upward Lowenheim-Skolem theorem. It seems like it would be difficult to answer the question: "Given a theory $T$, for which infinite order types $\alpha$ is $I(\alpha, T) \neq 0$?" (The corresponding question for cardinalities of the universe for a $T$ with infinite models is trivial, by Lowenheim-Skolem.) For example: your theory $T$ could force the order type of any model to not be Dedekind complete (e.g. take the complete theory of an densely-ordered ring with a unary predicate for a proper convex subring).

Are there Morley-like categoricity theorems? If $T$ is countable, say, and $I(\alpha, T) = 1$ for some uncountable order type $\alpha$, can we conclude that $I(\beta, T) \leq 1$ for every uncountable $\beta$? Possibly this could be an interesting question; offhand I have no idea what the answer is.

Illustrating the difficulties of this, here's a paper just on the possible order types of a particular theory, PA:

"Order-types of models of Peano arithmetic," by Andrey Bovykin and Richard Kaye, pp. 275-285 of Logic and Algebra, edited by Yi Zhang with a preface by Oleg Belegradek, Contemporary Mathematics 302, AMS.

A different interpretation of the original question would be: given a particular order type $\alpha$, investigate structures with order type $\alpha$. Along these lines, many model theorists (such as Pillay, van den Dries, Wilkie, and others) have been studying expansions of the ordered field of the real numbers under the rubric of "o-minimal theories," though generally the interest has been in definable sets rather than models per se. Chris Miller is an example of an o-minimalist who has done a significant amount of research just on structures expanding the field of reals; check out his webpage for some state-of-the-art papers in this area.

Answer by John Goodrick for Complete Extensions of First Order Logic (or Language)

2010-08-03T18:26:49Z

There are some model theorists currently studying extensions of first-order logic, mainly in the setting of so-called Abstract Elementary Classes (or AECs). An AEC is a class of structures with a given signature (as in model theory) equipped with a distinguished "strong substructure relation" which satisfies some of the same axioms as the elementary substructure relation between models in first-order logic.

The study of AECs in a sense generalizes both infinitary logics like $L_{\omega_1, \omega}$ (where one is allowed to form countably infinite conjunctions and disjunctions) and the logic $L(Q)$ with a quantifier for "there exists uncountably many." For a recent and thorough exposition of all of this, you should look at John Baldwin's AMS monograph Categoricity, which is avaialbe here.

Answer by John Goodrick for Three questions on large simple groups and model theory

2010-07-27T03:36:50Z

Another example of an ultraproduct of simple groups which is not simple (somewhat sillier than Simon's): take some (any) nonprincipal ultraproduct of the finite cyclic groups $Z_p$ as $p$ ranges over all primes. This ultraproduct must be infinite, and abelian (since commutativity is an elementary property), but any infinite abelian group has a proper subgroup, hence it can't be simple.

(I say "sillier" than the alternating groups example since it seems like nobody cares about abelian simple groups, so Simon's answer deals with the natural follow-up question.)

OK, as for, "what are some general techniques for tackling a problem like this one," I'd first look at Theorem 4.1.12 of Chang and Keisler's Model Theory textbook: a class of structures is elementary if and only if it is closed under both ultraproducts and elementary equivalence. This seems relevant because ultraproducts, at least, seems like a relatively natural concept for algebraists, and depending on the particular class, you might hope to also find an algebraic definition of "elementarily equivalent."

Answer by John Goodrick for Geometric flavored textbook on algebra

2010-07-27T02:21:12Z

Confusingly, in addition to Emil Artin's Geometric Algebra mentioned by Anweshi, there is Michael Artin's textbook Algebra. The latter is more of a modern first-year graduate textbook covering the usual topics you'd find in a book like Lang, Dummit and Foote, and so on. I don't have Michael Artin's book handy but I remember a lot of it having a "geometric flavor," e.g. there was a lot of discussion of symmetry groups and linear representations.

This was one of the first abstract algebra books I read and I remember loving it at the time.

How are the two natural ways to define ''the category of models of a first-order theory T'' related?

2010-02-06T22:19:30Z

Background/Motivation: Inspired by an interesting question by Joel, I've been wondering about the relationship between two very natural ways to define the category of ''all models of T'' where T is a first-order theory.

Let us assume that T is a complete theory with infinite models. Then on the one hand we can define the category Mod(T) whose objects are all the models of T and whose morphisms are all homomorphisms in the sense of model theory -- i.e. functions $\varphi: M \rightarrow N$ such that

For any $n$-ary relation $R$ in the language of $T$, if $M \models R^M(a_1, \ldots, a_n)$, then $N \models R^N(\varphi(a_1), \ldots, \varphi(a_n))$;

and

$\varphi(f^M(a_1, \ldots, a_n)) = f^N(\varphi(a_1), \ldots, \varphi(a_n))$ for any $n$-ary function symbol $f$ in the language of $T$.

Also, one can define another category Elem(T) whose objects are also all the models of T, but whose morphisms are only the elementary embeddings, that is, functions which preserve the truth of all first-order formulas. As a model theorist, I'm more used to thinking about the category Elem(T), and this latter category arises naturally if one cares about which sets are definable but one does not particularly care about which sets are definable by positive quantifier-free formulas.

Question: What sorts of category-theoretic properties automatically transfer from Mod(T) to Elem(T), or from Elem(T) to Mod(T)?

To be clear, by a ``category-theoretic property'' I mean something that is preserved by an equivalence of categories.

Another related question is:

Question: Suppose we have a set of category-theoretic properties which we know characterize all the categories C which are equivalent to Mod(T) for some T [or to Elem(T) for some T]. Can we use this to characterize the categories which are equivalent to Elem(T) [respectively, Mod(T)] for some T?

Here are a couple of basic facts I know, which may or may not be useful here. First of all, every category Elem(T) is equivalent to a category Mod(T') for some other theory T' -- namely, the "Morleyization'' T' of T, where we expand the language by adding new predicates for every definable set (and iterating $\omega$ times), thereby forcing T' to have quantifier elimination. However, it is certainly not true that every category Mod(T) is equivalent to a category of the form Elem(T') -- for instance, Mod(T) might not have colimits of $\omega$-directed chains, but Elem(T) always will (by Tarski's elementary chain theorem).

Addendum: As Joel pointed out, there is a third possible notion of ''morphism'' for this category: the ``strong homomorphisms'' $\varphi: M \rightarrow N$ which commute with the interpretations of function symbols and have the property that for any $n$-ary relation $R$ in the language of $T$, $$M \models R^M(a_1, \ldots, a_n) \Leftrightarrow N \models R^N(\varphi(a_1), \ldots, \varphi(a_n)).$$

I'd also be interested to learn about any relationships between the category of models with strong homomorphisms and the other two categories above.

Bi-embeddability vs. isomorphism

2009-10-08T16:59:17Z

Can anybody give me an example of a "naturally-occurring" algebraic category C in which:

C has two non-isomorphic objects A and B which are bi-embeddable via monic maps; but
C does NOT have any infinite collection A_1, A_2, ... of objects which are pairwise bi-embeddable (via monic maps) and pairwise nonisomorphic?

Alternatively: can anybody give a reason why, under some reasonable hypothesis about the category C, property 1 should imply that 2 fails ("there is an infinite collection of pairwise bi-embeddable, pairwise nonisomorphic objects")?

Answer by John Goodrick for Choice vs. countable choice

2010-04-29T15:22:42Z

I have no idea who these alleged people are who are nervous about using full AC but not countable AC, but perhaps they (as you would put it) cannot fathom the following consequences of ZFC which are unprovable from ZF + countable choice:

-The existence of a nonmeasurable set of real numbers;

-The existence of a set of real numbers without the property of Baire;

-The Banach-Tarski paradox (that the unit ball in R^3 has a finite, pairwise-disjoint decomposition into subsets which can be reassembled, via isometries in R^3, into two identical copies of the original unit ball).

Answer by John Goodrick for Where's the notion of interpretation (model) originally introduced?

2010-03-07T21:44:14Z

Updated answer:

As best as I have been able to figure out, the pre-Tarskian notions of "semantics" in mathematical logic grew out of the "algebra of logic" introduced by Boole ("An investigation into the laws of thought," 1854, and some earlier papers) and elaborated by Charles Peirce, Schröder, and others.

It's difficult for me to follow all the arguments in the old papers, but roughly the idea behind Boole's logic was to study logical equations such as "$x + (1 - x) = 1$" or "$x \times (1 - x) = 0.$" Here, + means exclusive or, multiplication is "and," and subtracting $x$ means taking a conjunction with not-$x$. The number 1 should be interpreted as an always-true proposition, 0 as an always-false proposition, and $x$ as a propositional variable (or as Boole might say, a proposition with "indeterminate truth value").

Boole was interested in this analogy between logic an algebra, and here maybe we see the beginnings of the notion of interpretation in logic: we can check the validity of these formulas by considering whether they are true for all possible propositions $x$. (At least, I think this is what Boole meant -- you should track down the Dover reprinting of The Laws of Thought if you want to do some more historical investigation.)

Peirce considered the possibility of different "domains of individuals," which could be finite, infinite, or even uncountable. I think it was Peirce who first generalized Boole's calculus of logical propositions to the "calculus of relatives," where a "relative" is the interpretation of some $n$-ary predicate in a domain of individuals. To track down the beginnings of this, I would try Peirce's 1870 "Description of a notation for the logic of relatives," which unfortunately I cannot access right now from where I am.

Peirce, Schröder, and even Löweinheim in his 1915 "On possibilities in the calculus of relatives" continued to use algebraic notation along the lines of Boole, with many $0$'s and $1$'s. Even the "domain of individuals'' was denoted by $1^1$!

One thing in particular that is confusing about reading Löweinheim's paper is that, while he is clearly aware that the domain of individuals $1^1$ could be one of any number of possible collections of things (some finite, others infinite), he seems to insist on talking about "the domain of individuals $1^1$" and referring to every possible domain by the same name $1^1$! Obviously, this is confusing if you want to think about comparing two different such domains, and maybe one of Tarski's key contributions here was simply to introduce a notation ''$\mathfrak{A} \models \varphi$'' which explicitly names the universe $\mathfrak{A}$ and suggests comparison with other universes $\mathfrak{B}, \mathfrak{C}, \ldots$.

My original answer (missing the key point):

My knee-jerk answer to this question was going to be, "Tarski!" But you seem to already be aware of Tarski's work, so maybe you're looking for something different?

In particular: Alfred Tarski's 1933 article "The concept of truth in formalized languages" (in Polish, unfortunately) seems to be generally regarded as the first place where the concept of "logical satisfaction" (in the modern sense) was first defined.

There was already an "application" of semantic methods in logic by 1940: Gödel's proof of that Con(ZFC) implies Con(ZFC + GCH + AC). (It might be fun to try to find an even earlier application of semantic methods to prove a syntactic result.) Certainly by the 1960's the field of model theory was coming into its own with the work of A. Robinson, Vaught, Morley, and others.

Can a group be a finite union of (left) cosets of infinite-index subgroups?

2010-03-07T17:16:03Z

To be more precise (but less snappy): is there an example of a group G with finitely many infinite-index subgroups H_1, ..., H_n and elements k_1, ..., k_n such that G is the union of the left cosets k_1 H_1 , ..., k_n H_n? And what if we relax the requirement that these all be left cosets, and ask: can G be the union of finitely many such cosets, some being left cosets, others being right cosets?

If G is amenable then this can't happen, since any coset of an infinite-index subgroup must have measure 0. So this immediately rules out any abelian group G.

I've tried playing around with the only non-amenable groups that I'm comfortable with, the free groups on two or more generators. A few months ago I thought I found a simple counterexample in the free group on $\aleph_0$ generators, but now I've lost my notes and am beginning to doubt I ever had such an example.

(This question was asked to me by a friend who's interested in some kind of application to model theory, but I think it's interesting as a stand-alone puzzle.)

Answer by John Goodrick for Are there nonequivalent randomnesses?

2010-02-10T01:33:15Z

Short answer to the question in your title: yes, indeed, and a number of ~~recursion theorists~~ computability theorists have been busy investigating various notions of randomness for the past few years. For them, it seems that ``randomness'' is a notion that you apply to infinite sequences (say, of 0's and 1's), like Kolmogorov randomness -- but there is also ''Martin-Löf randomness'' and some other related notions.

This is far from my expertise, but here is a reasonable-looking survey article, and you can follow the references to find many other similar papers. My impression is that this has been a hot subfield of computability theory lately.

Answer by John Goodrick for What is the general opinion on the Generalized Continuum Hypothesis?

2010-02-06T21:25:56Z

My impression is that most mathematicians these days who work outside of mathematical logic would agree with the following statement: ``If at all possible, one should try to prove theorems within ZFC, or at least within ZFC plus some mild large cardinal axioms (e.g. the existence of inaccessible cardinals).''

I think this is even true in model theory, and I admit to having this bias myself -- partly because I generally want to prove things using as few hypotheses as possible, and partly just because ZFC is the system that I'm most used to. (I say this as someone who proved a result using Martin's Axiom in my thesis, and then was very happy when I later found a ZFC proof.)

To give an example of this attitude, in the 1970's pure model theory seemed to be getting more ''set theoretic,'' with natural statements such as Chang's Conjecture being proven to be independent of ZFC. I've heard that some model theorists were grateful to Shelah for demonstrating (in his 1978 book Classification Theory) that in fact there still were deep model-theoretic results that could be obtained in ZFC alone. The strategy was to define classes of well-behaved theories (e.g. the superstable theories) where one could prove within ZFC that the category of models is ''nice,'' and then show (again in ZFC) that the models of any theories not satisfying these tameness properties are ''as wild as possible.''

Answer by John Goodrick for Can we recognize when a category is equivalent to the category of models of a first order theory?

2010-01-28T18:27:10Z

For a long time, I've been thinking about this question for the category Mod*(T) of all models of T with elementary maps as morphisms (I'm putting an asterisk to distinguish it from Mod(T) in the original question). I still have more conjectures than answers about these categories, but I can say a few things about them. For example:

Proposition: If Mod*(T) is "linearly ordered" -- i.e. for any two M, N in Mod*(T), either M is embeddable into N, or vice-versa -- then Mod*(T) must have the Schroeder-Bernstein property (any two bi-embeddable models are isomorphic).

[Sketch of proof: First, note T must be complete. By a result of Shelah, T must be superstable -- otherwise, one of his constructions gives that there are many pairs of "incomparable" models neither of which can be embedded into the other. By some other results of Shelah from Classification Theory, we can deduce that T must be unidimensional (it cannot have a pair of orthogonal regular types) and omega-stable. But any omega-stable, unidimensional theory is categorical in aleph_1, and hence categorical in any uncountable cardinal by Morley's Theorem. By the Baldwin-Lachlan analysis of such theories, any model of T is determined up to isomorphism by a single cardinal-valued "dimension," and bi-embeddable models must have the same dimension, QED.]

I strongly suspect that there is some dichotomy result for Mod*(T) (and probably also for Mod(T)) saying that either it is extremely wild (e.g. as when T is unstable) or relatively "tame" (such as when T is uncountably categorical, and Mod*(T) is just a big tower, modulo isomorphisms). But I'm not sure what's the best way to make this precise.

As an example of the kind of dichotomy that may be true: I conjecture that if Mod*(T) does not have the Schroeder-Bernstein property, then in fact Mod*(T) contains an infinite collection of models which are pairwise bi-embeddable but pairwise nonisomorphic. I can prove this in some special cases (e.g. when T is weakly minimal) but not in general.

Answer by John Goodrick for Can infinite first-order categories be specified other than as categories of models?

2010-01-27T15:45:34Z

As for the OP's last question, "Is there a genuine model-theoretic notion of two equivalent theories if these have two arbitrary signatures:"

Sure, it's called bi-interpretability. See pp. 1378-1379 of this article for a definition of what this means for structures. For theories, we say that T_2 is interpretable in T_1 if there is a family of interpretation formulas (as in the linked definition) such that for any model M of T_1, these formulas define an interpretation in M of some model of T_2. Similarly, as above, we can define what it means for two theories to be bi-interpretable.

If you make the class of models of T into a category by declaring the morphisms to be the elementary embeddings (which seems very natural to me), then it follows directly from the definition that any two theories that are bi-interpretable (without parameters) have equivalent categories of models (via the natural "interpretation functors" which translate back and forth between the two languages). .

Answer by John Goodrick for Isomorphism types or structure theory for nonstandard analysis

2010-01-05T21:33:37Z

I think that the nonstandard models of R* will be fairly wild by most reasonable metrics, since the theory is unstable (the universe is linearly ordered). For instance, I don't think that arbitrary models will be determined up to isomorphism by well-founded trees of countable submodels (as they are in ``classifiable'' theories).

EDIT: I'm not sure how many nonisomorphic models there are of cardinality c (the size of the continuum), but there are 2^{2^c} distinct nonisomorphic nonstandard models of theory of R* of size 2^c. A crude counting argument shows that this is the maximum number of nonisomorphic models of size 2^c that any theory with a language of cardinality 2^c could possibly have, which can be considered as evidence that the class of models of the theory of R* is ``wild.''

(This result follows from the proof of Theorem VIII.3.2 of Shelah's Classification Theory, one of his ``many-models'' arguments about unclassifiable theories. In fact, an argument from the second chapter of my thesis applied to this theory shows that you can even build a collection of 2^{2^c} models of size 2^c which are pairwise bi-embeddable but pairwise nonisomorphic.)

It's a good question whether or not you can have two models of this theory which are order-isomorphic but nonisomorphic -- there must be somebody studying o-minimal structures with an answer to this.

Answer by John Goodrick for What are some results in mathematics that have snappy proofs using model theory?

2009-12-25T00:01:59Z

You can find lots of other applications just by browsing the titles of the papers on the MODNET preprint server (follow this link and look under "Publications" on the left side of the page). For example:

"The monomorphism problem in free groups", by L. Ciobanu and A. Ould Houcine (in which they show it is decidable);
"An invitation to model-theoretic Galois theory," by A. Medvedev and Ramin Takloo-Bighash -- expository paper explaining how the Galois correspondence can be explained using model theoretic tools;
"On algebraic closure in pseudofinite fields," by O. Beyarslan and E. Hrushovski;

etc.

Also, there is a recent book Model Theory with Applications to Algebra and Analysis: v. 1 (LMS Lecture Note series v. 349, Cambridge, 2008) which would probably be very relevant (judging by the table of contents -- unfortunately I haven't had a chance to read it yet).

Answer by John Goodrick for What are some results in mathematics that have snappy proofs using model theory?

2009-12-24T19:27:20Z

For a particular result in analysis with a snappy non-standard proof, there's this proof of the Bieri-Groves Theorem on tropical amoebas. (Does this count as "analysis"? I'm not sure.)
There are some nice applications of model theory to [differential Galois theory],[2] partly due to the fact that the complete theory of differentially closed fields of characteristic zero happens to have extremely nice model theoretic properties (it's omega-stable, hence there nice rank functions on definable sets and unique-up-to-isomorphism prime models over any set of parameters).

Answer by John Goodrick for Pedagogical question about linear algebra

2009-12-20T18:32:01Z

You could try giving the following example: the set of all positive real numbers, considered as a vector space over the field R, with vector addition given by multiplication and scalar multiplication given by taking exponents.

As a first step, you could verify that this satisfies a few of the vector-space axioms, and then let students check the rest of them (say, as homework). Then, you could ask questions like, "what is the dimension of this vector space?" or, "give an example of a (nontrivial) linear transformation from this space into R^3."

Answer by John Goodrick for categorification of logic

2009-12-18T22:18:02Z

You many also want to look at the work of Michael Makkai on [accessible categories].[1] My best understanding is that these are an attempt to generalize categories of models of first-order theories by distilling their essential category-theoretic properties.

(Perhaps this is essentially the same as Mike Shulman's project? To be honest, my knowledge of categorial logic is very limited, mostly I'm just aware that it exists, and its flavor seems to be more category-theoretic than logical so it's hard for me to digest.)

Also possibly relevant are some of the papers on Makkai's webapge:

http://www.math.mcgill.ca/makkai/

Answer by John Goodrick for What is a logic ?

2009-12-14T20:32:04Z

Are you familiar with Lindström's theorems?

You can define a "logic" L by giving the collection EC(L) of all classes of models which are "L-axiomatizable," and we assume that EC(L) has a few nice closure properties (closure under finite intersections, taking complements within the class of all structures with a given signature, closure under taking reducts to smaller signatures, and isomorphism invariance).

Say that a logic L_2 is stronger than a logic L_1 iff every class in EC(L_1) is also in EC(L_2). Then one of Lindström's theorems says that any logic which is stronger than first-order logic and satisfies the compactness theorem and Löwenheim-Skolem must be the same as first-order logic. (See Ebbinghaus and Flum's Mathematical Logic, chapter 12, for a proof.)

This doesn't seem to apply directly to your question about modal and linear logics, but at least for modal logics, people have worked on generalizing Lindström's results, e.g. here:

http://users.soe.ucsc.edu/~btencate/papers/lics2007full.pdf

Answer by John Goodrick for Alternative axiom to induction

2009-12-14T01:29:53Z

A crucial difference between non-Euclidean geometries and "non-inductive" models of PA- is that any model of PA- contains a canonical copy of the true natural numbers, and in this copy of N, the induction schema is true. In other words, PA is part of the complete theory of a very canonical model of PA-, and as such it seems much more natural (so to speak) to study fragments of PA rather than extensions of PA- which contradict induction.

To make this a little more precise (and sketch a proof), the axioms of PA- say that any model M has a unique member 0_M which is not the successor of anything, and that the successor function S_M: M to M is injective; so by letting k_M (for any k in N) be the k-th successor of 0_M, the set {k_M : k in N} forms a submodel of M which is isomorphic to the usual natural numbers, N. Any extra elements of M not lying in this submodel lie in various "Z-chains," that is, infinite orbits of the model M's successor function S_M.

(In the language of categories: the "usual natural numbers" are an initial object in the category of all models of PA-, where morphisms are injective homomorphisms in the sense of model theory.)

So, while PA seems natural, I'm not sure why there would be any more motivation to study PA- plus "non-induction" than there is to study any of the other countless consistent theories you could cook up, unless you find that one of these non-inductive extensions of PA- has a particularly nice class of models.

Answer by John Goodrick for Tropicalizing the learning

2009-12-03T16:37:44Z

Recently, M. Aschenbrenner, D. Lippel, and S. Starchenko used a nonstandard analysis approach to reprove a basic theorem in the subject (the Bieri-Groves Theorem relating tropical varieties to tropical amoebas). Here is a nice outline of the argument, which is elementary and completely free of contemporary-style algebraic geometry.

Caveat: I know very little about tropical geometry and I have no idea whether these model-theoretic methods can be pushed further to prove other results in the field.

Answer by John Goodrick for Model theoretic applications to algebra and number theory(Iwasawa Theory)

2009-11-29T00:37:13Z

It's hard for me to think of an area of algebra that applied model theorists haven't touched recently. I have not heard of any logicians working on Iwasawa theory, but it wouldn't surprise me if there are some.

Diophantine geometry: here is a survey article by Thomas Scanlon on applications of model theory to geometry, including discussions of Mordell-Lang and the postivie-characteristic Manin-Mumford conjecture.

Number fields: Bjorn Poonen has shown that there is a first-order sentence in the language of rings which is true in all finitely-generated fields of characteristic 0 but false in all fields of positive characteristic. It was conjectured by Pop that any two nonisomorphic finitely-generated fields have different first-order theories.

Polynomial dynamics: see here for a recent preprint by Scanlon and Alice Medvedev. It turns out that first-order theories of algebraically closed difference fields where the automorphism is "generic" are quite nice.

Differential algebra: By some abstract model-theoretic nonsense ("uniqueness of prime models in omega-stable theories"), it follows that any differential field has a "differential closure" (in analogy to algebraic closure) which is unique up to isomorphism over the base field. There are much more advanced applications, e.g. here.

Geometric group theory: Zlil Sela has recently shown that any two finitely-generated nonabelian free groups are elementarily equivalent (i.e. they have the same first-order theory). According to the wikipedia article, this work is related to his solution of the isomorphism problem for torsion-free hyperbolic groups, but I don't understand this enough to say whether this counts as an "application" of model theory.

Exponential fields: Boris Zilber has suggested a model-theoretic approach to attacking Schanuel's Conjecture. His conjecture that the complex numbers form a "pseudo-exponential field" is actually a strengthening of Schanuel's Conjecture, but the picture that it suggests is appealing. See here for more.

This is in addition to the work on Tannakian formalism, valued fields, and motivic integration that have already been mentioned in other answers, and I haven't even gotten to all the work by the model theorists studying o-minimality. This was just a pseudo-random list I've come up with spontaneously, and no offense is meant to the areas of applied model theory that I've left off of here!

Answer by John Goodrick for A problem of an infinite number of balls and an urn

2009-11-29T00:52:53Z

Thinking about these kinds of problems has convinced me that it may be quite reasonable to assume that there's an absolute bound on how fast an object can travel. Or at least, that this is more "intuitive" than the alternative.

Answer by John Goodrick for How to respond to "I was never much good at maths at school."

2009-11-13T15:04:01Z

Like Scott Carter, I sometimes say something like: "I was never any good at [e.g.] writing essays..."

"I was never any good at math(s)" always makes me feel funny because usually the speaker is angling for some kind of commiseration which I simply cannot provide. So I try to change the subject as quickly as possible.

Answer by John Goodrick for How does one identify properties of objects with good "inheritance"?

2009-11-10T14:38:03Z

In first-order logic, some of the most natural inheritance properties have been studied.

First, you should recall what a substructure means in the sense of model theory -- basically just that you're closed under all the operations of the bigger structure, and the interpretation of any relational symbols in your language agrees on tuples common to the two structures. (I'm using the "non-weak" sense in the link I provided.)

A first-order axiomatizable class of structures is closed under substructures if and only if it can be axiomatized by a set of universal sentences (of the form: , where phi is quantifier-free). Think of groups (in a language with a function symbol for inverses) or ordered groups.

A first-order axiomatizable class of structures is closed under superstructures if and only if it can be axiomatized by a set of existential sentences (, with phi quantifier-free).

An axiomatizable class of structures is closed under unions of ascending chains of superstructures if and only if it can be axiomatized by a set of "AE-sentences," of the form with phi quantifier-free. Think of fields in the language with only the symbols for 0, 1, and the two field operations: the axiom expressing that every element has a muliplicative inverse is AE.

Inheritance under products in first-order logic is trickier. Any class that can be axiomatized by first-order Horn sentences is closed under products, but the converse is false, and I've never heard of a good syntactic characterization of such classes. (I think this is why logicians are so fond of ultraproducts, which automatically preserve the truth of all first-order sentences!)

I'm not sure how useful these results actually are, since many (most?) properties that algebraists care about are not first-order axiomatizable. E.g. the class of all Noetherian rings is not axiomatizable (by the compactness theorem).

Comment by John Goodrick

2010-10-04T18:16:28Z

@Diego: Offhand, I don't know of a "categorical" proof of the Myhill isomorphism theorem, whatever this would mean (I'm not saying that there isn't one, but I don't know of one). To be clear, I didn't mean that "classifiability by a bounded set of cardinal invariants" is necessary to have S-B in your category, just that it is (with a suitable interpretation of the terms) a sufficient condition for S-B.

Comment by John Goodrick

2010-09-18T06:58:40Z

@Andrés: I wonder if anyone has defined an easy-to-classify/hard-to-classify boundary for axiomatizable classes of finite structures? I can't recall hearing about such a thing, but it could be interesting if it exists.

Comment by John Goodrick

2010-09-17T19:28:52Z

And I guess this argument generalizes to n-dimensional projections of convex (n+1)-dimensional objects when n is at least 2?

Comment by John Goodrick

2010-09-15T19:38:07Z

@François: I think that "the dope" in the English translation of Cours de théorie des modèles comes from French "la DOP", from English "DOP" (Dimensional Order Property), which is a Shelahian term. I think the story here is that the French-to-English translator wasn't familiar with the English word for the concept...

Comment by John Goodrick

2010-09-06T19:51:58Z

Even as a model theorist, unfortunately I have to disagree with "Most categories we encounter in real life..." (Noetherian rings? Locally ringed spaces? CW complexes? Etc.)

Comment by John Goodrick

2010-09-04T03:25:29Z

I presume Väänänen meant computational complexity, that is, computability? In fact, it's hard for me to imagine an interesting formulation of Godel's incompleteness that doesn't involve computability: you could just say that PA is incomplete, but that seems too localized to be interesting; or there's the cocktail-party version that "arithmetic can't be axiomatized" which, taken literally, is false (just take the set of all sentences true in the structure (N, +, times)).

Comment by John Goodrick

2010-09-03T23:04:35Z

@Joel: OK, I just inserted a parenthetical comment into the answer explaining that part.

Comment by John Goodrick

2010-09-03T15:27:41Z

When computing the "rank of a structure" such as N, do you mean the rank of the domain N, or the rank of the ordered tuple (N, +, times) of the domain plus the operations? The rank of the latter will be greater than omega.

Comment by John Goodrick

2010-08-25T19:48:15Z

Getting back a positive referee report within two weeks of submission to math journal would be a pleasant shock to me... (Maybe things ought to be different, but this seems to be pretty far from the present community standard.)

Comment by John Goodrick

2010-08-19T16:31:30Z

@Dave: Do you have examples of order types which are dense, without endpoints, and 2-homogeneous (any two increasing pairs (a,b) and (c,d) are in the same orbit of the order-automorphism group), but which could not be the reduct of a real-closed field?

Comment by John Goodrick

2010-08-06T19:13:00Z

Just a small quibble (since I don't have much to add to the answers of Andreas and Carl): you probably shouldn't talk about "the axioms for the integers," since there are many different (partial) axiomatizations of this structure (e.g. Q, PA, PA^_ plus Delta-0 induction, ...), none of which is particularly canonical. (Well, OK, the complete theory of (N, +, times) is canonical, but that's cheating.)

Comment by John Goodrick

2010-08-03T18:34:43Z

@Sergei: OK, I see. This makes sense, but I don't think this terminology is currently standard.

Comment by John Goodrick

2010-08-03T18:32:52Z

+1. And if you look in many standard introductory logic texts (e.g. Enderton's), you can find theorems stating that these two approaches are equivalent (I think this fact is usually called "generalization over constants").

Comment by John Goodrick

2010-08-03T18:12:21Z

I know what it means for a deductive system or a set of axioms to be complete, but what does it mean for a logic to be complete? Does this mean that there exists a deductive system which is strong enough to produce all tautologies, and for which one can computably check whether or not a finite string is a valid proof?

Comment by John Goodrick

2010-07-27T03:06:17Z

"...assume no friction..." So you have braking rockets on the hood of your car?