1
$\begingroup$

Def : A set $X$ is finite if every injective map from $X$ to $X$ is surjective.

Using this, how can I prove that if $X$ is finite, then there exists a bijective map from $X$ to some natural number.

I was trying to prove by contrapositive statement:

Assume that there is no bijective map from $X$ to any natural number $n$. Then I have shown that if a map $f:X \rightarrow n$ is not bijective, then it can not be injective. Now, I want to show that there exists a family of surjective maps $\{f_n: X \rightarrow n\}$ such that $Dom(f_n)$ is properly contained in $Dom(f_{n+1})$ show that I construct a map $g$ from $X$ to $X$ which is injective but not surjective. But I am not able to show the existence of such a family.

$\endgroup$
1
$\begingroup$

Note that you need to use the axiom of choice at some point there. Otherwise the definition of "finite" which you are using (also known as Dedekind-finiteness) may include sets which are strictly larger than all the natural numbers, but not larger than $\Bbb N$.

So here you need to assume that if a set is infinite, then it has a countably infinite subset (which is precisely where you are using the axiom of choice). But this makes an easy way of finding an injection which is not surjective. Just note that we can find such function for $\Bbb N$.

$\endgroup$
  • $\begingroup$ Suppose I assume that if set is infinite then it has countably many elements. But I do not see the prof as I have that there is no injective map from $X$ to any natural $n$. How to use above fact in constructing a map which is injective but not surjective? $\endgroup$ – Steve Dec 3 '14 at 13:23
  • $\begingroup$ Can you find a non-surjective injection from $\Bbb N$ to itself? $\endgroup$ – Asaf Karagila Dec 3 '14 at 13:43
1
$\begingroup$

I think it's easiest to use Zorn's Lemma on the set of all injections $n\to X$ for any possible $n$, ordered by set inclusion. Clearly a maximal map of that kind must have all of $X$ as its image; otherwise it would be easy to extend it by at least one element.

For once, the upper-bound-for-chains condition is the interesting part of an application of Zorn. If the union of a chain does not have a natural as its domain, it must be all of $\omega$, but it is still an injection, and armed with this it is easy to construct a non-surjective injection $X\to X$, contradicting assumptions.

$\endgroup$
0
$\begingroup$

A set X is Tarski finite when any non-empty family F of subsets of X has a subset-minimal member Y.(Y is not a proper subset of any member of F.) We can show in ZF (set theory without the axiom of choice) that a Tarski-finite set is a bijective image of a natural number. Your definition of finite is called Dedekind-finite. It has been shown to be consistent with ZF that there exists a Dedekind-finite set which is not Tarski-finite (using an inner model of a forcing extension of a model of ZFC).

$\endgroup$
  • $\begingroup$ I prefer Jech's terminology from "The Axiom of Choice", where Tarski-finite was a set where every non-empty chain of subsets has a min/max element. Then you can show that finite implies Tarski-finite implies Dedekind-finite, but without choice none of the implications are reversible. Assigning "Tarski-finite" to something which is provably finite is a waste of a good term. $\endgroup$ – Asaf Karagila Aug 5 '15 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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