User simon thomas - MathOverflow

Ultrafilters and automorphisms of the complex field

2010-05-09T21:00:21Z

It is well-known that it is consistent with $ZF$ that the only automorphisms of the complex field $\mathbb{C}$ are the identity map and complex conjugation. For example, we have that $|Aut(\mathbb{C})| = 2$ in $L(\mathbb{R})$. But suppose that we are given a nonprincipal ultrafilter $\mathcal{U}$ over the natural numbers $\mathbb{N}$. Is there any way to use $\mathcal{U}$ to define a third automorphism of $\mathbb{C}$?

Some background ... the "obvious" approach would be to note that the ultraproduct $\prod_{\mathcal{U}} \bar{\mathbb{F}}_{p}$ of the algebraic closures of the fields of prime order $p$ has lots of automorphisms arising as ultraproducts of Frobenius automorphisms. Of course, working in $ZFC$, this ultraproduct is isomorphic to $\mathbb{C}$ and hence we obtain many "strange " automorphisms of $\mathbb{C}$. However, the isomorphism makes heavy use of the Axiom of Choice and these fields are not isomorphic in $L(\mathbb{R})[\mathcal{U}]$. So a different approach is necessary if we are to find a third automorphism of $\mathbb{C}$ just in terms of $\mathcal{U}$ ...

Edit: Joel Hamkins has reminded me that I should mention that I always assume the existence of suitable large cardinals when I discuss properties of $L(\mathbb{R})$ and $L(\mathbb{R})[\mathcal{U}]$. For example, if $V = L$, then $L(\mathbb{R}) = L= V$ and so $L(\mathbb{R})$ is a model of $ZFC$. Of course, nobody would dream of studying $L(\mathbb{R})$ under the assumption that $V = L$ ...

Answer by Simon Thomas for counting non-isomorphic groups of a given cardinality

2012-04-25T01:46:22Z

If you just want a direct construction which avoids nontrivial set theory such as stationary sets etc., how about this?

Step One: For each subset $S \subseteq \kappa$, let $M(S)$ be the structure $\langle \kappa; < , S \rangle$, where $S$ is regarded as a unary relation. Obviously, if $S \neq T$, then $M(S)$ and $M(T)$ are non-isomorphic.

Step Two: For each subset $S \subseteq \kappa$, encode $M(S)$ into a corresponding graph $\Gamma(S)$ so that if $S \neq T$, then $\Gamma(S)$ and $\Gamma(T)$ are non-isomorphic. (This is an easy exercise.)

Step Three: For each subset $S \subseteq \kappa$, encode the graph $\Gamma(S)$ into a suitable group $G(S)$ with generators $\Gamma(S)$ and relations $R(S)$ which encode the adjacency relation. (This can be done using small cancellation theory.)

Answer by Simon Thomas for Free groups as quotients of hyperbolic groups

2012-04-21T14:10:00Z

There exist hyperbolic groups $G$ with the Kahzdan property. Since every quotient of $G$ also has the Kahzdan property, it follows that $G$ has no nonabelian free quotients.

Answer by Simon Thomas for Amenability and ultrafilters

2012-04-19T17:09:56Z

Of course, $ZF$ is enough to prove that $\mathbb{Z}$ has a Folner sequence. But, as you point out, $ZF$ is not enough to prove that $\mathbb{Z}$ has an invariant mean. Thus $ZF$ does not prove the equivalence of A1 and A2.

On the other hand, the Hahn-Banach Theorem is enough to prove the equivalence of A1 and A2 for countable discrete groups and Pincus-Solovay have constructed a model of $ZF$ in which the Hahn-Banach Theorem is true but there are no nonprincipal ultrafilters on $\mathbb{N}$. Hence the equivalence of A1 and A2 for countable groups does not imply the existence of nonprincipal ultrafilters on $\mathbb{N}$.

Answer by Simon Thomas for Example of two structures

2011-11-29T19:15:25Z

