A Bijection N --> NxN
Christian Reinbothe
I don't want to be a "Crank", but I must try it now.
I have constructed a bijective map N -> NxN. Because this
map is so simple and I haven't found it in literatur,
I think I have a little chance.
You can find the PDF-document on my hompage
http://www.Reinbothe.DE
(Preprints of Mathematical Ideas)
or direct as
http://www.Reinbothe.DE/english/download/bijection.pdf
Should one of the above links are faulty, please let me know
(This is the first time, that my homepage is really used. :)).
I am awaiting Your reactions. If I deceive, tell me,
where I can find this map in literature.
Thanks and Greetings Christian
Arturo Magidin
Christian Reinbothe <Christian...@T-Online.DE> wrote:
>Hello,
>
>I don't want to be a "Crank", but I must try it now.
>I have constructed a bijective map N -> NxN. Because this
>map is so simple and I haven't found it in literatur,
>I think I have a little chance.
I assume, of course, that by "N x N" you mean all pairs (a,b) with a
and b both natural numbers.
There is nothing "cranky" about a bijection between N and N x N. In
fact, it is the first part in the argument that the cardinality of the
rationals is the same as the cardinality of the natural numbers.
There are many easy bijections between them.
Perhaps you were confused? What can be proven is that there is no
bijection between N and P(N), i.e., N and the set of all SUBSETS of
N. Or between N and N^N, the set of all function from N to N (which
can be bijected with the set of all real numbers between 0 and 1).
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Justin
: I don't want to be a "Crank", but I must try it now.
: I have constructed a bijective map N -> NxN.
As was mentioned, this is nothing special, there are lots of such maps.
: http://www.Reinbothe.DE/english/download/bijection.pdf
This link works fine. To be honest your map is fairly confusing given
that all it's got to do is go N->NxN. Does it have any special features?
Justin
Arturo Magidin
Christian Reinbothe <Christian...@T-Online.DE> wrote:
>
>I don't want to be a "Crank", but I must try it now.
>I have constructed a bijective map N -> NxN. Because this
>map is so simple and I haven't found it in literatur,
>I think I have a little chance.
>
>
>
>You can find the PDF-document on my hompage
>
> http://www.Reinbothe.DE
> (Preprints of Mathematical Ideas)
>
>or direct as
>
> http://www.Reinbothe.DE/english/download/bijection.pdf
I notice that you use (N)^2; could your confusion (if there is any)
perhaps lie in that there is no bijection from N to 2^N (rather than
to N^2)?
Note that A^B, for set A and B, represents the set of all functions
from B to A. So N^2 is the set of all functions from 2={0,1} to N
(which is indeed "essentially" the same as the set of all ordered
pairs, N x N); while 2^N is the set of all functions from N to {0,1}
(which is essentially the set of all subsets of N, by associating to
each subset its characteristic function).
A N Niel
<Christian...@T-Online.DE> wrote:
This is a fine bijection.
Use the expansion in base b (for example base 10), then to get
two numbers use alternate digits.
He's asking where does this exist in the literature.
guenther vonKnakspot
surjective.
regards.
Arturo Magidin
A N Niel <ann...@nym.alias.net.invalid> wrote:
>In article <dvp89h$s8q$03$1...@news.t-online.com>, Christian Reinbothe
><Christian...@T-Online.DE> wrote:
>> I don't want to be a "Crank", but I must try it now.
>> I have constructed a bijective map N -> NxN. Because this
>> map is so simple and I haven't found it in literatur,
>> I think I have a little chance.
>>
>> You can find the PDF-document on my hompage
>>
>> http://www.Reinbothe.DE
>> (Preprints of Mathematical Ideas)
>>
>> or direct as
>>
>> http://www.Reinbothe.DE/english/download/bijection.pdf
>Use the expansion in base b (for example base 10), then to get
>two numbers use alternate digits.
>
>He's asking where does this exist in the literature.
Since the two sets are known to be bijective, and there are so many
bijections from a countable set to a countable set (uncountably many),
there is no reason to think that all bijections between N and N x N
will be in the literature somewhere; even if they seem "simple". Given
any bijection f from N to N x N, and any bijection g from N to itself,
you get a "new" bijection from N to N x N by taking fg.
It is also unclear what "little chance" he is hoping for. A chance
that it is "new"? There's a good chance of that. And it is certainly a
good personal achievement, not to be belittled. But, in the grand
scheme of things, it is not all that important, nor is its absence
from the literature (if this is indeed the case) reflective of a need
to get it ->into<- the literature. As that Math Review once said, one
may perhaps say that "this bijection fills a much needed gap in the
literature."
Christian...@t-online.de
1.
N x N -> N
(n,m) |-> (n+m)(n+m+1)/2 + n
2. The one constructed by me.
Please let me know other examples.
Greetings
Christian...@t-online.de
A_q ---> (A_q) x (A_q) is a bijection
(a_i) |---> ((a_2i), (a_2i+1))
Then you have to use the theorem of q-adic evolution of natural
numbers.
Greetings Christian
Christian...@t-online.de
A_q ---> (A_q) x (A_q) is a bijection
(a_i) |---> ((a_2i), (a_2i+1))
Then you have to use the theorem of q-adic evolution.
Greetings Christian
Arturo Magidin
Define "easy". I did not find YOUR example to be particularly
"easy". So what?
Pick any injection from NxN to N, any injection from N to NxN, and
apply Cantor-Bernstein to construct a bijection. This is easy if the
injections are easy. So, for example, map (n,m) to 2^n*3^m, map n to
(n,0), you get a bijection.
Pick your favorite bijection f from N to N; pick your favorite bijection
from g NxN to NxN. Compose any given bijection h:N->NxN with f and g,
to get ghf a bijection.
Since there are uncountably many bijections, it is not hard to come up
with some. What is easy or "not easy" depends on subjective unmeasurables.
A N Niel
<Christian...@T-Online.DE> wrote:
every natural number is a power of 2 times an odd number:
(n,m) -> 2^n*(2*m+1)-1 [if N includes 0]
(n,m) -> 2^(n-1)*(2*m-1) [if N does not include 0]
William Elliot
> I know only two easy bijections N ->NxN.
>
> 1.
> N x N -> N
> (n,m) |-> (n+m)(n+m+1)/2 + n
>
> 2. The one constructed by me.
>
Vaporware.
> Please let me know other examples.
>
f:N^2 -> N, (n,m) -> (2n - 1) 2^(m-1)
is a continuous bijection.
Arturo Magidin
In what topology?
(Not that it matters, but why would we care about "continuity"?)
William Elliot
> William Elliot <ma...@hevanet.remove.com> wrote:
> >On Sun, 26 Mar 2006 Christian...@T-Online.DE wrote:
> >
> >> I know only two easy bijections N ->NxN.
> >> (n,m) |-> (n+m)(n+m+1)/2 + n
> >
> >
> >is a continuous bijection.
> In what topology?
>
> (Not that it matters, but why would we care about "continuity"?)
>
Because it is and it's so obvious and so real, just like the other one.
Because "I'm just very selective about what I accept as reality." ;-)
denis feldmann
> On Mon, 27 Mar 2006, Arturo Magidin wrote:
>
>>William Elliot <ma...@hevanet.remove.com> wrote:
>>
>>>On Sun, 26 Mar 2006 Christian...@T-Online.DE wrote:
>>>
>>>
>>>>I know only two easy bijections N ->NxN.
>>>> N x N -> N
>>>> (n,m) |-> (n+m)(n+m+1)/2 + n
>>>
>>>f:N^2 -> N, (n,m) -> (2n - 1) 2^(m-1)
>>>
>>>is a continuous bijection.
>>
N being, of course, {0,1,2,...}-{0}
>>In what topology?
>>
>
> The usual discrete N and N^2 subspaces of R and R^2.
Again, "as subspaces" is useless
William Elliot
> William Elliot a écrit :
> > On Mon, 27 Mar 2006, Arturo Magidin wrote:
> >>William Elliot <ma...@hevanet.remove.com> wrote:
> >>>On Sun, 26 Mar 2006 Christian...@T-Online.DE wrote:
> >>>
> >>>>I know only two easy bijections N ->NxN.
> >>>> N x N -> N
> >>>> (n,m) |-> (n+m)(n+m+1)/2 + n
> >>>
> >>>f:N^2 -> N, (n,m) -> (2n - 1) 2^(m-1)
> >>>
> >>>is a continuous bijection.
>
> N being, of course, {0,1,2,...}-{0}
>
> >>In what topology?
> > The usual discrete N and N^2 subspaces of R and R^2.
>
> Again, "as subspaces" is useless
>
Would that it be worth half as much as a useless president.
----
Christian...@t-online.de
Your method with Cantor-Bernstein produces biecjtions - no question.
The proof of Cantor-Bernstein uses the axiom of choice heavily, so
all bijections you get with Cantor-Bernstein are difficult to write
down.
I have a suggestion:
Use map (n,m) to 2^n*3^m, map n to (n,0) on Cantor-Bernstein and
try to write it down. Good Luck!
I am sorry, If I have bad Netiquettes. I am learning it :).
Christian...@t-online.de
Greetings Christian
Arturo Magidin
Christian...@T-Online.DE <Christian...@T-Online.DE> wrote:
>I had to think for a while. The point is:
>
>Your method with Cantor-Bernstein produces biecjtions - no question.
>The proof of Cantor-Bernstein uses the axiom of choice heavily,
No. The proof of Cantor-Bernstein is complete Axiom-of-Choice
free. You are incorrect.
> so
>all bijections you get with Cantor-Bernstein are difficult to write
>down.
No. If you can write down the injections, you can write down the
bijection given by Cantor Bernstein.
In any case, you were already given several others.
But I repeat: what is the ->point<-? Why should anybody care about
->YOUR<- bijection (other than yourself)? It is hardly trivial. Is
there anything that your bijection does that the usual, well-known
bijections do not?
>I have a suggestion:
I have a suggestion too: tell us why we should care about your
bijection, then I'll consider wasting more of my time with you.
>Use map (n,m) to 2^n*3^m, map n to (n,0) on Cantor-Bernstein and
>try to write it down. Good Luck!
You haven't even bothered to look up Cantor-Bernstein, have you? Tell
me: why should I spend my time doing work to satisfy your curiosity,
if you clearly have so little as to not bother checking the standard
literature for bijections and for the CONSTRUCTIVE proof of
Cantor-Bernstein?
I should tell you to go do something anatomically impossible, seeing as
to how you are being so cavalier with my time while at the same time
valuing your so highly that you can't be bothered to look up a
standard proof, a standard text, or even the basic rules of nettiquette.
In the meantime, why don't you point out to me the step in which you
think the Axiom of Choice is used, in, say, the proof of
Cantor-Bernstein as described in
http://en.wikipedia.org/wiki/Cantor-Bernstein_theorem
?
Or in the traditional proof: let X=N, Y=NxN, f:X->Y given by
f(n)=(n,0), g(n,m) = 2^n*3^m
No element can trace its ancestry arbitrarily back. An element of X
has ultimate ancestor in X if and only if it is divisible by some
prime other than 2 or 3, or else is of the form
2^{2^{2^...^{k}}} where k is not a power of 2 times a power of 3.
Describe these elements as X_X.
And element of X has ultimate ancestor in Y if and only if it is a
power of 2 times a power of 3, which is divisible by 3, or else it is
a power of 2 of the same form as above, but with k a power of 2 times
a power of 3, divisible by 3. These elements are in X_Y.
Define h:N -> NxN as follows:
h(x) = (x,0) if x is in X_x.
h(x) = (n,m) if x = 2^n*3^m, and either m>0, or else n is not of the form
2^{2^...^{k}} where k is not a power of 2 times a power of 3.
This is the desired bijection.
Daryl McCullough
that seems particularly simple:
f(m,n) = (2*m + 1)*2^n
In other words, to compute f(m,n),
1. Write m in binary.
2. After the end of m, write a 1.
3. After the 1, write n 0s.
This is clearly a bijection from NxN to N+. To get a bijection
from NxN to N, just use f(m,n) - 1.
--
Daryl McCullough
Ithaca, NY
--
NewsGuy.Com 30Gb $9.95 Carry Forward and On Demand Bandwidth
William Elliot
> I am sorry, If I have bad Netiquettes. I am learning it :).
>
Good netiquette is to include sufficient and appropriate context.
You may find informative
http://oakroadsystems.com/genl/unice.htm#quote
http://oakroadsystems.com/genl/unice.htm
-- To Google and MathForum users:
Reply only if adequate context is included _within_ the reply.
Otherwise all contexts are removed from my view,
the flow of thought disrupted and chaos reigns.
In particular for Google users:
Instead of simply hitting the prominent "Reply" link, which doesn't
include a copy of the post to which one is replying, click the "Show
Options" link (toward the top of an item in the thread), which causes
a shaded area of links to appear next to the top of the item, including
"Reply" (first) that does introduce a copy of the previous text (offset
by > signs in the usual fashion).
----
Mitch
Christian...@T-Online.DE wrote:
> I know only two easy bijections N ->NxN.
>
> 1.
> N x N -> N
> (n,m) |-> (n+m)(n+m+1)/2 + n
- diagonalization
> 2. The one constructed by me.
- interleaving base q digits (extends to a bijection R <-> R^2)
3. powers of 2 and odds (mentioned by others)
4. the "herring bone" pattern using max:
0 1 4 9 16
2 3 5 10 17
6 7 8 11 18
12 13 14 15 19
20 21 22 23 24
or
-||||
--|||
---||
----|
-----
(x,y) -> if x>y, x^2 + y, else y(y+1)+x
(the other direction is messy just like for diagonalization).
There's the Hilbert-Gray code-Peano curve finite bijection which I
think can be extended to cover the whole (natural-number) quarter-plane
These can all be modified/extended to other bijections N <-> N^2, or
even to N <-> N^k.
For example, in 1. the two coords are of equal importance; one could
weight them differently (giving diagonals of different slopes). Or
yours you can interleave three or more sequences. As to generalizing
powers of 2/odds, off the top of my head, I can't seem to get a
factorization to biject N with anything other than N^N.
Any others?
Mitch
A N Niel
> - interleaving base q digits (extends to a bijection R <-> R^2)
that "extension" has problems because of reals with two expansions...
Mitch
A N Niel wrote:
> >
> > - interleaving base q digits (extends to a bijection R <-> R^2)
>
> that "extension" has problems because of reals with two expansions...
are those problems still there if you do the usual
"don't-allow-infinite tail of 0's" ?
Mitch
A N Niel
Mitch <mah...@gmail.com> wrote:
Yes, it still does not work.
What pair corresponds to: 0.101010101010101010... ?
Remember, you do not allow infinite tail of 0s.