0
$\begingroup$

Let $A=\{ a \in \Bbb{N} : a \text{ even}\}$ and $B=\{b \in \Bbb{N} : b \text{ odd}\}$ Define a funtion $f:A \times B \to \Bbb{N}$ by $f(a,b)=(a+2b)/2$.

How do you show this function is surjective?

  • 0
    Yojito: Any luc$k$ with my answer below?2012-05-07

3 Answers 3

3

It is not.

If the convention is that $\mathbb N=\{1,2,3,\ldots\}$, then, for every $(a,b)$ in $A\times B$, $a\geqslant2$ and $b\geqslant1$ hence $f(a,b)\geqslant2$. One sees that $1$ is not in $f(A\times B)$.

If the convention is that $\mathbb N=\{0,1,2,\ldots\}$, then, for every $(a,b)$ in $A\times B$, $a\geqslant0$ and $b\geqslant1$ hence $f(a,b)\geqslant1$. One sees that $0$ is not in $f(A\times B)$.

In both cases, $f(A\times B)\ne\mathbb N$ and, in fact, $f(A\times B)=\mathbb N+1=\mathbb N\setminus\{n\}$ with $n=\min\mathbb N$.

Edit More generally, define the function $f:(2\mathbb Z)\times(2\mathbb Z+1)\to\mathbb Z$ by $f(2i,2j+1)=i+2j+1$ and, for every $n$ in $\mathbb Z$, the sets $N_n=\{k\in\mathbb Z\mid k\geqslant n\}$, $A_n=N_n\cap(2\mathbb Z)$ and $B_n=N_n\cap(2\mathbb Z+1)$.

Then, $f$ is trivially surjective but, for every $n$ in $\mathbb Z$, one sees that $f(A_{2n}\times B_{2n})=N_{3n+1}$ and $f(A_{2n+1}\times B_{2n+1})=N_{3n+2}$.

Hence, $f(A_n\times B_n)\subset N_n$ with $f(A_n\times B_n)\ne N_n$ if $n\leqslant-3$, $f(A_n\times B_n)=N_n$ if $n=-1$ or $n=-2$, and $N_n\subset f(A_n\times B_n)$ with $N_n\ne f(A_n\times B_n)$ if $n\geqslant 0$.

  • 0
    @Asaf: Indeed. Thanks.2012-04-10
0

By definition: $f(a,b)=\frac{a}{2}+b$

The function f is surjective if for every element $n \in \mathbb{N}$ there is a corresponding pair of even and odd integers $(a,b)$ where $f(a,b)=n$.

Taking $b=1$ and $a=2(n-1)$, for $n \in \mathbb{N}-\{1\}$ gives:

$f\left(2(n-1),1\right)=n$ where $n \in \mathbb{N}-\{1\}$.

However, as rightfully pointed out, no pair of even and odd natural numbers $(a,b)$ map to the least element under $f$, and hence $f$ is not surjective.

  • 2
    If $n=\min\mathbb N$ then $n-1\notin\mathbb N$ and neither is $2(n-1)$.2012-04-10
0

It is not True.

Counter Example: There are no a and b such that f(a,b)=1.

  • 0
    You can link all you want, the fact is that excluding zero from the natural numbers causes *a lot* of definitions in set theory and logic to become cumbersome and awkward (e.g. finite set) and I can easily construct many a page which claim that zero *is* a natural number. Just so you won't say I am making unfounded claims here, [read the remark given in this answer](http://math.stackexchange.com/a/127700).2012-04-10