- #1
takk
- 1
- 0
Homework Statement
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+: [itex]\frac{a}{b}[/itex]=[itex]\frac{c}{d}[/itex] [itex]\Leftrightarrow[/itex] 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 [itex]\Rightarrow[/itex] p+q=2 (1 element)
1/2 2/1 [itex]\Rightarrow[/itex] p+q=3 (2 elements)
1/3 2/2 3/1 [itex]\Rightarrow[/itex] 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]
[itex]\sum^{1}_{k=1}[/itex]k
(1,3]
[itex]\sum^{2}_{k=1}[/itex]k
(3,6]
[itex]\sum^{3}_{k=1}[/itex]k
(6,10]
[itex]\sum^{4}_{k=1}[/itex]k
now I'm trying to show f:Z[itex]^{+}[/itex][itex]\rightarrow[/itex] Q[itex]^{+}[/itex]
f(1) = 1/1
let n[itex]\geq[/itex]2[itex]\in[/itex]Z[itex]^{+}[/itex]
let S[itex]_{n}[/itex]={s[itex]\in[/itex]Z[itex]^{+}[/itex][itex]\leq[/itex][itex]\sum^{j}_{k=1}[/itex]k}
then consider 2n [itex]\sum^{2n}_{k=1}[/itex]k= 1+2+...+n+n+1+...+2n
thus n[itex]\leq[/itex][itex]\sum^{2n}_{k=1}[/itex]k
therefore 2n[itex]\in[/itex]S[itex]_{n}[/itex] therefore S[itex]_{n}[/itex][itex]\neq[/itex][itex]\oslash[/itex]
Then by the well ordering principle [itex]\exists[/itex] m[itex]\in[/itex]S[itex]_{n}[/itex] [itex]\exists[/itex] m[itex]\leq[/itex]j [itex]\forall[/itex]j[itex]\in[/itex]S[itex]_{n}[/itex]
i.e exists a "least" element
Call the least element M
therefore
[itex]\sum^{m-1}_{k=1}[/itex]k<n[itex]\leq[/itex][itex]\sum^{m}_{k=1}[/itex]k
or in other words m[itex]\in[/itex] ([itex]\sum^{m-1}_{k=1}[/itex]k, [itex]\sum^{m}_{k=1}[/itex]k]
so let p= n-[itex]\sum^{m-1}_{k=1}[/itex]k
1[itex]\leq[/itex]p[itex]\leq[/itex]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[itex]^{+}[/itex][itex]\rightarrow[/itex]Z[itex]^{+}[/itex] 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[itex]_{1}[/itex][itex]\neq[/itex]x[itex]_{2}[/itex] [itex]\Rightarrow[/itex] f(x[itex]_{1}[/itex])[itex]\neq[/itex]f(x[itex]_{2}[/itex])
or
f(x[itex]_{1}[/itex])=f(x[itex]_{2}[/itex])[itex]\Rightarrow[/itex] x[itex]_{1}[/itex]=x[itex]_{2}[/itex]
suppose f(n[itex]_{1}[/itex])=f(n[itex]_{2}[/itex])
then [itex]\frac{p_{1}}{q_{1}}[/itex]=[itex]\frac{p_{2}}{q_{2}}[/itex]
I have no idea how to get from here to n[itex]_{1}[/itex]=n[itex]_{2}[/itex]
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 ([itex]\sum^{p+q-2}_{k=1}[/itex]k, [itex]\sum^{p+q-1}_{k=1}[/itex]k]
then let n= p+[itex]\sum^{p+q-2}_{k=1}[/itex]k
and then I get hung up again