For each $n \geq 1$, let $F_{n}$ be the free group on $n$ generators and let $\mathbb{Q}^{n}$ be the direct product of $n$ copies of the additive group of the rationals. Since $\mathbb{Q}^{2} \equiv \mathbb{Q}$ and $F_{2} \equiv F_{3}$, it follows that $F_{2} \times \mathbb{Q}^{2} \equiv F_{3} \times \mathbb{Q}$. Clearly $F_{3} \times \mathbb{Q}$ embeds into $F_{2} \times \mathbb{Q}^{2}$ and it is easily seen that $F_{2} \times \mathbb{Q}^{2}$ does not embed into $F_{3} \times \mathbb{Q}$. On the other hand, using the proof that elementary subgroups of free groups are free factors, it follows that $F_{3} \times \mathbb{Q}$ cannot be elementarily embedded into $F_{2} \times \mathbb{Q}^{2}$.

Just for fun, I will also show that there exists an uncountable family of pairwise non-embeddable elementarily equivalent finitely generated simple amenable groups ... but fail to provide a single explicit example of a pair of such groups. Let $\mathcal{G}$ be the Polish space of f.g. groups. Using recent work of Grigorchuk-Medynets, there exists a Borel reduction $\varphi: 2^{\mathbb{N}} \to \mathcal{G}$ from $E_{0}$ to $\cong$; say, $x \mapsto G_{x}$. Let $L$ be the language of group theory and let $\psi: \mathcal{G} \to \mathcal{P}(L)$ be the Borel map $G \mapsto Th(G)$. Then there exists a fixed complete theory and a comeagre $X \subseteq 2^{\mathbb{N}}$ such that $Th(G_{x}) = T$ for all $x \in X$. Consider the Borel subset $Z = \varphi(X) \subseteq \mathcal{G}$. Define a Borel coloring $\theta: [Z]^{2} \to 2$ by $\theta(G,H) = 0$ iff $G$, $H$ are incomparable with respect to embeddability. Then there exists a Cantor set $C \subseteq Z$ such that $\theta$ is constant on $[C]^{2}$. Since each f.g. group has only countably many f.g. subgroups, it follows easily that $C$ is an uncountable family of pairwise non-embeddable elementarily equivalent finitely generated simple amenable groups.

Answer by Simon Thomas for Connes' embedding conjecture for uncountable groups

2011-11-06T21:56:50Z

A partial answer to Alain's question ... Suppose that the Continuum Hypothesis $CH$ holds. Let $G$ be any group of size $2^{\aleph_{0}} = \aleph_{1}$. Then there exists a countable subgroup $H$ of $G$ with the same first order theory $T$. Let $\Gamma = \prod_{\mathcal{U}} H_{n}$ be the ultraproduct such that every $H_{n} = H$. Then $CH$ implies that $\Gamma$ is a saturated model of $T$ and hence $G$ embeds into $\Gamma$.

Your question concerning the possibility of embedding groups $G$ with $|G| \leq 2^{\aleph_{0}}$ into ultraproducts $\prod_{\mathcal{U}} H_{n}$ over a countable index set might be interesting in the case when $CH$ fails. There is a similar open problem concerning sofic groups. It is an easily seen that every group is sofic iff $Sym(\mathbb{N})$ embeds in some universal sofic group. However, even if every group is sofic, it is not clear whether or not $Sym(\mathbb{N})$ embeds in a universal sofic group arising from an ultrafilter over $\mathbb{N}$.

If you are interested in embeddings using ultraproducts over larger index sets, then you can make use of an ancient result of Malcev, which says that every group $G$ embeds into a suitable ultraproduct of its finitely generated subgroups. Here the index set $I$ is the set of its finitely generated subgroups, which is uncountable if $G$ is uncountable.

PS: In Shelah's paper on ultraproducts, he mentions that if Martin's Axiom holds, then there exists an ultrafilter $\mathcal{D}$ over $\mathbb{N}$ such that for every countable structure $M$ for a countable language, the corresponding ultraproduct $\prod_{\mathcal{D}}M$ is saturated. In particular, it is consistent with the failure of $CH$ that every group $G$ with $|G| \leq 2^{\aleph_{0}}$ embeds into an ultraproduct $\prod_{\mathcal{U}} H_{n}$ over a countable index set.

Answer by Simon Thomas for SQ-universality in the class of amenable groups

2011-09-25T01:35:07Z

Here's what you were looking for:

