Correspondence between a countably infinite set A and the set of positive integers

Question

I'm currently taking a course on logic & computability and they're using as a manual the famous "Logic and computability" by Boolos, Burgess and Jeffrey. The last week I've been trying to solve this problem presented in chapter 1 but I'm having a really hard time trying to understand the question. The problem is:

1.4 A set A has n elements, where n is a positive integer, if it is equinumerous with the set of positive integers up to n, so that its elements can be listed as a1, a2, ... , an. A nonempty set A is finite if it has n elements for some positive integer n. Show that any enumerable set is either finite or equinumerous with the set of all positive integers. (In other words, given an enumeration, which is to say a function from the set of positive integers onto a set A, show that if A is not finite, then there is a correspondence, which is to say a one-to-one, total function, from the set of positive integers onto A.)

So, my understanding is that I have to prove $$ p \lor q $$

I was thinking that, as a first step, I could suppose that $$ \lnot p\to q $$ That is, assume that A is not finite and show that a correspondence between the set of positive integers and the set A follows. Now, I know that if A is an enumerable set, then there exists a function $$ f:\mathbb Z^+ \to A $$

Such that that function is surjective. What I should prove now is that there exists a function: $$ g:\mathbb Z^+ \to A $$ Such that that function is one-to-one and total. But I'm not sure how to proceed, at first I thought that I could workaround the inverse function, but that's a no-go. I'm unable to see how to construct an injective, total function from the set of positive integers to A and show the correspondence. I think my misunderstanding is that I don't understand how the infinity of the set A is playing a role in this proof. Could you please provide me with some keys in order to construct this proof?

Answer 1

Hint: we can construct $g$ step-by-step by taking "not yet used" values of $f$.

Assume that we have already defined $g(k)$ for $k < n$ in a way such that

1) for any $m < n$ there exists $k < n$ such that $g(k) = f(m)$ - ie we covered $\{f(1), f(2), \ldots, f(n - 1)\}$

2) if $k_1 < n$, $k_2 < n$, $k_1 \neq k_2$ then $g(k_1) \neq g(k_2)$

How can we define $g(n)$ to keep this properties?

Answer 2

Hint: You can built $g$ recursively. Let $g(1)=f(1)$, and $g(n+1)=f(k)$ where $k:=\min\{t\in\mathbb{Z}^+:f(t)\neq f(n)\}$ (This minimum exists because $A$ is not finite).