Is Lagrange's Theorem equivalent to AC?

Question

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 04 '16 at 02:20
Yes definitely - I tried to prove LT => AC by proving one of the several equivalent forms. Every set has a group structure seemed hard to prove since we really want our sets to be groups before we can apply Lagrange to them. I spent a lot of time trying to find general constructions of $H \leq G$ s.t. given an infinite set $A$, $|A| = |G:H|$ (in attempt to then try and use Lagrange to prove one of the cardinal properties forms of AC e.g. Tarski's Theorem) but to no avail. — Ben E, Dec 04 '16 at 02:28
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? — Danielle Ulrich, Dec 04 '16 at 02: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 04 '16 at 03:42
What I had called Lagrange's Theorem Plus is just "there is a choice function for G:H" so by the first article you cited, it implies AC. — Danielle Ulrich, Dec 04 '16 at 04:19
If $\kappa$ is an infinite cardinal, then I think that $\kappa+\kappa=\kappa$ does not require choice. Considering then a group $G$ that is the direct sum of $\kappa$ copies of $\mathbb{Z}$, you can use a bijection $\kappa+\kappa=\kappa$ to identify a subset of the index set that has cardinality $\kappa$ and complement of cardinality $\kappa$. Call the sum of those subgroups corresponding to that subset $H$. Then $|H|=|G|$, and $|G:H|=|G|$. So Lagrange's Theorem would yield that $|G|=|H||G:H|$, or that $\kappa=\kappa\times\kappa$. When this holds for all $\kappa$, you get AC (by Tarski's Thm). — Arturo Magidin, Dec 04 '16 at 05:53
@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 04 '16 at 06:48
@ArturoMagidin If $G$ is the direct sum of $\kappa$ many copies of $\mathbb{Z}$, then does it follow that $|G| = \kappa$? Alternatively, do we know every infinite cardinal $\kappa$ arises as the size of such a $G$? — Ben E, Dec 04 '16 at 11:54
@Ben: Again, the question is whether or not $\kappa$ is assumed to have certain properties, which are true for $\aleph$-numbers but not generally for infinite cardinals (in the general sense of the word). — Asaf Karagila, Dec 04 '16 at 18:21
@AsafKaragila Yes, but showing $\kappa + \kappa = \kappa$ + LT => AC is a non-trivial result (since we know that the former doesn't imply AC by itself), so in my mind it's worth investigating (if it looks to be fruitful) — Ben E, Dec 04 '16 at 22:03
@Asaf: Thanks; actually, that should have been "if $A$ is an infinite set"; I would need "for any infinite set $A$, $A$ is bijectable with $(A\times{0})\cup (A\times{1})$" (i.e., the disjoint union of two copies of $A$); but your comment already suggests that this is not provable in ZF, so that's that, I think. — Arturo Magidin, Dec 04 '16 at 23:15
@BenE: Hmm... I'm no expert. But Asaf's comment already suggests my idea of going through Tarski's Theorem won't work in ZF by itself. I think it is possible to prove that if $G$ is countable, and $A$ is any infinite set, then the direct sum of $G$ with itself indexed by $A$ is bijectable with $A$, but perhaps that is not the case in ZF. We could try with $G$ the group of two elements, in which case you would have essentially $2\times A$; in that case, that the cardinality of $G$ is equal to the cardinality of the infinite index set would just depend on the same fact as the argument. — Arturo Magidin, Dec 04 '16 at 23:18
In any case, the off-hand comment in the Wikipedia page suggests to me that the way Lagrange is used to get to AC has to do with the assertion about cardinals/infinite sets; that is, that you somehow go from "the underlying set of $G$ is bijectiable with the product of the underlying set of $H$ and the underlying set of the partition induced by $H$ via cosets" to AC. That's why I thought of Tarski's theorem. — Arturo Magidin, Dec 04 '16 at 23:20
@Is this true because we can deefine the choice function to send the sets to the identity element of the group structure? or am I getting something wrong? — FNH, Dec 08 '16 at 16:49
@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 08 '16 at 18:07
Is choice hidden in the translation of the normal proof in the finite case? If a group $G$ has a subgroup $H,$ then $\sim$ is an equivalence relation on $G,$ where $x \sim y$ if and only if $x^{-1}y \in H.$ Furthermore, each equivalence class is in bijection with $H$. Is the issue then whether the set of equivalence classes has a well-defined cardinality? — Geoff Robinson, Dec 09 '16 at 10:54
@GeoffRobinson: yes, those those statements don't require choice (as we're only ever dealing with a finite number of elements and cosets when we prove that they partition the group and each coset bijects with $H$). The problem comes with the next step where you show $|G|$ = $|G:H||H|$: the way this is traditionally done (in the finite case) is to pick some element of $G$, take its coset, remove all of those elements from $G$ and iterate - as $G$ is finite we know we must be done in finite time. But this will not work in general if $|G:H|$ is infinite. — Ben E, Dec 09 '16 at 14:20
@BenE: This is what confuses me though: if we accept that the equivalence classes partition $G$, and that there are $[G:H]$ of them, each with $|H|$ elements, that would seem to justify that $|G| = [G:H]|H|.$ What you suggest as the stiicking point seems to me to be a repetition of the justification that the equivalence classes really exhaust $G$. I might be open to the argument that choice is being used implicitly in thee statement that the equivalence classes exhaust $G,$ but if that statement is accepted, I am still unclear about why the cardinality statement is not justified. — Geoff Robinson, Dec 10 '16 at 12:48
@GeoffRobinson I agree that it is very weird. I don't claim to be an expert, but let me try my best to explain (as far as I understand) what's going on, and hopefully somebody can correct me if I misspeak. Let me first draw parallels with the Partition Principle - PP says, effectively, if $A$ has a partitioning ${X_b | b \in B}$, then $A$ has at least $|B|$-many elements. This seems to be a very natural statement: if you can split $A$ into $|B|$-many non-empty disjoint subsets, then $A$ must have at least $|B|$ elements, since each such subset has an element, and there's $|B|$ of them! — Ben E, Dec 10 '16 at 15:25
However, it turns out that PP is independent of ZF! In ZFC, PP is clear: one can simultaneously pick an element from each one, and then we're done. But PP is not true in general without choice: in fact PP implies a great deal of choice (let me draw your attention to this wonderful blog post by Asaf about PP: https://boolesrings.org/asafk/2014/on-the-partition-principle/). So one has to wonder - why is it that PP doesn't follow from ZF? Well, in my mind the issue is that what we have is for every cell of the partition, a proof that it is nonempty, but what we really need is a... — Ben E, Dec 10 '16 at 15:27
...simultaneous proof that each such cell is nonempty, and such a proof requires choice. So the same thing happens here: for every coset, we have a proof that it bijects $H$, but we don't have a 'simultaneous proof' that every coset bijects $H$. When we assume choice, we can pick a representative of each coset and this gives us what we want, but without it it's not obvious how one would continue. $|G| = |G:H||H|$ means there is a bijection $G \to (G:H) \times H$ (or equivalently that there are injections in both directions), and it seems unclear to me how one would show the existence of such — Ben E, Dec 10 '16 at 15:34
functions without choice, but of course just because I can't see how one would do it doesn't mean it's not possible. Hope that helps. — Ben E, Dec 10 '16 at 15:36