MR2254627 (2007k:20086) Erschler, Anna(F-PARIS11-M) Piecewise automatic groups. (English summary) Duke Math. J. 134 (2006), no. 3, 591–613. 20F65 (20F69 43A07 57M07)

"The main result of the paper under review is stated as follows: For any function f:N→N there exists a finitely generated group of an intermediate group (and thus amenable) whose Følner function satisfies FølG,S(n)≥f(n) for all sufficiently large n."

HNN Embedding Theorem for Amenable Groups?

2010-07-05T19:30:29Z

Does there exist an analog of the HNN Embedding Theorem for the class of countable amenable groups? In other words, is it true that every countable amenable group embeds into a 2-generator amenable group? Perhaps easier, is it true that every countable amenable group embeds into a finitely generated amenable group?

Answer by Simon Thomas for Two-cardinal models of the random graph

2011-07-23T07:55:06Z

MR1889546 (2003e:03064) Cherlin, Gregory(1-RTG); Thomas, Simon(1-RTG) Two cardinal properties of homogeneous graphs. (English summary) J. Symbolic Logic 67 (2002), no. 1, 217–220. 03C30 (03C65 05C99)

The main result of the paper is the following theorem: If G is the Rado graph or the generic $K_{n}$-free graph, and $\kappa \leq \lambda$ are infinite cardinals, then the following are equivalent: (1) $\lambda \leq 2^{\kappa}$; (2) there is a graph $G^{\prime}$ elementarily equivalent to G of cardinality λ and a vertex $v\in V(G^{\prime})$ for which |Δ(v)|=κ; (3) there is a graph $G^{\prime}$ elementarily equivalent to G of cardinality λ and a vertex $v\in V(G^{\prime})$ for which |Δ′(v)|=κ. (Here Δ(v) is the set of neighbors of v in G∗, and Δ′(v) is its complement.)

Answer by Simon Thomas for an algebraically closed field definable in a real closed field

2011-04-30T19:44:48Z

Suppose that $A$ is an infinite definable subset of a real closed field $R$ which is a zero-divisor-free ring under operations whose graphs are definable in $R$. Then $A$ is definably isomorphic to one of $R$, $R(\sqrt{-1})$ or the ring of quaternions over $R$. This is a special case of the main result of:

Otero, Peterzil, and Pillay, On groups and rings definable in o-minimal expansions of real closed fields, Bull. London Math. Soc. 28 (1996), no. 1, 7–14.

Answer by Simon Thomas for Codimension of Measurable Sets

2011-02-13T13:31:03Z

In 1917, Lusin and Sierpinski showed that the unit interval $[0,1]$ can be partitioned into $2^{\aleph_{0}}$ many pairwise disjoint sets each having Lebesgue outer measure 1; say, $X_{i}$, $i \in I$. Fix $i_{0} \in I$. For each proper subset $J$ with $i_{0} \notin J \subset I$, let $S_{J} = \bigcup_{j \in J} X_{j}$. Then the sets $S_{J}$, $i_{0} \notin J \subset I$, are distinct modulo $\mathcal{M}$.

Nikolai N. Lusin and Waclaw Sierpinski, “Sur une décomposition d’un intervalle en une infinité non dénombrable d’ensembles non mesurables” [On a decomposition of an interval into a nondenumerably many nonmeasurable sets], Comptes Rendus Académie des Sciences (Paris) 165 (1917), 422-424.

Answer by Simon Thomas for Regularity of asymptotic cones

2010-11-14T12:59:19Z

Drutu has shown that if every asymptotic cone of the finitely generated group $G$ is a proper space, then $G$ has polynomial growth; and hence by Gromov's Theorem, it follows that $G$ is nilpotent-by-finite. It seems to be open whether or not the conclusion holds if just one asymptotic cone of $G$ is proper.

Folner sequences of amenable groups of exponential growth

2010-10-28T11:56:02Z

Let $G$ be an amenable group of exponential growth and let $S$ be a finite symmetric generating set. For each $k$, let $B_{k}$ be the closed ball of radius $k$ about the identity element in the corresponding Cayley graph of $G$ and let $b_{k} = |B_{k}|$. If $\lim b_{k+1}/b_{k}$ exists, then $\lim b_{k+1}/b_{k} = \lim b_{k}^{1/k} > 1$ and this easily implies that no subsequence of the $B_{k}$ forms a Folner sequence for $G$. But is this also true for those amenable groups of exponential growth for which $\lim b_{k+1}/b_{k}$ does not exist?

