44
$\begingroup$

I am teaching a first-semester course in abstract algebra, and we are discussing group isomorphisms. In order to prove that two group are not isomorphic, I encourage the students to look for a group-theoretic property satisfied by one group but not by the other. I did not give a precise meaning to the phrase "group-theoretic property", but some examples of the sort of properties I have in mind are $$ \forall g,h\in G:\exists n,m\in\mathbb{Z}:(n,m)\neq (0,0)\wedge g^n=h^m,\\ \forall H\leq G:\exists g,h\in G:H=\langle g,h\rangle,\\ \forall g,h\in G:\exists i\in G: \langle g,h\rangle = \langle i\rangle $$ One of my students asked if, give two non-isomorphic groups, there is always a group-theoretic property satisfied by one group but not the other. In a sense, "being isomorphic to that group over there" is a group-theoretic property. But this is not really what I have in mind.

To pin down the class of properties I have in mind, let's say we allow expressions involving

  • quantification over $G$, subgroups of $G$, and $\mathbb{Z}$,
  • group multiplication, inversion, and subgroups generated by a finite list of elements
  • the symbol $1_G$ (the group identity element),
  • addition, subtraction, multiplication, exponentiation (provided the exponent is non-negative), and inequalities of integers ,
  • the integer symbols $0$ and $1$,
  • raising a group element to an integer power, and
  • equality, elementhood, and logical connectives.

I do not know much about model theory or logic, but my understanding is that this is not the first-order theory of groups. In particular, this MSE question indicates that there exist a torsion and a non-torsion group which are elementarily equivalent (meaning they cannot be distinguished by a first-order statement in the language of groups), but these groups can be distinguished by a property of the above form. I have also heard that free groups of different rank are elementarily equivalent, but these can also be distinguished by a property of the above form.

My questions are:

(1) Is there a name for the theory I am considering? Or something closely (or distantly) related?

(2) Are there examples of non-isomorphic groups that cannot be distinguished by a property of the above form? Are there examples where the groups involved could be understood by an average first-semester algebra student?

$\endgroup$
0

3 Answers 3

Reset to default
31
$\begingroup$

First, let's start with the silly answer. Your language only has countably many different expressions, so can only divvy groups up into continuum-many classes - so there are definitely non-isomorphic groups it can't distinguish! In general this will happen as long as your language has only set-many expressions: you need a proper class sized logic like $\mathcal{L}_{\infty,\infty}$ to distinguish between all pairs of non-isomorphic structures.

That said, you're right that you're looking at something much stronger than first-order logic. Specifically, you're describing a sublogic of second-order logic, the key difference being that second-order logic lets you quantify over arbitrary subsets of the domain, and indeed functions and relations of arbitrary arity over the domain, and not just subgroups. Second-order logic doesn't have an explicit ability to refer to (say) integers built in, but it can do so via tricks of quantifying over finite configurations.

While the exact strength of the system you describe isn't clear to me, second-order logic is known to be extremely powerful. In particular, I believe there are no known natural examples of non-isomorphic second-order-elementarily-equivalent structures at all, although as per the first paragraph of this answer such structures certainly have to exist! So second-order-equivalence is a pretty strong equivalence relation, and in practice will suffice to distinguish all the groups your students run into.

$\endgroup$
15
  • $\begingroup$ Out of curiosity, how do you state having infinite cyclic subgroups without going into infinitary logic? $\endgroup$
    – tomasz
    Oct 9, 2020 at 20:14
  • $\begingroup$ Where can I read more about proper class sized logics? $\endgroup$
    – user76284
    Oct 9, 2020 at 20:31
  • 1
    $\begingroup$ @tomasz For example, we can say that an element $g$ of a group has infinite order (this is basically the same) by saying "The smallest subgroup containing $g$ has a non-surjective self-injection." This is of course second-order, but not infinitary. In general, for most things we run into normally second-order logic is actually vastly stronger than infinitary logic, with combinatorial tricks like the above being used to get around apparent reliance on infinitary Boolean combinations. $\endgroup$
    – Noah Schweber
    Oct 9, 2020 at 20:40
  • $\begingroup$ @user76284 The huge collection Model-theoretic logics is freely available online and has some relevant material. The most important proper-class-sized logic is definitely $\mathcal{L}_{\infty,\omega}$; it's certainly much better-behaved than the "full infinitary logic" $\mathcal{L}_{\infty,\infty}$. For example, $\mathcal{L}_{\infty,\infty}$-equivalence is just isomorphism, whereas $\mathcal{L}_{\infty,\omega}$-equivalence is potential isomorphism (= existence of a "back-and-forth system"; equivalently, isomorphism in some forcing extension). $\endgroup$
    – Noah Schweber
    Oct 9, 2020 at 20:42
  • 1
    $\begingroup$ Regarding the insufficiency of a countable number of sentences: I've found myself wondering whether "ordinal definable" classes would suffice to overcome that, e.g. you use a sentence with some number of free variables which are intended to represent ordinal parameters plus one for the group, and then consider the classes which are formed by assigning all possible tuples of ordinals to those free variables, say over a ZFC foundation. That would certainly be enough to distinguish groups of different cardinalities, without feeling cheap like "isomorphism to this given group". $\endgroup$
    – Daniel Schepler
    Oct 9, 2020 at 21:38
