# Do "superinfinite" sets exist?

A set $$X$$ is infinite if and only if it is equivalent to one of its proper subsets. That is, if there is a proper subset $$Y\subset X$$ and a bijection $$f:X\rightarrow Y$$.

But what if we require $$f$$ to preserve additional structures on $$X$$? Let us call a set $$X$$ "superinfinite" if it is equivalent to one of its proper subsets $$Y\subset X$$ via a bijective mapping $$f:X\rightarrow Y$$ preserving all structures on $$X$$.

For example, the map $$n\mapsto n+1$$ preserves the ordering on $$\mathbb{N}$$, but it does not preserve addition. So far, every bijection I have defined between $$\mathbb{N}$$ and one of its proper subsets fails to preserve some structure on $$\mathbb{N}$$.

Questions:

1. What are "superinfinite" sets really called? As I am sure this has been studied.
2. Is $$\mathbb{N}$$ a "superinfinite" set? If not, do they even exist?

Edit: I have found an article in an old issue of Pour la Science (December 2000, #278) by Patrick Dehornoy where he mentions (p.140) that it is not known whether "superinfinite" sets exist. But that it has been proven that $$\mathbb{N}$$ is NOT a superinfinte set. He mentions that superinfinite sets are also called large cardinals.

In these slides (page 134) Dehornoy calls this superinfinite sets ultra-infinite, or self-similar. More precisely using his definition:

• A set $$X$$ is infinite iff there is $$f:X\rightarrow X$$ injective but non-bijective.
• A set $$X$$ is "superinfinite" (ultra-infinite, self-similar) iff there is $$f:X\rightarrow X$$ injective, non-bijective AND preserving everything definable from $$\in$$.
• what you call infinite is actually called "Dedekind infinite." A usual definition of infinite is being not finite. Mar 4 at 15:07
• @mathlearner98 assuming the axiom of choice, Dedekind infinite is equivalent to being infinite
– ℋolo
Mar 4 at 15:08
• Here is an English version (and I believe the original version) of the slide show you linked that uses the proper terms we use today
– ℋolo
Mar 4 at 16:51
• Thank you, indeed, I looked and the English version of the slide show I linked can be found here
– John
Mar 4 at 17:05
• There is a more general notion than preserving everything definable from ϵ. An Elementary Embedding is a f:A → B s.t. any definable formula true for x in A, is true for f(x) in B. This is where large cardinals come in. As assuming elementary embeddings exist, lead to the existence of various large cardinals. Mar 5 at 16:36

There are no superinfinite sets. Let $$Y\subsetneq X$$ be any infinite set and let $$f:X→Y$$ be a bijection, and let $$(X,R)$$ be a structure where $$R(a)⇔a\notin Y$$.

Clearly $$f$$ does not preserve this structure.

Here is a related idea that is achieved by only caring about structures with only functions, and allowing not requiring a single function to capture all substructures:

An algebra $$(X,F)=(X;f_0,f_1,\ldots)$$ is a set $$X$$ (called "domain") together with countably many functions from $$X^{n_i}$$ to $$X$$ (where $$n$$ can change between functions).

A subalgebra $$(Y,F)$$ is an algebra such that $$Y\subseteq X$$ and for each $$f_i$$ we have that $$f_i''(Y^{n_i})⊆Y$$, that is, a subset of $$X$$ that is closed under the functions in $$F$$.

A Jónsson algebra is an algebra $$(X,F)$$ such that if $$(Y,F)$$ is a proper subalgebra of $$(X,F)$$, then $$|Y|<|X|$$. For example $$(ℕ,x\to x-1)$$ (where $$0-1=0$$) is a Jónsson algebra, but $$(ℕ,x\to x+1)$$ is not.

So an algebra is not a Jónsson algebra if there exists a proper subalgebra of the same cardinality as $$X$$.

A cardinal $$κ$$ is called "Jónsson cardinal" if it has no Jónsson algebras on it, so any algebra whose domain is $$κ$$ has a proper subalgebra of the same cardinality as $$κ$$ (note that each algebra will have a different subset).

The existence of a Jónsson cardinal is a special kind of a Large Cardinal Axiom and the strength of the statement "$$\aleph_ω$$ is Jónsson-cardinal" is open.

• I would have pinged you in my answer with an @ command if I knew how to type out your tag :-/ Mar 4 at 15:42
• @LeeMosher lol, copy paste is always an option (I have toggle to enable the mathcal template in plain text on my keyboard)
– ℋolo
Mar 4 at 15:53
• Heh. I have old habits, I stick to basic ascii characters. Mar 4 at 16:11

I don't think it makes much sense to talk about "all structures" on a set - if one takes any injective, non-surjective function $$f : X \mapsto X$$ one can cook up a very specialized structure on $$X$$ which is designed so that it is not preserved by $$f$$; see the answer of @ℋolo.

But one could make sense of this question if one restricted to a particular "type" of mathematical structure, i.e. if one restricted the category in question.

In any (concrete) category, an object $$X$$ is called co-Hopfian if every injective structure-preserving self map $$X \mapsto X$$ is surjective. So your property could be described by saying that $$X$$ is a non co-Hopfian object in its category.

The one place I've seen this terminology a lot is in the category of groups. You'll find an extended list of co-Hopfian and non-co-Hopfian groups here. A particularly simple example of a non-co-Hopfian group is the rank $$2$$ free group $$F_2 = \langle a,b \rangle$$; a simple example of an injective, nonsurjective homomorphism $$F_2 \hookrightarrow F_2$$ is given by $$a \mapsto a^2$$, $$b \mapsto b$$.

• Yes, indeed. When I said "all structures" I was implicitly assuming everything that is definable via $\in$, in a sense that I cannot put precisely because I do not know the terminology. But what I had in mind rules out the non-existence argument @ℋolo rightly points out.
– John
Mar 4 at 16:05
• You might want to take a look at category theory, which is what one uses nowadays as a means of discussing "mathematical structures" in a rigorous and conceptual manner. Mar 4 at 16:11
• @John I do not think any sensible restriction to ∈-definable objects will change the answer, the only 2 sensible ways I can think of to make this question non-trivial is either by restricting yourself to specific kind of structures (so this answer), or allow different subset for each structure (so my answer). LeeMosher while Cats is very popular Set theory is not quite dead yet as a way to talk about general mathematical structures (e.g. infinitary combinatorics and colouring problems are not yet done in Cats, similarly model theory is not done with cats background) :)
– ℋolo
Mar 4 at 16:18
• Patrick Dehorhoy calls these superinfinite sets ultra-infinite or self-similar sets here: lmno.cnrs.fr/archives/dehornoy/Talks/Dys.pdf (page 134 for example) Hence, there must be more to it. And apparently these ultra-infinite sets are used to prove properties of Laver tables, which from the slides are finite objects.
– John
Mar 4 at 16:38
• @John what they wrote there is quite different from what you described, I will edit my answer to reflect this new question
– ℋolo
Mar 4 at 16:41

The abelian group $$\mathbb{Z}$$ is isomorphic, as a group, to any of its nonzero ideals. If $$(n)$$, $$n\neq 0$$, is such an ideal, then multiplication by $$n$$ is a group homomorphism and an isomorphism between $$\mathbb{Z}$$ and the ideal $$(n).$$ Is this the kind of situation in which you are interested?

• Good example, but your isomorphism does not preserve all the structures on $\mathbb{Z}$.
– John
Mar 4 at 15:17
• @John - So for $\mathbb{Z}$ you would want to preserve its structure as an ordered integral domain whose set of positive elements is well-ordered? If so, I cannot be of much help. I also notice that in my answer I referred to the ideal $(n),$ when I should have said cyclic subgroup. Mar 4 at 15:24