# Intuition - Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5]

Define $I_n = \{1, 2, ..., n \}$. Let $A$ be a nonempty set. TFAE :
(i) $A$ is finite (ie: a bijection $h:A\rightarrow I_{N}$ exists)
or A is countably infinite (ie: a bijection $h:A\rightarrow \mathbb{N}$ exists.)
(ii) $A = \emptyset$ or There exists a surjection $f: \mathbb{N} \rightarrow A$. $\quad$ (iii) There exists an injection $g: A \rightarrow \mathbb{N}$.

What's the intuition? Are there pictures? I'm not enquiring about formal arguments, so this is not a duplicate of any other question.

• @AndresCaicedo: I'm asking about intuition here, so it's not a duplicate of that other question. – Greek - Area 51 Proposal Apr 14 '14 at 6:39
• It is. You make a mistake that has been mentioned to you every time, and it is to think that there can be intuition separated from actual mathematics. They come together. You cannot understand a formal proof without the intuition that guides the result, and cannot have intuition at this level without it leading directly to a proof. – Andrés E. Caicedo Apr 14 '14 at 6:41
• "I don't see it in the proof?" Then you do not understand the proof yet. You need to think about it more. – Andrés E. Caicedo Apr 14 '14 at 6:52
• At this level. Eventually (hopefully) you will develop reasonable intuition that guides you further. But, at this level, you cannot really separate them. – Andrés E. Caicedo Apr 15 '14 at 5:35
• To add on the comments of @Andres, and my comments from the now-deleted duplicate, you focus too much on the intuition. How about you accept, for the next three months that there is absolutely no intuition and no visualization and nothing more than plain definitions? Work just with the definitions. Try to unwind them, try to apply theorems that you have proved before, until you have a proof. After three months of really doing that, you should develop the correct intuition, and you will see how these things go. Right now it seems like you're looking for the shortcut which isn't there. – Asaf Karagila May 7 '14 at 13:36

There's two main ideas involved in the proof of these statements.

1. Taking an injection $A \rightarrow \mathbb{N}$, and building an injection the other way around $\mathbb{N} \rightarrow A$ or $I_N \rightarrow A$.

2. Taking an surjection from a smaller set, and turning it into a surjection from a larger set.

Once you have intuition for these things, it should be easier to understand the formal proof.

First, to "turn around" the injection $A \rightarrow \mathbb{N}$, you can relabel the elements that get hit. Label the first natural number to get hit by $1$, the second number to get hit by $2$, and so forth. Either an infinite number of things get hit, or a finite number of things gets hit, so you now can turn around the arrows to get an injection from either $\mathbb{N} \rightarrow A$ or $I_N \rightarrow A$ respectively.

Second, to take a surjection from a smaller set and turn it into a surjection from a larger set, just map everything from the smaller set the same, and map the the extra stuff to a single element.