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$:


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?

  • 1
    $\begingroup$ You should define the function before we can help you. $\endgroup$ – nullUser Feb 20 '15 at 2:14
  • 1
    $\begingroup$ 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?? $\endgroup$ – 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?

  • $\begingroup$ So, you are saying it would be sufficient to prove that the function is surjective by letting n=1 and showing that |{1}|= 1? I am also curious if there is an inverse to the function f(x)=|x|? $\endgroup$ – user3699546 Feb 20 '15 at 2:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Jason Feb 20 '15 at 2:37
  • $\begingroup$ I'm not sure what you are referring to by "obvious choice". I know that I have to show that for some n \in \mathbb N there is an a \in A such that f(a)=n, but I do not understand how to prove it, even if it seems obvious. $\endgroup$ – user3699546 Feb 20 '15 at 2:54
  • $\begingroup$ Would it be necessary to prove that finite subsets of N are countable? Or am I making this overcomplicated? $\endgroup$ – user3699546 Feb 20 '15 at 3:43
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jason Feb 20 '15 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.