Do "superinfinite" sets exist?

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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?