Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does the following definition adequately characterize the notion of finite? Is it equivalent to, say, Dedekind-finiteness?

A set $S$ is finite if and only if for all $x_0\in S$ and all $f:S\to S$, if $f$ is injective then $\exists x\in S: f(x)=x_0$.

Intuitively, with this definition, I meant to convey the notion of "counting without numbers", i.e. starting at any element $x_0\in S$, and going from one element to another without "counting" any element more than once. If $S$ is finite, I would think that you would eventually have to "come back" to $x_0$.

$f(x)=y$ can be taken to mean that you go from $x\in S$ to a unique $y\in S$.

The injectivity of $f$ ensures that you don't go to (or count) any element of $S$ more than once.

Follow-Up

See "Infinity: The Story So Far" at my math blog.

There I present an informal development of the notion of infinity beginning with the above, non-numeric approach to the finite set (equivalent to Dedekind) along with accompanying formal proofs.

share|improve this question
1  
There is indeed a characterisation of finiteness as "$S$ is finite if $f\colon S\to S$ is injective if and only if $f$ is surjective" This is often called Dedekind finite. You may like to read this short section in the Wikipedia article en.wikipedia.org/wiki/… –  Daniel Rust Feb 23 at 18:28
2  
There are several definitions of finite. The one you mention is due to Dedekind. There is a paper by Lawrence Neff Stout entitled "Dedekind finite objects in topoi" that appeared in the Journal Of Pure and Applied Algebra. In it, if memory serves, he mentions several definitions of "finite." I cannot put my hand on the paper at the moment or I could give you more specifics on the reference. –  Chris Leary Feb 23 at 18:28
    
@DanielRust The OP's condition is only that all injections are surjective, not that all surjections are injective. –  Jack M Feb 23 at 18:31
    
A shorter way of saying this is: $S$ is finite if and only if every injective function from $S$ to $S$ is surjective. –  Michael Hardy Feb 23 at 18:35
1  
@Daniel: Yes. It is consistent with the failure of the axiom of choice that there is a set that every injection is a surjection, but not every surjection is an injection. –  Asaf Karagila Feb 23 at 18:41

1 Answer 1

up vote 2 down vote accepted

You need to define what does it mean "an adequate characterization of finite". If by adequate you mean equivalent in set theory $T$ to a different, presupposed definition of finite (e.g. Dedekind-finiteness), then yes.

Taking $T$ as $\sf ZF$ the definition you propose is equivalent to Dedekind-finiteness. To see this, note that your definition is just a restatement of the condition "Every injective function from $S$ to $S$ is surjective".

However there is a myriad of definitions for the term "finite" which are not equivalent to one another in $\sf ZF$. For example, your definition is not equivalent (in $\sf ZF$) to the following definition, given by Tarski:

$A$ is finite if and only if for every non-empty $U\subseteq\mathcal P(A)$ there exists a $\subseteq$-maximal element in $U$.

The only agreement you are likely to find through and through is that:

  1. Bounded sets of natural numbers are finite.
  2. The set of natural numbers is not finite (henceforth infinite).
  3. Subsets of finite sets are finite.
  4. Supersets of infinite sets are infinite.

Between here and there, there are many different definitions, some equivalent to others and some are not. But all are "adequate" if by that you mean satisfy the above four properties.

share|improve this answer
    
Equivalence to Dedekind-finiteness would be enough for my purposes. Thanks. –  Dan Christensen Feb 23 at 19:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.