Answer by Simon Thomas for Centralisers of transitive permutation groups

2010-10-04T12:38:39Z

Of course, there is the classical result that $C_{Sym(n)}(G)$ is a semi-regular subgroup of $Sym(n)$ of cardinality $|Fix(G_{0})|$, where $G_{0}$ is the stabilizer of a point and $Fix(G_{0})$ is the set of points fixed by $G_{0}$.

Answer by Simon Thomas for Groups as automorphism groups of small graphs and the number of rigid graphs of a given size

2010-09-01T17:02:35Z

It is well-known that every infinite group $G$ can be realized as the automorphism group of a graph of size $|G|$. It is also well-known that for each infinite cardinal $\kappa$, there are $2^{\kappa}$ nonisomorphic rigid graphs of size $\kappa$. For example, both results are easily extracted from Section 4.2 of the following unpublished book:

http://www.math.rutgers.edu/~sthomas/book.ps

Answer by Simon Thomas for Is non-connectedness of graphs first order axiomatizable?

2010-08-29T12:54:10Z

The class of non-connected graphs is not axiomatizable. To see this, consider $\mathbb{Z}$ as a graph with $i$, $j$ connected by an edge if and only if $|i-j|=1$. Then a simple compactness argument yields a non-connected graph $\Gamma$ such that $\Gamma$ is elementarily equivalent to $\mathbb{Z}$; ie $\Gamma$ and $\mathbb{Z}$ satisfy precisely the same first order sentences. Since $\mathbb{Z}$ is connected and $\Gamma$ is non-connected, the result follows.

Answer by Simon Thomas for Criteria for Aut(G) to be simple

2010-08-26T21:42:42Z

Obraztsov has shown that if $p$ is a sufficiently large prime, then there exists a finitely generated infinite simple complete group $G$, all of whose proper subgroups are cyclic of order $p$. In particular, $G$ is an example of a group such that $Aut(G)$ is an infinite simple group. The relevant reference is:

