What is the definition for an infinite set?
I'm physicist, not a mathematician, but this time I have following question related to Math: What is an infinite set per definition? Of course I know, that a set is infinite, when it is not finite - clear.
But lets say I have infinite set M.
Assume there is a surjection $f: M \rightarrow \mathbb{N}$
So every element of $m \in M$ points to a given $n \in N$.
Such a set M must be, of course infinite, but does the definition suffice for all infinite sets, including non countable ones so I can say:
"Each infinite set has a surjection $f: M \rightarrow \mathbb{N}$" ?
For example a surjective function for the non countable infinite set $\mathbb{R^+_0}$ could be$x \in [n-1, n) \mapsto n$
But does my definition include all possible infinite sets and is this definition reasonable at all?
Sorry for mathematical incorrectness, but I think one can understand what I mean.
$\endgroup$ 46 Answers
$\begingroup$Depends - how do you feel about the axiom of choice? (Or rather, very tiny fragments of it.)
In set theory without the axiom of choice (that is, $\mathsf{ZF}$ as opposed to $\mathsf{ZFC}$), the standard definition of "finite" is "in bijection with an element of $\omega$" - where $\omega$ is the smallest inductive set, that is, the smallest set with $\emptyset$ as an element and closed under the map $x\mapsto x\cup\{x\}$. Think of $\omega$ as giving a "purely $\in$-based" description of $\mathbb{N}$. Elements of $\omega$ are the finite (von Neumann) ordinals.
We also have the notion of Dedekind finiteness: a set $A$ is Dedekind-finite iff there is no injection $A\rightarrow A$ which is not a surjection (think by contrast about Hilbert's Hotel). This is equivalent to $A$ not having an injection from $\omega$ (or $\mathbb{N}$ if you prefer). You raised a third notion, namely "does not surject onto $\omega$" (this one's definitely in the literature too, I just don't recall its name at the moment - I'll add it when I can find it). And there are many others.
Over $\mathsf{ZF}$ alone, these need not be the same; e.g. it is consistent with $\mathsf{ZF}$ that there is an infinite set which is Dedekind-finite. Indeed, in $\mathsf{ZF}$ alone there is a lot to be said about the various types of finiteness. But in $\mathsf{ZFC}$ these all coincide, and so in particular your proposed definition works ... if you're happy assuming (at least a small fragment of) the axiom of choice.
$\endgroup$ 1 $\begingroup$There are a couple of ways to define "infinite set", depending on your set theory, and depending on whether you want your primary concept to be that of "infinite set" or that of "finite set."
Giving primacy to finite set. We define a set $X$ to be finite if it can be put in one-to-one correspondence with a proper initial segment of $\mathbb{N}$; that is, there exists a bijection $f\colon X\to\{0,1,\ldots,n-1\}$ for some natural number $n$. A set $X$ is infinite if and only if it is not finite. The set $\mathbb{N}$ is defined as the least inductive set, and there is a very specific object in Set Theory corresponding to it.
Giving primacy to infinite sets. A set $X$ is "Dedekind infinite" if there is a proper subset $Y$ of $X$ such that $X$ and $Y$ can be put in bijective correspondence (there is a bijection $f\colon X\to Y$). A set is Dedekind-finite if and only if it is not Dedekind-infinite.
In Zermelo-Fraenkel Set Theory ($\mathsf{ZF}$), without assuming the Axiom of Choice, one can show that a Dedekind-infinite set $X$ contains a countably infinite subset; that is, there is an injection $f\colon\mathbb{N}\to X$, and conversely, any set $Y$ that admits an injection $f\colon \mathbb{N}\to Y$ is Dedekind-infinite. This definition agrees with your proposal: say $X$ is Dedekind-infinite, and let $f\colon\mathbb{N}\to X$ be an injection. Define $g\colon X\to \mathbb{N}$ as follows: given $x\in X$, if $x\notin f(\mathbb{N})$, then $g(x)=0$. If $x\in f(\mathbb{N})$, then because $f$ is one-to-one, there exists a unique $n\in\mathbb{N}$ such that $x=f(n)$; define $g(x)=n$. Then $g$ is surjective, since for every $n\in\mathbb{N}$, $g(f(n))=n$.
One can also show in $\mathsf{ZF}$ that if $X$ is Dedekind-infinite, then it is also infinite in the sense of the first definition. However, there are set theories in which there are sets that are not Dedekind-infinite and also are not finite in the sense of the first definition.
In Zermelo-Fraenkel with Choice ($\mathsf{ZFC}$), if a set is not Dedekind-infinite then it is finite in the sense of the first definition, and thus that the two definitions (finite and Dedekind-finite; infinite and Dedekind-infinite) coincide.
However, while Dedekind-infinite implies your notion even without the Axiom of Choice, your definition does not imply Dedekind-infinite if we do not have the Axiom of Choice at hand: your definition is what is called a "weakly Dedekind-infinite set", and it sits somewhere between Dedekind-infinite and finite; that is, if a set is Dedekind-infinite then it is weakly Dedekind-infinite (as noted above), and if it is weakly Dedekind-infinite then it is not finite; but you could have weakly Dedekind-infinite sets that are not Dedekind-infinite, and you could have a set that is not weakly Dedekind-infinite but is also not finite.
$\endgroup$ $\begingroup$Yes that is sufficient as long as the map is surjective, the actual definition should be
An infinite set is a set that is not a finite set.So you could show that there does not exist a bijection between your "infinite" set and a finite set.
Other ways:
A set is infinite if and only if for every natural number, the set has a subset whose cardinality is that natural number.
If the axiom of choice holds, then a set is infinite if and only if it includes a countable infinite subset.
Also if interested:
the actual definition of finite set is centered on the fact that you define numbers in such a way that they are sets, exactly of their cardinality, and so on... but this was not the question.
If you'd like to know more about this finite set definition just comment.
$\endgroup$ 1 $\begingroup$One could possibly use that definition, but it would be unusual. To get an understanding of cardinality we need a stronger concept than surjectivity, namely bijectivity. Two sets are said to have the same cardinality if it exists a bijection between them. This gives rise to a natural way of assigning a «size», or cardinality, to finite sets. We say that a set $A$ has cardinality $n$ if there exists a bijection $f:A \rightarrow \{ m \in \mathbb{N} \, | \, 1 \leq m \leq n \}$.
Having done this, we may define an infinite set as follows: A set $A$ is called infinite if there exists no $n \in \mathbb{N}$ so that there exists a bijection $f:A \rightarrow \{ m \in \mathbb{N} \, | \, 1 \leq m \leq n \}$.
$\endgroup$ 1 $\begingroup$A proof assuming AC goes as follows:
If $M$ is not finite, then construct inductively a sequnce $m_i \in M$ of distinct elements. This works, because $M \setminus \{m_1, \dots, m_i\}$ is never empty, otherwise $M$ would be finite. Any map $M \to \mathbb N, m_n \mapsto n$ that maps elements $M \setminus \{m_1, \dots\}$ is surjective. (To prove existence of such a map uses AC).
If $M \to \mathbb N$ is surjective, then $M$ cannot be finite, since otherwise the image of this map is already finite and properly contained in $\mathbb N$.
$\endgroup$ $\begingroup$This is an interesting question, because we can interpret it as asking if there is any infinite cardinality strictly smaller than $\aleph_0$.
Infinite sets are usually defined in terms of finite sets. A set is finite if there is a one-to-one mapping between it and a set of the form $\boldsymbol n = \{0, 1, ..., n\}$ for some $n\in \mathbb{N}$.
So this interesting question is, is there any set which satisfies the standard definition but does not have a surjection onto $\mathbb{N}$?
Let's try to show that.
Let us suppose we have a set $S$ such that for every $n\in \mathbb N$ there is no one-to-one mapping $f:S\to \boldsymbol n$.
First we note that at the very least, for every $n\in \mathbb N$ we will always be able to find at least a surjective $g_n:S\to \boldsymbol n$.
We can show this by induction. The base case for $n=0$ is trivial. Suppose that there is a surjective $g_n:S\to \boldsymbol n$. Since we assumed that there are no one-to-one mappings between $S$ and $\boldsymbol n$, there must be two elements $a_n,b\in S$ such that $g_n(a) = g_n(b)$. Hence we can define $g_{n+1}(x) = g_n(x)$ if $x\not = a$ and $g_{n+1}(a) = n+1$.
Ok so now we have a surjection $g_n: S \to \boldsymbol n$ for every $n$. Not only that, but we have also defined along the way a series $A = \{a_0, ..., a_n\}$ such that $g_n(a_n)=n$ for every $n$.
Let us define $g:S \to \mathbb N$ such that $g(a_n) = n$ ($g(x) = 0$ if $x \not\in A$.
Hence we have defined a surjection $g:S \to \mathbb N$, and thus we have seen that any infinite set satisfying the classical definition also satisfies that there is a surjection between it and the natural numbers.
PS: I am 78% sure that this construction relies on the axiom of choice, but right now I cant see exactly how.
$\endgroup$ 1
