# Is Lagrange's Theorem equivalent to AC?

Lagrange's Theorem is most often stated for finite groups, but it has a natural formation for infinite groups too: if $G$ is a group and $H$ a subgroup of $G$, then $|G| = |G:H| \times |H|$.

If we assume AC, the we get a fairly straightforward proof (pick a representative of each coset, and then let your map $(G : H) \times H \to G$ be $(gH, h) \mapsto gh$).

However, somebody told me someone told them that the converse is true too, i.e. Lagrange's Theorem gives us AC. (Indeed, the wikipedia page for LT offhandedly mentions they're equivalent without a reference). Does anybody have a proof (or alternatively a proof AC is stronger than LT)?

• It should be noted that the existence of a group structure on every set is itself equivalent to the Axiom of Choice. – Cameron Zwarich Dec 4 '16 at 2:20
• Suppose we strengthen Lagrange's theorem to Lagrange's Theorem Plus, that is: there is a bijection $f: G \to (G:H) \times H$ such that for every $a \in G$ there is $b \in H$ with $f(a) = (aH, b)$. Do we know either of the implications: Lagrange's Theorem implies Lagrange's Theorem Plus, or Lagrange's Theorem Plus implies AC? – Douglas Ulrich Dec 4 '16 at 2:57
• Possibly relevant: having selectors for quotients of abelian groups is equivalent to AC, and so is the projectivity of any free abelian group. – Cameron Zwarich Dec 4 '16 at 3:42
• @Arturo: If by "cardinal" you mean an intial ordinal, then you are right, but also $\kappa^2=\kappa$. If you mean a general cardinal, then this is not true anymore. While $\kappa+\kappa=\kappa$ does not imply choice, it is certainly not provable in ZF itself. – Asaf Karagila Dec 4 '16 at 6:48
• @MathsLover: no, since in general there may be many group structures on a set and we aren't given a canonical choice of group structure for each set (and hence not a canonical choice of identity element). (Interestingly, everybody who I've seen introduced to this fact, including myself, immediately thought that this was why!) Instead, let me point you to this mathoverflow question. – Ben E Dec 8 '16 at 18:07

The following version of Lagrange's theorem is equivalent to AC:

LT+: Let $H$ be a subgroup of the group $G$. Then there is a bijection $k: (G:H)\times H\to G$ such that for each $(\tilde{g},h)\in (G:H)\times H$, the image $k((\tilde{g},h))$ is in $\tilde{g}$.

That AC implies LT+ was already shown in the question. To show that LT+ implies AC, the additive notation seems easier.

Let $P\subseteq X\times Y$ be sets such that $\forall x\in X\exists y\in Y[(x,y)\in P]$. We wish to derive from LT+ the existence of an $f\subseteq P$ such that $\forall x\in X\exists! y\in Y[(x,y)\in f]$.

For this we construct a group $G$ as follows. First, let $L$ be the free non-abelian group on $X$ [as specified at the bottom of this answer], and $M$ the free non-abelian group on $P$. Then let $G$ be the diagonal' subgroup of the group $L\times M$ generated by $\{(x,(x,a))\mid (x,a)\in P\}$. Let $H$ be the subgroup of G generated by $\{(\mathbf{0},(x,a)-(x,b))\mid (x,a), (x,b)\in P\}$.

Taking right cosets $H/G$ amounts to identifying $(x,(x,a))$ with $(x,(x,b))$, for $x$ and $a,b$ such that both $(x,a),(x,b)\in P$. More precisely, the right $H$-coset of $(x,(x,a))$ is independent of $a$:

$\tilde{x}:=\{(x, \Sigma_{i<n}((z_i,w_i)-(z_i,v_i))+(x,a))\mid n\in \mathbb{N},(z_i,w_i), (z_i,v_i)\in P, (x,a)\in P\}$

$\tilde{x}$ contains $(x, (x,b))$ for all $b$ such that $(x,b)\in P$. But more importantly, every element of $\tilde{x}$ pinpoints a single $c$ such that $(x,c)\in P$. Because in $M$ there is only one interpretation of the expression $\Sigma_{i<n}((z_i,w_i)-(z_i,v_i))+(x,a)$, and this is a finite sequence in $(P\times\{-1,1\})^*$ [see below]. Every element of $\tilde{x}$ is derived from an $M$-sum in the second coordinate, such as $(x,\Sigma_{i<n}((z_i,w_i)-(z_i,v_i))+(x,a))$, and in this $M$-sum there is always a term $(x,c)$ for some $c$. So we can look for the first occurrence (smallest index) of such a term $(x,c)$, and this is canonical (no choice). Therefore there is a function $s: \bigcup\{\tilde{x}\mid x\in X\}\to Y$ such that for all $u\in\tilde{x}$ we have that $(x,s(u))\in P$.

By LT+ there is a bijection $k: (G:H)\times H\to G$ such that for each $(\tilde{g},h)\in (G:H)\times H$, the image $k((\tilde{g},h))$ is in $\tilde{g}$.

We now define the desired $f$ as follows:

$f(x):= s(k(\tilde{x},\mathbf{0}_G))$

[This is an edited answer after Emil pointed out the fallacies in the original answer which used the free abelian group construction. To understand the comments, the original answer can be refound by replacing non-abelian with abelian.]