V. N. OBRAZTSOV, `On infinite complete groups', Comm. Algebra 22 (1994) 5875--5887

Answer by Simon Thomas for Is there any criteria for whether the automorphism group of G is homomorphic to G itself?

2010-08-20T10:55:23Z

There does not exist a reasonable necessary and sufficient condition for an infinite centerless group to be complete. More precisely, letting $V$ be the set-theoretic universe, there exists an infinite complete group $G \in V$ and a $c.c.c$ notion of forcing $\mathbb{P}$ such that $G$ has an outer automorphism in the generic extension $V^{\mathbb{P}}$. An example can be found in :

S. Thomas, The automorphism tower problem II, Israel J. Math. 103 (1998), 93-109.

In fact, it can be shown that the group $G$ in this paper satisfies the stronger property that $G \not \cong Aut(G)$ as abstract groups in $V^{\mathbb{P}}$. In other words, there does not even exist a ''non-canonical isomorphism''.

For more on the ``nonabsoluteness'' of the height of automorphism towers, see:

J. Hamkins and S. Thomas, Changing the heights of automorphism towers, Annals Pure Appl. Logic 102 (2000), 139-157.

On the size of balls in Cayley graphs

2010-08-19T21:08:44Z

Next semester I will be teaching an introductory course on geometric group theory and there is a basic question that I do not know the answer to. Let $G$ be a finitely generated group with finite symmetric generating set $S$ and let $\Gamma$ be the corresponding Cayley graph. For each $n \geq 1$, let $B_{n}$ be the closed ball of radius $n$ in $\Gamma$ about the unit element $e$ and let $b_{n} = |B_{n}|$. Then it is known that $\lim b_{n}^{1/n}$ always exists. (For example, see de la Harpe's book.) My question is whether $\lim b_{n+1}/b_{n}$ always exists?

Answer by Simon Thomas for Three questions on large simple groups and model theory

2010-07-22T07:06:11Z

The class of simple groups isn't elementary. To see this, first note that if it were, then an ultraproduct of simple groups would be simple. But an ultraproduct of the finite alternating groups is clearly not simple. (An $n$-cycle cannot be expressed as a product of less than $n/3$ conjugates of $(1 2 3)$ and so an ultraproduct of $n$-cycyles doesn't lie in the normal closure of the ultraproduct of $(1 2 3)$. )

It turns out that an ultraproduct $\prod_{\mathcal{U}} Alt(n)$ has a unique maximal proper normal subgroup and the corresponding quotient $G$ is an uncountable simple group. This group $G$ has the property that a countable group $H$ is sofic if and only if $H$ embeds into $G$. For this reason, $G$ is said to be a universal sofic group.

As for your third question, Shelah has constructed a group $G$ of cardinality $\omega_{1}$ which has no uncountable proper subgroups. Clearly $Z(G)$ is countable. Consider $H = G/Z(G)$. Then $H$ also has no uncountable proper subgroups.Furthermore, every nontrivial conjugacy class of $H$ is uncountable and it follows that $H$ is simple.

Answer by Simon Thomas for When is something too big to be a set?

2010-07-20T18:46:56Z

The cumulative hierarchy is defined inductively as follows:

$V_{0} = \emptyset$

$V_{\alpha + 1} = \mathcal{P}({V_{\alpha}})$, the powerset of $V_{\alpha}$

$V_{\delta} = \bigcup_{\alpha < \delta} V_{\alpha}$ if $\delta$ is a limit ordinal.

The $ZFC$ axioms essentially say that the set theoretic universe $V$ is the union of the $V_{\alpha}$, where $\alpha$ runs through the ordinals. It turns out that a collection of sets $X$ is a set if and only there exists an ordinal $\alpha$ such that $X \subseteq V_{\alpha}$. Thus $X$ is a set if and only if $X$ has ``finished being created'' before the entire universe is created.

Answer by Simon Thomas for Finite simple groups with upper bound on order of elements

2010-07-06T23:17:22Z

The classification of the finite simple groups implies that there are only finitely many finite simple groups of a given exponent $k$. To see this, first note that we can ignore the sporadic groups, as well as the cyclic groups of prime order. It is also also clear that there are only finitely many alternating groups of a given exponent. So we need only consider groups of (possibly twisted) Lie type over finite fields. Here we see that there are only finitely possibilities for the Lie type: otherwise, the Weyl groups would involve arbitrarily large alternating groups. Once the Lie type is fixed, there are only finitely many possibilities for the finite field: otherwise we would obtain semisimple/diagonal elements of arbitrarily large exponent.

There are currently no proofs of this result which do not use the classification of the finite simple groups.

Answer by Simon Thomas for Isomorphism types or structure theory for nonstandard analysis

2010-06-17T07:13:35Z

The following was useful in a recent paper on asymptotic cones with Kramer, Shelah and Tent. How many ultraproducts $\prod_{\mathcal{U}} \mathbb{N}$ exist up to isomorphism, where $\mathcal{U}$ is a non-principal ultrafilter over $\mathbb{N}$? If $CH$ holds, then obviously just one ... if $CH$ fails, then $2^{2^{\aleph_{0}}}$.

In the case when $CH$ fails, the ultraproducts are already nonisomorphic as linearly ordered sets. The proof uses the techniques of Chapter VI of Shelah's book "Classification Theory and the Number of Non-isomorphic Models".

Answer by Simon Thomas for How much are reduced powers different ?

2010-07-03T16:37:48Z

Given that you are interested in ultrapowers of $\mathbb{R}$, you might like the following which appears in a joint paper with Kramer, Shelah and Tent.

Theorem: Up to isomorphism, the number of ultrapowers $\prod_{\mathcal{U}} \mathbb{R}$, where $\mathcal{U}$ is a nonprincipal ultrafilter over $\mathbb{N}$, is 1 if $CH$ holds and $2^{2^{\aleph_{0}}}$ if $CH$ fails.

Here $CH$ is the Continuuum Hypothesis. (In the case when $CH$ fails, the relevant ultrapowers are already non-isomorphic merely as linearly ordered sets.) The relevant reference is:

L. Kramer, S. Shelah, K. Tent and S. Thomas Asymptotic cones of finitely presented groups, Advances in Mathematics 193 (2005), 142-173.

Answer by Simon Thomas for Uniformization in Descriptive Set Theory

2010-06-30T13:12:43Z

One reason to be interested in uniformization is a very nice application of the Lusin–Novikov Uniformization Theorem to the theory of countable Borel equivalence relations. Here an equivalence relation $E$ on a Polish space is said to be Borel if $E$ is a Borel subset of $X \times X$ and $E$ is said to be countable if every $E$-class is countable. For example, if a countable discrete group $G$ has a Borel action $(g,x) \mapsto g \cdot x$ on a Polish space $X$, then the corresponding orbit equivalence relation $E_{G}^{X}$ is countable Borel. Using the Lusin–Novikov Uniformization Theorem, Feldman-Moore proved that every countable Borel equivalence relation arises in this manner; namely, if $E$ is a countable Borel equivalence relation on the Polish space $X$, then there exists a countable group $G$ with a Borel action on $X$ such that $E = E^{X}_{G}$.

Of course, if $E$ is an arbitrary equivalence relation on $\mathbb{R}$ with countable classes, then the Axiom of Choice implies that there is an action of $\mathbb{Z}$ on $\mathbb{R}$ which realizes $E$ as its orbit equivalence relation. The point of the Feldman-Moore Theorem is that if $E$ is Borel, then $E$ can be realized by a Borel action. It is interesting to note that there are countable Borel equivalence relations which cannot be realized by Borel actions of $\mathbb{Z}$.

Answer by Simon Thomas for Is there a universal countable group? (a countable group containing every countable group as a subgroup)

2010-06-21T21:44:43Z

There isn't a countable group which contains a copy of every countable group as a subgroup. This follows from the fact that there are uncountably many 2-generator groups up to isomorphism.

The first example of such a family was discovered by B.H. Neumann. A clear account of his construction can be found in de la Harpe's book on geometric group theory.

Computing the Galois group of a polynomial

2010-04-29T01:39:48Z

Does there exist an algorithm which computes the Galois group of a polynomial $p(x) \in \mathbb{Z}[x]$? Feel free to interpret this question in any reasonable manner. For example, if the degree of $p(x)$ is $n$, then the algorithm could give a set of permutations $\pi \in Sym(n)$ which generate the Galois group.

Periodic Automorphism Towers

2010-06-11T19:51:36Z

In Scott's classic textbook on Group Theory, he asks:

Suppose that $G$ is a finite group. Is the sequence of isomorphism types of the groups $Aut^{(n)}(G)$ for $n \in \mathbb{N}$ eventually periodic?

Here $Aut^{(2)}(G) = Aut(Aut(G))$ etc. Equivalently, is the sequence $|Aut^{(n)}(G)|$ always bounded above?

It apparently remains opens whether the sequence of automorphism types of $Aut^{(n)}(G)$ is in fact always eventually constant. (A wonderful theorem of Wielandt says that if $G$ is a finite centerless group, then the sequence is eventually constant.) So I would like to ask:

Does there exists a finite group such that $Aut(G) \not \cong G$ but $Aut^{(n)}(G) \cong G$ for some $n \geq 2$?

Edit: Joel has pointed out that my question is perhaps even open for infinite groups. This sounds like an interesting question which doesn't seem amenable to the standard tricks.

Answer by Simon Thomas for Does every automorphism of G come from an inner automorphism of S_G?

2010-06-11T19:24:50Z

The statement is true. Let $g \in G$ and $\pi \in Aut(G)$. Let $\lambda_{g}$ be the corresponding left translation by $g$. Regard $\pi$ and $\lambda_{g}$ as elements of $Sym(G)$. Then for all $x \in G$,

$(\pi \lambda_{g} \pi^{-1})(x) = (\pi \lambda_{g}) ( \pi^{-1}(x)) = \pi( g \pi^{-1}(x)) = \pi(g) x = \lambda_{\pi(g)}(x)$.

Thus $\pi \lambda_{g} \pi^{-1} = \lambda_{\pi(g)}$.

Answer by Simon Thomas for Ramsey multiplicity

2010-05-31T00:55:09Z

This is not an answer ... this is an even more trivial question. Why is it obvious with this definition of $m(n)$ that there doesn't exist a constant $k$ such that $m(n) \leq k$ for all $n \in \mathbb{N}$?

Comment by Simon Thomas

2013-05-16T15:46:14Z

Better to be a platonist ...

Comment by Simon Thomas

2013-05-16T14:52:03Z

@ Joel: your disagreement with Noah seems to based on whether you use extensional or intensional definitions of sets of natural numbers. Your example clearly uses an intensional definition and could be simplified as follows: Let X be an undecidable set of natural numbers and let Y be a decidable set of natural numbers. Let Z be X if ZFC is consistent and Y if ZFC is inconsistent. Then the decidability of Z is independent of ZFC.

Comment by Simon Thomas

2013-03-30T15:00:12Z

This is not true in general since it would imply that any two consistent theories were mutually interpretable. However, the complete theory of the field of real numbers cannot be interpreted in the complete theory of the complex field.

Comment by Simon Thomas

2012-12-25T20:19:37Z

@Jim: Rutgers doesn't have it online either. My guess/memory is that it also treats the Suzuki and Ree groups as the corresponding result for these groups is also needed for the main application: the classification of the simple periodic linear groups. In any case, these cases were done earlier by Kegal and Stingl.

Comment by Simon Thomas

2012-12-25T15:37:52Z

@Jim: Assuming the Suzuki groups are "sufficiently large", any inclusion is natural. In fact, this is true for any (possibly twisted) Lie type. For example, see: MR0734665 (85k:20094) Reviewed Hartley, B.(4-MANC); Shute, G.(1-WIP) Monomorphisms and direct limits of finite groups of Lie type. Quart. J. Math. Oxford Ser. (2) 35 (1984), no. 137, 49–71.

Comment by Simon Thomas

2012-11-13T01:51:01Z

This is clearly false.

Comment by Simon Thomas

2012-05-05T12:09:45Z

For example, see: MR1624736 (2000a:03081) Hjorth, Greg(1-UCLA); Kechris, Alexander S.(1-CAIT); Louveau, Alain(F-PARIS6-E) Borel equivalence relations induced by actions of the symmetric group. (English summary) Ann. Pure Appl. Logic 92 (1998), no. 1, 63–112.

Comment by Simon Thomas

2012-05-05T12:05:21Z

The various iterates $T_{\alpha}$ for $\alpha < \omega_{1}$ of the $FS$-jump are indeed unbounded within the class of Borel equivalence relations. And this is all that is needed for the application in Kechris-Louveau.

Comment by Simon Thomas

2012-04-28T21:54:07Z

Google Translate does a wonderful job!

Comment by Simon Thomas

2012-04-25T11:21:19Z

@Mark: Thanks! Alternatively, you can first code the graph in a field $K(S)$ and then let the group be $SL(3,K(S))$. The possibilities are endless ... (Suitable codings of graphs into fields were given by Fried-Kollar and Friedman-Stanley. I used to this to construct centerless groups whose automorphism towers terminate after any given transfinite number of steps.)

Comment by Simon Thomas

2012-04-25T02:22:26Z

I was thinking of Saharon's proof via stability theory which involves coding stationary sets. For example, consider the usual construction of $2^{\aleph_{1}}$ dense linear orders of cardinality $\aleph_{1}$ as unions of countable dense linear orders, where the embeddings are end extensions.

Comment by Simon Thomas

2012-04-25T02:07:41Z

I was being too terse. The relations $R(S)$ are supposed to be chosen so that this is true. For example, for every vertex $v$, include the relation $v^{p}=1$, where $p$ is a large prime. If $u$, $v$ is a pair of vertices, then include the relation $(uw)^{q}$ or $(uw)^{r}$, depending on whether or not $u$, $w$ are adjacent, where $q$ and $r$ are much bigger primes. (This trick is borrowed from Jay William's recent PhD thesis.)

Comment by Simon Thomas

2012-04-21T14:22:53Z

I have added the hypothesis that $G$ is non-elementary, since otherwise the first paragraph is incorrect.

Comment by Simon Thomas

2012-04-19T19:09:52Z

Solovay constructed a model of ZF in which $\mathbb{Z}$ does not have an invariant mean. But, of course, $\mathbb{Z}$ has a Folner sequence in this model.

Comment by Simon Thomas

2012-03-16T13:24:51Z

Yes, it is part of the Vive la différance I-III series.