7
$\begingroup$

It is well known that the collection of all sets does not form a set, the proof of this uses assumes that such a set exists, and obtains a contradiction by using either the axiom of restricted comprehension, or the derived result that no set can contain itself.

Now, one would naively expect that since there is an embedding of the class of all sets into the class of all groups, that the latter does not form a set either, but how does one formally prove this? It does not seem possible to use the normal Russell's-paradox type proof, since the members of the class of all groups are formally tuples, and the set of all groups, had it existed, is not a group.

Is there a simple argument to show that the set of all groups does not exist? The most general argument would be that injective class-functions preserve the property of being a proper class, and this seems difficult for me to prove with my limited set theory knowledge.

$\endgroup$
9
  • 2
    $\begingroup$ Maybe the axiom schema of replacement together with the "mapping" that assigns to every group its underlying set? $\endgroup$
    – Stefan
    Dec 9, 2023 at 17:41
  • 4
    $\begingroup$ @Stefan For this argument to work, you need to know that every set is the underlying set of some group (or at least that arbitrarily large sets are). This is true, and not hard, but it's easier to observe that for every set $x$, $\{x\}$ is the underlying set of an isomorphic copy of the trivial group, so the union of the set of all groups (if it existed) would contain every set. $\endgroup$ Dec 9, 2023 at 18:41
  • 5
    $\begingroup$ Does this answer your question? Why is the collection of all groups a proper class rather than a set? $\endgroup$ Dec 9, 2023 at 18:41
  • 1
    $\begingroup$ @Alex: I think what I wrote is implicitly also part of your argument, but the follow-up with singletons is indeed much better than what I had in mind. $\endgroup$
    – Stefan
    Dec 9, 2023 at 19:14
  • 1
    $\begingroup$ @Carlyle Ok, then look here: math.stackexchange.com/q/1096528/7062 A brief on this site can go a long way... All I had to do to find these was type in "class of all groups" and "class of all singletons" in the search bar. They were the first results. $\endgroup$ Dec 9, 2023 at 19:25

1 Answer 1

18
$\begingroup$

Nice question again :).

I think your argument looks good and is not too hard to make rigorous (depending a little on which embedding you have in mind - if you wanted to send $X$ to some group $G_X$ with underlying set $X$ that is a bit subtle, actually).

The argument that I like the most proves something even slightly stronger - "there is no set of groups which contains a representative from each isomorphism class":

Lemma. Let $S$ be a set of groups. Then there is some group $G$ such that no element of $S$ is isomorphic to $G$.

Proof. Let $X = \bigcup_{H \in S} H$ be the union of all the underlying sets of the elements of $S$ (if you're being more formal and "group" means "tuple of data" to you, this means $X = \bigcup_{t \in S} \pi_1(t)$). Let $G$ have underlying set $\mathcal P(X)$, the powerset of $X$, and equip $G$ with the symmetric difference operation to make it into a group.

Then for each $H \in S$, note there is a surjection $X \to H$. Since there is no surjection from $X \to \mathcal P(X)$ (by Cantor's theorem), it follows that $H$ does not even surject onto $G$. So certainly they don't biject, and they definitely aren't isomorphic. QED.


By the way, this argument works perfectly well in ZF, with no choice needed!

This argument is really using the fact that there are groups of arbitrarily large cardinality, and that the elements of any set of sets cannot have arbitrarily large cardinality. This will work equally well for pretty much any other algebraic structure you can think of. In this case it's a bit "lucky" that $\mathcal P(X)$ has a natural operation making it into a group. In general you might have to consider "the free structure on a large set", or "the product of a large number of copies of a nontrivial structure" to make big structures. (In fact $\mathcal P(X)$ is an example of the latter - it's the product of $|X|$ many copies of $C_2$).

In some sense there being groups of arbitrarily large cardinality is the only reason this lemma is true - namely, if $K$ is any set, then the collection of isomorphism types of groups which are the same size as some element of $K$ is a set. More precisely, there is a set $S$ of groups, such that every group $G$ that bijects with some set in $K$ is isomorphic to some group in $S$ (this is because the collection of all group operations on a set $X$ is a set). Particularly, if $\kappa$ is a cardinal then there is a set containing representatives for all isomorphism classes of groups of cardinality less than $\kappa$.

$\endgroup$
1
  • 2
    $\begingroup$ This answer is really nice, I appreciate that it is somewhat an analogue of Russell's paradox, since the proof of Cantor's theorem uses a similar argument to that of Russell's paradox $\endgroup$
    – Carlyle
    Dec 9, 2023 at 19:28

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