For a set $W$, form a free' non-abelian group $F(W)$ as follows. First, giving each element $w$ of $W$ an inverse $-w$, we come to consider $K=W\times\{-1,1\}$, and write $w$ for $(w,1)$ and $-w$ for $(w,-1)$, and sometimes as abbreviation $-(-w)$ for $w$. To avoid having to quotient/project/select, we look at finite sums of these elements, that is finite sequences $(k_1,...,k_n)$ in $K^*=\bigcup \{K^n\mid n\in\mathbb{N}\}$ in which we have already removed the partial sums that yield $0$. In other words, there is no $i<n$ such that $k_i = z$ and $k_{i+1}=-z$. So put $F(W)=\{(k_1,...,k_n)\in K^*\mid \forall i<n [k_i \neq -k_{i+1}], n\in\mathbb{N}\}$. With the empty sequence as $0$, this yields a non-abelian group structure on $F(W)$ by putting $(k_1,...,k_n)+(l_1,...,l_m):= (k_1,...,k_n,l_1,...,l_m)$ if $k_n\neq -l_1$, and $(k_1,...,k_n)+(l_1,...,l_m):= (k_1,...,k_{n-1})+(l_2,...,l_m)$ if $k_n = -l_1$. ($k_n = -l_1$ is an abbreviation of two different cases, and the definition is inductive in the length $n$, meaning that we cancel out neighboring opposite terms in the sequence $(k_1,...,k_n,l_1,...,l_m)$ one after the other, as far as possible).

The nice thing about $F(W)$ is that all its elements are unique representations of finite sums. For elements $s_0,...,s_{n-1}$ in $F(W)$ we write $\Sigma_{i< n}s_i$ to denote the element $s_0+s_1+...+s_{n-1}$.

• This is already stated in the comments of Douglas Ulrich and Cameron Zwarich above. – Emil Jeřábek Dec 15 '16 at 10:41
• "throughout M we write our generated finite sums in a way that we can search for the first occurrence of (x,...) in an M-sum": no, not in any choice-free construction of the free abelian group that I can imagine. In fact, the claim that you can write free abelian groups in this way by itself implies AC for families of finite sets. – Emil Jeřábek Dec 15 '16 at 10:51
• (The construction of the free a.g. over $P$ that does work in ZF is that its elements are functions from $P$ to $\mathbb Z$ that are $0$ on all but finitely many arguments. This does not make the "sums" ordered unless we have an a priori linear order on $P$. Note also that ZF proves that the free a.g. over $P$ is unique up to a unique isomorphism identical on $P$.) – Emil Jeřábek Dec 15 '16 at 10:58
• I gave it a little thought meanwhile, too, and I think your original argument can be extended to make it correct. Namely, your construction shows that a multifunction from $X$ to $Y$ has a selector if $Y$ can be linearly ordered. I think this does imply full AC. First, taking $X=\mathcal P(Y)$, we obtain a selection function for all subsets of $Y$, and then we can construct an enumeration of $Y$ by transfinite recursion. Thus, we get: every linearly ordered set can be well ordered. Moreover, if $X$ is well ordered, the lexicographic order linearly orders its power set. ... – Emil Jeřábek Dec 15 '16 at 14:45
• Hi @FrankWaaldijk, currently slowly chewing over this answer. Sorry if I ask anything elementary, just want to make sure we're not doing anything that secretly uses AC. Is it obvious that we have a map $X \to (G \colon H)$ s.t. $x \mapsto \tilde{x}$ $\forall x$? Certainly given an $x$ we can produce $\tilde{x}$ by finding some $a$ with $(x, a) \in P$, then $\tilde{x} = H(x, (x, a))$. But the natural way of turning this into our map $X \to (G \colon H)$ would require picking such an $a$ $\forall x$ - is there another way we can do this? – Ben E Dec 23 '16 at 16:56

Lagrange's Theorem does not follow from ZF. In fact, the following weaker statement also does not follow:

$\sf LT^{-}$: Let $H$ be a subgroup of $G$. Then $|H|$ divides $|G|$, i.e. there exists a set $A$ s.t. $|H| \times |A| = |G|$.

(The name LT$^{-}$ is not standard, but in the vein of the name LT$^{+}$.)

I stumbled upon the paper The Construction of Groups in models of set theory that fail the Axiom of Choice (Hickman, 1976) where he constructs a model of ZF with an amorphous group (a group whose carrier set is amorphous, i.e. an infinite set that isn't the disjoint union of two infinite sets).

He then goes on to prove several properties about amorphous groups, including the following:

Suppose $G$ is an amorphous group, and $H \leq G$ a finite non-trivial subgroup. (Such a subgroup always exists: every element in $G$ has finite order as $G$ has no $\aleph_0$ subset.)

Suppose that there was a set $A$ and a bijection $f \colon H \times A \to G$. As $H$ is finite, $A$ must be infinite. But then for any $h_1 \neq h_2 \in H$, $f(\{h_1\} \times A)$ and $f(\{h_2\} \times A)$ are infinite disjoint subsets of $G$, contradicting $G$ being amorphous.

So we need some 'choice' (i.e. a statement along the lines of 'no amorphous sets exist' or 'every infinite set is Dedekind-infinite') at the very least to have LT. How much is still unclear.

• You don't need to go as far as amorphous sets. You can get it for $\Bbb R$ and $\Bbb Q$. If all sets of reals have the Baire property, then $\Bbb{R/Q}$ cannot be linearly ordered, in which case $|\Bbb R|\neq|\Bbb{Q\times R/Q}|$. – Asaf Karagila Feb 15 '17 at 19:41
• @AsafKaragila - can you link/point me to a proof of that? Cheers – Ben E Feb 15 '17 at 23:33
• mathoverflow.net/a/26893/7206 and also relevant to this, math.stackexchange.com/a/2001591/622 – Asaf Karagila Feb 16 '17 at 4:24