0

I'm trying to prove the equivalence of the following two (weaker) definitions of finiteness. I know that these definitions are equivalent to the standard definition of finiteness if the axiom of choice holds, but I'm trying to prove they are equivalent to one another, possibly without the axiom of choice. I'm not sure if it's possible though.

1) A set $S$ is finite if there is no bijection between $S$ and any proper subset of $S$.

2) A set $S$ is finite if there exists an injection from $S$ to $\mathbb{N}$ but no injection from $\mathbb{N}$ to $S$.

user308485
  • 1,229
  • 7
  • 13
  • If you weaken (2) by dropping the part about "there exists an injection from $S$ to $\mathbb N$" then it's equivalent (without AC) to (1), which is the usual definition of "$S$ is Dedekind finite". As stated, (2) is equivalent (without AC) to "$S$ is really finite, i.e., $S$ is an $n$-element set for some natural number $n$", and you need (a weak form of) AC to prove that that's equivalent to Dedekind-finite. – bof Jul 22 '19 at 14:21
  • For proving equivalences or implications, I recommend working with the negations, e.g., there is a bijection between $S$ and some proper subset of $S$ if and only if there is an injection from $\mathbb N$ to $S$. – bof Jul 22 '19 at 14:26
  • I see. So what you are saying is that without axiom of choice, 2 is stronger than 1? – user308485 Jul 22 '19 at 14:33
  • I think you're going to need the axiom of dependent choice. (Sorry: I've only just seen bof's comment: DC is the weak form of AC needed.) – Rob Arthan Jul 22 '19 at 14:33
  • Actually the countable axiom of choice (every countable family of disjoint nonempty sets has a choice function) is good enough to prove that every infinite set is Dedekind-infinite; you don't need dependent choice for that. – bof Jul 22 '19 at 14:52

0 Answers0