Functions $\mathbb{N} \to \mathbb{N}$ that are injective but not surjective, and vice versa

Question

Suppose that $A$ and $B$ are sets each containing the same finite number of elements and $f: A \to B$.

a. Prove that $f$ is injective if and only if it is surjective.

b. Give an example of an injective function from $\Bbb N \to \Bbb N$ that is not surjective. Does this contradict (a)?

c. Give an example of a surjective function from $\Bbb N \to \Bbb N$ that is not injective. Does this contradict (a)?

My attempts

b. $f(x)= \frac{x}{2}$

c. $f(x) = x -1$

I don't get if it contradict part a.

Answer 1

It may be that the downvotes are because your work does not even exhibit that you understand the concepts of injective and surjective, the definitions of which you may well be expected to use in your answers for b) and c).

Both of your answers are dead-wrong: the function listed in b) is NOT from $\Bbb N \to \Bbb N$ (it has the wrong co-domain). For example, $f(1) = \frac{1}{2}$ is NOT a natural number.

The function you give in c) IS surjective, but it also is injective, To see this, suppose:

$f(x) = f(y) \implies x - 1 = y - 1 \implies (x - 1) + 1 = (y - 1) + 1 \implies x = y$.

(EDIT: as pointed out in the comments, $f$ is not even a function from $\Bbb N \to \Bbb N$, as one can see by noting $f(0) = -1 \not\in \Bbb N$).

I suggest you try some function $f$ for b) that "skips" values in $\Bbb N$, you want "gaps" in the co-domain. For c), you might try using the floor function, somehow.

a) is the most important question, here though. Finiteness is key, that's what b) and c) are supposed to convince you of. Start by assuming $f$ is surjective. What happens if you assume (by way of contradiction), that $f$ is not injective? (hint: compare the cardinalities of the range, and the domain).

Answer 2

$a)$: Since $f$ is injective, $|A| = |f(A)|$, and $|A|=|B|$, so $|f(A)| = |B|$, and since both $|f(A)|, |B|$ are finite,and more over $f(A) \subseteq B$, we deduce that $f(A) = B$, hence $f$ is surjective.

Conversely, if $f$ is surjective, we prove it is injective. Suppose that $f$ is not injective, then $|A| > |f(A)|$, and since $|A| = |B| \Rightarrow |f(A)| < |B| = |B \setminus f(A)| + |f(A)| \Rightarrow |B\setminus f(A)| > 0 \Rightarrow B\setminus f(A) \neq \emptyset$, and both $B$, and $f(A)$ are finite, it must be that $f(A) \neq B \Rightarrow f$ is not surjective, contradiction. So $f$ is injective.

$b)$: Take $f: \mathbb{N} \to \mathbb{N}$: $f(1) = 2, f(2) = 3, \cdots , f(n) = n+1$ is injective but not surjective.

$c)$: Take $f: \mathbb{N} \to \mathbb{N}$: $f(1) = f(2) = 1, f(3) = 2, f(4) = 3,\cdots f(n) = n - 1$ is surjective but not injective.

Answer 3

a.) Use the definitions you know. $f$ is injective if $f(n_1) = f(n_2) \implies n_1 = n_2, \forall {n_1,n_2} \in \mathbb{N}$. $f$ surjective if the image matches the domain, that $f(A) = [b \in B \space | \space \forall b \in B, \exists a \in A \space s.t. f(a) = b]$.

Here's the intuitive proof:

So suppose $f$ injective, so that every value in A is matched with a unique element in B. But A and B have the same number of finite elements. So that means the image of A is simply all elements in B, so surjection holds, that $f(A) = B$

Suppose $f$ surjective, so that every element in the codomain B is matched with an element in the domain A. But by definition of a function, multiple elements in B can't be matched with the same element in A. Since A and B have the same number of elements, every element in B is associated with a unique element in A, and injection holds.

b, c.) You have to make a function so that the the number of elements in A and B aren't the same. So something silly like $f(x) = 2x$ for $x$ between 1 and 10 for the domain and codomain. This is injective, but not surjective, because not every element in the codomain is in the image.

Answer 4

The function $f(x) = \frac{x}{2}$ in (b) is not a function $\mathbb{N} \to \mathbb{N}$, as $f(1) = \frac{1}{2} \not\in \mathbb{N}$. Still, it has the spirit of a correct answer: For which values $\lambda$ does the rule $x \mapsto \lambda x$ define a function $\mathbb{N} \to \mathbb{N}$? For which of these $\lambda$ is it injective? Surjective?

Likewise, the function in (c) again is not a function $\mathbb{N} \to \mathbb{N}$. If your convention is $\mathbb{N} = \{0, 1, 2, \ldots\}$, then $f(0) = -1 \not\in \mathbb{N}$. On the other hand, $0$ is the only value of $x$ for which $f(x) \not\in \mathbb{N}$, so you can modify this example to produce a function $\mathbb{N} \to \mathbb{N}$ by choosing some $a \in \mathbb{N}$ and defining $$ f(x) = \left\{ \begin{array}{cl} a, & x = 0 \\ x - 1, & x \in \mathbb{N} - \{0\} \end{array} \right. . $$ Is this function injective? Surjective? (Sometimes $\mathbb{N}$ is taken to be $\{1, 2, 3, \ldots\}$, in which case the above comments can be modified readily.)

Answer 5

1. Sets $A$ and $B$ have the same finite cardinality.

2. Since $f$ is a function, then every element in $A$ maps once to some element in $B$.

3. $f$ will be injective iff every element in $A$ maps exclusively to an element in $B$ (no other element in $A$ maps to that element).

4. $f$ will be surjective iff every element in $B$ is mapped to by an element in $A$.

Use these definitions to prove that $f$ is injective, if and only if, $f$ is surjective.

Answer 6

a) As $f$ is injective, each element of $A$ is uniquely mapped to an element of $B$. As $|A|=|B|$, there is no element of $B$ that is un-used, or used twice. Hence $f$ is surjective. With |A|=|B| and $|A|$ finite, we can merely reverse the argument to prove surjective implies injective. Hence $f$ is both injective or surjective, so it is a bijection.

b) $f(x)=2x$ is injective but not surjective

c) $f(x)=\lfloor{x/2}\rfloor$ is surjective but not injective

Wikipedia explains injective and surjective well.