3
$\begingroup$

Let $S$ be a set and for $n \in \mathbb{N}$ let $[n]$ be the set of all natural numbers less than $n$.

Suppose that for each nonzero $n \in \mathbb{N}$ there is an injection from $[n]$ to $S$. Show that there is an injection from $\mathbb{N}$ to S.

I am not sure if the above claim is true. It seems true, but I am unsure how to prove it (or to find a counterexample for that matter).

If possible, I'd prefer a proof that doesn't use the axiom of choice, or any of its equivalences.

$\endgroup$
4
  • 3
    $\begingroup$ The statement is true in ZFC. You will need some version of the Axiom of Choice because the statement isn't true for a "Dedekind finite" set, and those can exist if the Axiom of Choice is false. $\endgroup$ Jun 3, 2019 at 21:55
  • $\begingroup$ I haven't used the word finite in my question, so I'm not sure where the need for AC comes in? In any case, how do I prove this fact using AC? $\endgroup$
    – user308485
    Jun 3, 2019 at 22:20
  • $\begingroup$ @RobertShore's point is that there exists (if ZFC is consistent) a model of ZF which has a counterexample to your claim -- that is, a set that you can inject every finite set into, but cannot inject $\mathbb N$ into. Such a set is called a "Dedekind-finite" infinite set. Because such a model exists, you can't hope to prove the claim in ZF alone. $\endgroup$ Jun 3, 2019 at 22:22
  • 1
    $\begingroup$ On the other hand, if you're given a specific family of injections $f_n : [n] \hookrightarrow S$, I was thinking you could define $g : \mathbb{N} \to S$ recursively such that $g(n) = f_{n+1}(i)$ where $i \in [n+1]$ is the smallest element such that $f_{n+1}(i) \ne g(m)$ for all $m < n$. (Unless there's something I'm missing here?) So in this proof, the use of AC would be in choosing the family $f_n$ of injections. $\endgroup$ Jun 3, 2019 at 22:24

1 Answer 1

4
$\begingroup$

As mentioned in comments, this depends essentially of having the axiom of choice available at least in some variant. If you don't have choice then it is possible that there may exist an "infinite Dedekind-finite set", which would exactly be a counterexample to your claim.

(A set $S$ is called Dedekind-infinite if there exists an bijection between $S$ and a proper subset of $S$. It is easily proved -- in ZF -- that this is the case exactly when there is an injection $\mathbb N\to S$).

If you have at least the axiom of countable choice, it is easy enough. Use the axiom to select simultaneously for each $n$ a particular injection $f_n: [n]\to S$. Then construct the function $g:\mathbb N\to S$ recursively by the rule:

  • $g(n) = f_{n+1}(i)$ where $i$ is the smallest number in $[n+1]$ such that $f_{n+1}(i) \notin \{g(0),\ldots,g(n-1)\}$.

It ought to be clear enough that there is always such an $i$ and that $g$ becomes injective. The work of writing down the proof then amounts to finding an appropriate recursion theorem and showing that it applies. (You'll need as a lemma something like there is no surjection $[n]\to[n+1]$, but that's just finite reasoning).

$\endgroup$
1
  • $\begingroup$ To the proposer: (Terminology). It is consistent with ZF that there exists $S$ such that there is an injection $f_n:[n]\to S$ for every $n\in \Bbb N,$ that is, $S$ is Tarski-infinite, but no injective $f:\Bbb N\to S,$ that is, $S$ is Dedekind-finite. $\endgroup$ Jun 6, 2019 at 9:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .