# 1:1 and onto proof of Z+ and Q+

1. Apr 29, 2014

### takk

1. The problem statement, all variables and given/known data
After exploring this problem a bit out of curiosity I decided to attempt to write a full fledged proof of it for my final exam.
I will try my best to explain what I am doing. i am pretty frustrated with it but I've put so much time into it I don't want to give up and do something else now.

For this theorem Equality in Q+: $\frac{a}{b}$=$\frac{c}{d}$ $\Leftrightarrow$ a=c, and b=d

now I'm using the grid system, i.e.
1/1 1/2 1/3 1/4 1/5 1/6..
2/1 2/2 2/3 2/4 2/5 2/6..
3/1 3/2 3/3 3/4 3/5 3/6..
.
.
but adjusting it to represent the diagonals and defining it as follows
1/1 $\Rightarrow$ p+q=2 (1 element)
1/2 2/1 $\Rightarrow$ p+q=3 (2 elements)
1/3 2/2 3/1 $\Rightarrow$ p+q=4 (3 elements)
etc
as you can see each list represent one diagonal of the grid

next I went to the integers by observing the following number line and looking at the sums that represent the integers

(-----|](--|-----|](---|-----|-----|](---|-----|-----|-----|]-----|-----|
0 1 2 3 4 5 6 7 8 9 10 11 12

Representing each section with a summation we get
(0,1]
$\sum^{1}_{k=1}$k
(1,3]
$\sum^{2}_{k=1}$k
(3,6]
$\sum^{3}_{k=1}$k
(6,10]
$\sum^{4}_{k=1}$k

now I'm trying to show f:Z$^{+}$$\rightarrow$ Q$^{+}$
f(1) = 1/1

let n$\geq$2$\in$Z$^{+}$
let S$_{n}$={s$\in$Z$^{+}$$\leq$$\sum^{j}_{k=1}$k}

then consider 2n $\sum^{2n}_{k=1}$k= 1+2+...+n+n+1+...+2n
thus n$\leq$$\sum^{2n}_{k=1}$k
therefore 2n$\in$S$_{n}$ therefore S$_{n}$$\neq$$\oslash$
Then by the well ordering principle $\exists$ m$\in$S$_{n}$ $\exists$ m$\leq$j $\forall$j$\in$S$_{n}$

i.e exists a "least" element
Call the least element M

therefore
$\sum^{m-1}_{k=1}$k<n$\leq$$\sum^{m}_{k=1}$k
or in other words m$\in$ ($\sum^{m-1}_{k=1}$k, $\sum^{m}_{k=1}$k]

so let p= n-$\sum^{m-1}_{k=1}$k
1$\leq$p$\leq$m

then choose a q such that p+q = m+1
q= m+1-p

now f(n) = p/q
That ends the mapping

Now show f:Q$^{+}$$\rightarrow$Z$^{+}$ is 1:1 and onto.
This is where I can't finish the proof but this is what I have of an attempt on both

One to one:
x$_{1}$$\neq$x$_{2}$ $\Rightarrow$ f(x$_{1}$)$\neq$f(x$_{2}$)
or
f(x$_{1}$)=f(x$_{2}$)$\Rightarrow$ x$_{1}$=x$_{2}$

suppose f(n$_{1}$)=f(n$_{2}$)

then $\frac{p_{1}}{q_{1}}$=$\frac{p_{2}}{q_{2}}$
I have no idea how to get from here to n$_{1}$=n$_{2}$

Onto:
consider p+q
the diagonals the p/q is in has the property that the # of elements in that diagonal is p+q-1 (referring way back to the beginning)
or in other words ($\sum^{p+q-2}_{k=1}$k, $\sum^{p+q-1}_{k=1}$k]
then let n= p+$\sum^{p+q-2}_{k=1}$k

and then I get hung up again

2. May 1, 2014

### Staff: Mentor

You seem to prove some unnecessary or trivial stuff while other parts are wrong.

So $\frac{1}{2}=\frac{2}{4} \Leftrightarrow$ 1=2 and 2=4? That is wrong.

What does that mean?

I guess the sum is supposed to run up to n instead of j?
Okay, so as an example:
S3 = {1,2,3,4,5,6}
It is obvious that Sn is not empty (as an example, it always contains 1) and that it has a smallest element (it always contains 1 and 1 is the smallest number in Z+).

Why should $n \leq \sum^{1}_{k=1} k = 1$ be true?

This plus the wrong way to start make it impossible to finish your mapping or show that it has the desired properties.