Franka Waaldijk · Answer 1 · 2016-12-24T12:04:38.243

12

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}$.

edited Dec 24 '16 at 12:04

answered Dec 15 '16 at 10:11

Franka Waaldijk

1,606

1

This is already stated in the comments of Douglas Ulrich and Cameron Zwarich above. – Emil Jeřábek Dec 15 '16 at 10:41
1

"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
1

(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
Thank you Emil for pointing out the fallacies, I am now thinking of ways to resolve them. The free a.g. was not the correct approach, but I still have hope that the general strategy will work. I did not recognize this strategy in the remarks of Douglas Ulrich and Cameron Zwarich, but they were discussing LT⁺ and free abelian groups, so I should have checked Cameron Zwarich's references. Anyway, right now I checking to see whether a free non-abelian approach will do the trick. If anyone knows offhand why this cannot work, please let me know! – Franka Waaldijk Dec 15 '16 at 14:32
1

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
... Thus: the power set of any well ordered set is well ordered. This implies AC by a well known argument (prove that $V_\alpha$ can be well ordered by induction on $\alpha$; the limit case is more subtle). – Emil Jeřábek Dec 15 '16 at 14:47
Ah nice but over my head! I'll potter along with an alternative non-abelian construction and hope to lead that to a satisfying end as well. Could take some more time though, as I have other responsibilities. – Franka Waaldijk Dec 15 '16 at 15:22
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)$. 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$, or vice versa. – Franka Waaldijk Dec 15 '16 at 17:18
With the empty sequence as $0$, this yields a non-abelian group $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).
The nice thing about $F(W)$ is that all its elements are unique representations of finite sums. Therefore I hope that using this free non-abelian group construction, the fallacies that Emil pointed out in the proof above can be removed. Comments welcome.
– Franka Waaldijk Dec 15 '16 at 17:18
The definition second part should read $(k_1,...,k_n)+(l_1,...,l_m):= (k_1,...,k_{n-1})+(l_2,...,l_m)$ if $k_n = -l_1$. Other small corrections have been incorporated in the re-edit of the original answer (replacing free abelian with free non-abelian throughout). – Franka Waaldijk Dec 15 '16 at 19:43
It would be nice to have some comments on the correctness of the edited answer above (not just for me, but for other users and people who visit). If the non-abelian construction is deemed correct by some knowledgeable people, then the answer can be re-edited to remove the `I hope this works' remarks. So if you can spare the time, it would be much appreciated. Thanks in advance. – Franka Waaldijk Dec 22 '16 at 16:50
1

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
My current thinking is: we have a map $\varphi \colon (G : H) \mapsto L$ which sends $\tilde{g}$ to the unique element in ${ l \mid (l,m) \in \tilde{g}}$. This map is surjective (given $l = x_1 + \cdots + x_n \in L$, construct an $m$ by picking a $y_i$ with $(x_i, y_i) \in P$ for each $i$, then let $m = (x_1, y_1) + \cdots + (x_n, y_n)$, and then $\varphi(H(l, m)) = l$. Maybe I'm missing something but it doesn't seem injective (due to our free groups being non-abelian), but if we restrict it to $\varphi^{-1}(X)$ (by $X$ I mean its natural embedding into $L$), then I think it is injective... – Ben E Dec 23 '16 at 17:49
...so that gives us a bijection $\varphi^{-1}(X) \to X$ satisfying $\varphi(\tilde{x}) = x$ and hence $\varphi^{-1}(x) = \tilde{x}$. This seems a little round-the-houses so I suspect I've missed something. – Ben E Dec 23 '16 at 17:52
thank you Ben, your question is just what I needed to convince myself of the correctness! I was too `lazy' and a bit unsure to just check everything myself, but now I see that it is actually very straightforward. We only need to check whether everything is nicely defined according to the language and axioms of ZF. So, first: the definition of $\tilde{x}$ is unique, its correctness falls under the axiom of restricted comprehension since $\tilde{x}:={g\in G\mid\exists h\in H[g=h+x]}$ (axiom of restricted comprehension says that ZF-definable subsets of existing sets also exist). – Franka Waaldijk Dec 24 '16 at 09:08
The other constructions also fall under ZF axioms. Pairing axiom (for sets $X,Y$ the set $X\times Y$ exists). Infinity axiom for existence of $\mathbb{N}$ which is needed to define, inductively, $K^n$ for every $n\in\mathbb{N}$, then the union axiom to define the set $K^*$, and restricted comprehension again to form the elements of the free non-abelian group $F(W)$. All the other constructions are explicitly and uniquely definable in ZF, ergo... the proof is correct. I will edit to reflect this. – Franka Waaldijk Dec 24 '16 at 09:21
Sorry, sloppy mistake in the comment above: $\tilde{x}:={g\in G\mid\exists h\in H\exists a\in Y[(x,a)\in P\wedge g=h+(x,(x,a))]}$. – Franka Waaldijk Dec 24 '16 at 09:30
1

The definition of the free group operation is not quite correct: you need to cancel subwords of arbitrary length at the juncture if necessary, not just length 0 or 1. – Emil Jeřábek Dec 24 '16 at 10:09
Actually the definition is correct, since it is inductive and therefore covers your remark (arbitrarily long subwords are canceled). I have edited again to emphasize this, because this was indeed easy to miss. (restating my previous deleted comment more clearly) – Franka Waaldijk Dec 24 '16 at 15:05

score 8 · Answer 2 · answered Feb 15 '17 at 16:12

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
http://mathoverflow.net/a/26893/7206 and also relevant to this, http://math.stackexchange.com/a/2001591/622 — Asaf Karagila, Feb 16 '17 at 04:24

Is Lagrange's Theorem equivalent to AC?

2 Answers2