# Proving that a function that calculates the cardinality of a given set is surjective on specified domain and codomain.

Define the set $A \subseteq\mathcal P(\mathbb N)$ as

$$A = \{E \in\mathcal P(\mathbb N)\,:\, E\ \text{has a finite amount of elements}\}$$

Define a function $f: A\rightarrow \mathbb N$:

$$f(E)=|E|$$

I am trying to prove whether the function is injective or surjective. To prove that the function is not injective, I know that if I show the cardinalities of 2 different sets that are subsets of $\mathbb N$ are equal, then the function is not injective.

It appears as if the function is surjective since the codomain is restricted to natural numbers and the domain is restricted to countable subsets of the power set of natural numbers. I am unsure on how to to approach proving surjectivity here as the typical method of letting some $y=c(x$) and evaluating the value of $x$ requires me to take the inverse of the cardinality function. Is there another method to prove surjectivity that would prove useful here?

• You should define the function before we can help you. – nullUser Feb 20 '15 at 2:14
• Confusing. The notation $A\subseteq\mathcal P(\mathbb N)$ says that $A$ is a subset of $\mathcal P(\mathbb N)$, i.e., the elements of $A$ are elements of $\mathcal P(\mathbb N)$, i.e., the elements of $A$ are subsets of $\mathbb N$; so one would expect a definition like $A=\{E\in\mathcal P(\mathbb N):\text{blah}\}$ or $A=\{E\subseteq\mathbb N:\text{blah}\}$. Instead, we see $A=\{E\subseteq\mathcal P(\mathbb N):\text{blah}\}$, defining $A$ as a set of subsets of $\mathbb N$. Which is it?? – bof Feb 20 '15 at 2:47

To show $f$ is not injective, it suffices to find two non-equal finite subsets of $\mathbb N$ that have the same cardinality. The sets $\{1\}$ and $\{2\}$ will do.
To show that $f$ is surjective, let $n$ be a natural number and find a finite subset of $\mathbb{N}$ with $n$ elements. What might be an obvious choice?
• No, that is sufficient to show that $f$ is not injective. To show surjectivity, you must show that any natural number is the size of a finite subset of $\mathbb N$. A function has an inverse if and only if it is both injective and surjective, so this function cannot. – Jason Feb 20 '15 at 2:37
• Yes, I think you probably overthinking the problem. If $n=0$ then the empty set is the only choice, and if $n\ge1$ then consider the finite subset $\{1,\ldots,n\}\subset\mathbb N$. – Jason Feb 20 '15 at 4:21