14
$\begingroup$

Here are some simple examples where you at least need to make some decisions about what you believe about set theory to determine whether two groups are isomorphic. Assuming the axiom of choice every vector space has a basis, so $\mathbb{R}$ is isomorphic (as a group) to some direct sum of copies of $\mathbb{Q}$ (in fact necessarily to a direct sum of $|\mathbb{R}|$ copies of $\mathbb{Q}$). The existence of such a basis for $\mathbb{R}$ over $\mathbb{Q}$ allows you to construct Vitali sets, which are non-measurable, and there are models of $ZF \neg C$ in which every subset of $\mathbb{R}$ is measurable, so $\mathbb{R}$ fails to have a basis in such models.

Another example along the same lines is $\left( \prod_{\mathbb{N}} \mathbb{Q} / \bigoplus_{\mathbb{N}} \mathbb{Q} \right)^{\ast}$, taking the dual as a $\mathbb{Q}$-vector space. Assuming the axiom of choice this is a direct sum of $|\mathbb{R}|$ copies of $\mathbb{Q}$ again, but without at least enough choice to construct something like non-principal ultrafilters on $\mathbb{N}$ it's not clear how to write down a single nonzero element of this group!

$\endgroup$
1
  • 3
    $\begingroup$ It's an interesting question to ask what are the hardest groups to distinguish up to isomorphism that you would run into in a first-year class in abstract algebra. Here's an example I ran into in recently in another math.SE question: is it true that if $K$ is any field then $PSL_n(K) \cong PSL_m(K)$ iff $n = m$? In the question it sufficed to distinguish any $n \neq m$ where $n, m \ge 3$ and I could distinguish $PSL_3$ and $PSL_9$. Details: math.stackexchange.com/questions/3843808/… $\endgroup$
    – Qiaochu Yuan
    Oct 9, 2020 at 2:47
4
$\begingroup$

Another example that's basic and probably counts as cheating: Consider $G = \mathbb{Z}^{\kappa}$ for cardinal numbers $\kappa$ starting with $\aleph_0$. I don't know enough model theory to prove it, but I can't imagine there is a group-theoretic property that distinguishes between these.

$\endgroup$
4
  • 2
    $\begingroup$ In first-order logic there certainly isn't, but the OP isn't limiting themselves to first-order logic (see the role of the true integers or quantification over subgroups). Second-order logic certainly can distinguish between for example $\mathbb{Z}^{\aleph_0}$ and $\mathbb{Z}^{\aleph_1}$, although I'm not sure if the OP's fragment of SOL can. $\endgroup$
    – Noah Schweber
    Oct 9, 2020 at 17:33
  • $\begingroup$ My intuition is that it's impossible to make distinction using OPs methods, but like I said - I have no proof. If there exists a group property that distinguishes between these, it has to be very unnatural one. $\endgroup$
    – Jakub Konieczny
    Oct 9, 2020 at 17:41
  • $\begingroup$ Yes, I think I have the same intuition. Towards a proof we have the following fact: two groups $G,H$ are equivalent w/r/t the OP's logic iff their associated structures $[G],[H]$ are elementarily equivalent in the usual sense, where for a group $A$ the structure $[A]$ is the two-sorted structure consisting of $(i)$ $A$ itself and $(ii)$ the lattice of subgroups of $A$, with elementhood and the "shift" operation $(x,Y)\mapsto \{xy: y\in Y\}$ relating them. $\endgroup$
    – Noah Schweber
    Oct 9, 2020 at 17:47
  • $\begingroup$ It's known that $\text{Hom}(\mathbb{Z}^I, \mathbb{Z}) \cong \bigoplus_I \mathbb{Z}$ when $I$ is countable (a very strange result for sure, see: en.wikipedia.org/wiki/Baer%E2%80%93Specker_group); does anyone know if it has a chance of holding in general? If so we can do it. I'm not quite sure if this is expressible in the OP's language but in any case "the dimension of $\text{Hom}(G, \mathbb{Z}) \otimes \mathbb{Q}$" qualifies as a group-theoretic property by any stretch of the imagination, I think. $\endgroup$
    – Qiaochu Yuan
    Oct 10, 2020 at 21:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .