MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's start with some family of algebraic structures of the same type indexed by the natural numbers, say the symmetric group $S_n$. Suppose that the axioms of this algebraic structure (in this case, groups) can be stated within the framework of first-order logic. In this way, we can consider a structure $M$ defined as follows: it contains $\mathbb{N}$, as well as all the $S_n$. Consider the complete theory $Th(M)$ in first-order logic (i.e. containing all the symbols of $M$ and a symbol for each relation on $M$ of any arity).

In this theory, there are relations $m, e, i$ that correspond to the relations of multiplication, identity, and inverse, and a relation $P$ such that $P(a,b)$ iff $a \in S_n$ and $b = n$. There are a bunch of axioms that are satisfied, e.g. if $P(a,b)$ then $P( i(a), b)$ and $m( a, i(a)) = e(b)$, etc., that correspond to the group laws. There is also a relation $isParameter$ that tells you whether the object in question is a parameter (i.e. a natural number).

So, in this way (am I misunderstanding this?) one can use an ultraproduct construction (or the compactness theorem applied to $Th(M)$ together with the collection of sentences $isParameter(c) \wedge c> 1 + \dots + 1$ where $c$ is some new constant symbol) to embed $M$ in a bigger structure $M'$ where there are parameters greater than all the standard elements of $\mathbb{N}$, i.e. where the parameters are (some version of) the hypernatural numbers. Since the group $S_n$ is nonempty for each standard $n$, it should follow by transfer that $S_n$ is also defined for infinite $n$. It must be a group by transfer.

Question: Is $S_{n}$ for infinite $n$ in any way related to the set of permutations of the interval from $1$ to $n$? If not, what can we say about it?

My hunch is that this probably isn't the case, because "every permutation is contained in $S_n$" sounds like a second-order statement and this is first-order logic we're dealing with. Nevertheless, I'm curious about what we can say about $S_{n}$ for infinite $n$, and whether we can deduce additional properties about $S_n$ for infinite $n$ from the known theory for finite $n$.

share|cite|improve this question
up vote 4 down vote accepted

You can build your group directly as an ultraproduct without fussing about the particular language. Namely, let U be any nonprincipal ultrafilter on ω, and let S be the ultraproduct Πn Sn/U. That is, one defines f ≡ g in the product Π Sn if and only if { n | f(n) = g(n) } ∈ U. This is an equivalence relation, and the ultraproduct is the collection of equivalence classes [f], where the algebraic structure is well-defined coordinate-wise. Los's theorem then states that S will satisfy a statement about [f] in the language of groups if and only if the set of n for which f(n) has the property in Sn has the property is in U. For example, S will have elements of infinite order, since we can let f(n) select an element of Sn of order n, and then observe that for any fixed k, the set of n for which f(n) has order at least k is co-finite and hence in U. As Gerald observed, S is not itself a full symmetric group, since one will never be able to define the standard/nonstandard cut.

But let me describe a more general way to accomplish what you want, for all kinds of structures simultaneously. There is little reason when taking ultraproducts to restrict to any particular structure. Rather, one should simply consider the ultrapower of the entire set-theoretic universe V. This results in a new set-theoretic universe W = Vω/U that satisfies all the truths about any [f] that are true of f(n) in V on a set in U. In particular, S is the just [⟨ Sn | n ∈ ω ⟩] in the universe W. (What this shows is that ultraproducts of any set structures are elements of the ultrapower of the universe, and in this sense, ultraproducts are a special case of ultrapowers, although one usually hears the converse.) With this construction, we are not limited to the language of group theory when discussing properties of your group S, and we can freely refer to properties involving subgroups, group extensions and whatever else is expressible in set theory. If almost every Sn (that is, on a set in U) has some property expressible in set theory, then S will have this property in W. Thus, the group S is a "finite" permutation group inside W on the nonstandard natural number N represented by the identity function id(n) = n. That is, W thinks that S is just SN, where N = [id]. So any property that you can prove about all Sn, will be true of S in W. Some but not all of these properties are absolute between W and V, and it is often interesting to compare the differences.

What this shows is that there IS a sense in which your group S is a full group of permutations on a set, because it is the group of all permutations on N inside W. That is, it is a full symmetric group inside the alternative set-theoretic universe W, rather than in the original universe V. In particular, Gerald's counterexample permutation does not exist in W, since W also cannot define the standard/nonstandard cut.

share|cite|improve this answer
And there is then only a small step from the ultrafilter construction described by Joel to topos theory... – Andrej Bauer Mar 4 '10 at 13:47
Thanks! This is helpful. – Akhil Mathew Mar 4 '10 at 21:17
@Andrej: Do you have a reference for the connection topos theory? – Akhil Mathew Mar 4 '10 at 21:18

Of course you don't get ALL permutations, as the usual reasoning for non-standard arithmetic shows. For example, the permutation: "exchange 2k and 2k+1 if k is finite and fix k if k is infinite" cannot occur.

"In any way related..." is that an MO-qualified question?

share|cite|improve this answer
Oh yes, you're right. That was silly on my part. And I agree that it wasn't a very good question. After I actually learn something about logic I may be able to ask a better one. – Akhil Mathew Mar 4 '10 at 21:19
It's funny, I should have been able to realize what you said about "exchange 2k and 2k+1" being inadmissible just after the reading I did today... – Akhil Mathew Mar 4 '10 at 21:21

Your Answer


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.