This conversation appears very messy!

It seems to me that the issue here is not about bijections between countably infinite sets, but rather about order types for countably infinite sets. (Recall that two ordered sets are of the same ``order type'' if there is a bijection between them which is monotone increasing and whose inverse is also monotone increasing.)

E.g., (N,

Dear @Juan, It is clear that there is no bijection the way you are define, but there are other types of bijections between infinite sets of the same cardinality.

Dear Abedallah,

Of course there are other bijections....I am not so dummy. For instance the identity map is a bijection that exists for all possible sets. What I mean is that you can find some proofs in mathematical literature based upon the existence of some bijection, which is not defined in the proof, however its existence is assumed disregarding the order under which its domain and codomain are given. I think that this wrong procedure occurs by inertia, that is, generalizing a usual situation in the scope of finite sets. Indeed, between finite sets of the same cardinality, bijections can be arbitrary.

Zermelo's Well Ordering Theorem might be, to some extent, along the lines of what you seek.

Daniel,

I cannot see any relation between my post and Well Ordering Theorem. What I have stated is that bijections between infinite sets cannot be arbitrary. By arbitrary I mean that the corresponding domain and codomain can be given in any order as can happen with finite sets. It does not matter whether the order is Well or not.

As far as I know, Well Ordering is related with the existence of any map between a set E and the corresponding power set P(E), that is to say, the Axiom of Choice.

Clearly bijections cannot be arbitrary. The WOT implies that bijections can have surprising features, e.g. taking R to a well ordered set.

That said, I do not know what you have in mind in the remark " there are a lot of proofs in mathematical literature disregarding this impossibility [of arbitrary bijections]".

The fact that there is no bijection on the natural numbers N reversing the natural order is a consequence of the fact that N and N* (N with the reverse linear order) are not isomorphic linear orderings. The more structure-preservation you impose on your bijections, the less "arbitrary" they can be.

Dear Paul,

I agree with you. There is no monotone bijection. Nevertheless, this impossibility leads to another question. Is the order of N an intrinsic property which cannot be forgotten? In other words, it is not possible to handle the set of all natural numbers in a structure-free way; otherwise, to define a bijection it does not matter the order under which its members are arranged.

Recall that working with finite sets any order can be disregarded. Likewise, in general, forgetful functors are defined for any construct, that is, category of structured sets, disregarding every structure relation. I think that the accuracy in mathematical proofs should be stated taking into account this topic.

Hi Juan-Esteban,

Intrinsic to the definition of "finite set" is the existence of a bijection with an initial segment of N; likewise the definition of "countably infinite set" presupposes a bijection with N. So I don't understand your statement regarding being able to "disregard" order on a finite set, but not on a countable one. In some arguments involving N--say using induction--the natural order plays a key role. In others--say using free ultrafilters to construct richer structures--order is not important.

Hi Paul,

Indeed, "countable infinite set" means that there is "at least" one bijection onto N, but "need not be an arbitrary bijection", that is, being arranged in any order. You can find a bijection from N onto N easily, for instance the identity. Nevertheless, try defining a bijection from N onto N such that the domain is given in the natural order and the codomain in the reverse one. What I have stated is that there is no such a bijection. To see this fact, consider that the image f(1) of the first member of the domain should be the last member of N, (which is the first one of the codomain); however there is no last positive integer.

This conversation appears very messy!

It seems to me that the issue here is not about bijections between countably infinite sets, but rather about order types for countably infinite sets. (Recall that two ordered sets are of the same ``order type'' if there is a bijection between them which is monotone increasing and whose inverse is also monotone increasing.)

E.g., (N,

Well put, Collin.

Dear Collin.

I agree with you. You have grabbed the core of the question.

Best regards.

!!!

Happy day. Thanks.!

The followers of this thread may find the following book interesting:

A.D. Hwang, Calculus for Mathematicians, Computer Scientists, and Physicists:

http://mathcs.holycross.edu/~ahwang/print/calc.pdf

See, for example, Section 3.3, page 125 for examples of bijections between infinite sets.

Dear James,

I cannot understand which is the relation between the examples in http://mathcs.holycross.edu/~ahwang/print/calc.pdf and my question. The examples in this book are bijections and their inverses. In addition they are pointwise defined. Indeed, by definition, there is an inverse for every bijection. The inverse we are dealing with is the order of the bijection codomain. It is not the map inverse.

Pointwise map definitions are easy to build, but the cases I have exposed are positional definitions instead, therefore order dependent.

Some examples will help us. Consider this definition x -> 2x. This is a pointwise definition for a bijective map, the inverse of which is x -> 1/2x. Now, let us see a positional definition. Consider a two column hash-table defining a map from N onto N. In the first column is written the sequence of the positive integers in their natural order ≤. The second column consists of the sequence of positive integers arranged in the reverse order ≥. Now, try to find out which is the first element in the second column, that is to say, the image of 1. Of course, since in the second column the integers are arranged in the inverse order, the first element must be the last positive integer, but there is no last positive integer.

We can find some proofs either of bijection existence or of non-existence in mathematical literature, in which the codomain of a map between infinite sets is rearranged disregarding this topic. It is a lack of accuracy.

Please, excuse me: I suppose that my English is very poor, because your message has been voted up twice, and this is only possible by misunderstanding the question I have exposed. If so, I apologize and I will try to be more explicit, in order to avoid misinterpretations.

The first example in http://mathcs.holycross.edu/~ahwang/print/calc.pdf is the identity map. In the second message of mine in this thread I have mentioned this map. Nevertheless, my question has been interpreted as if I were negating the existence of any bijection. Even a baby knows the existence of the identity map when he looks at a mirror.

If somebody wants to negate my statement, he must show the image F(1) of a bijection F from N onto N, positionally defined, such that the domain is the infinite sequence 1,2,3....while the codomain is the same sequence arranged in the inverse order. Any other answer only means that my question has been misunderstood.

It is worth mentioning, that both orders for N, namely, ≤ and ≥ are linear, that is, both have identical structure.

Finally, notice that for finite sequences of positive integers 1,2,3...n this kind of bijection is always possible and trivial. It is sufficient to write the corresponding hash-table in both orders.

Dear Juan-Esteban,

Many thanks for your helpful observations and for clarifying your view of bijections. I find your question very interesting, since bijections between infinite sets are both important and useful in a number of ways.

Dear James,

I appreciate your kind words. Thank you.

The problem here is of course about order types, because you want to reverse an order. The order type of N cannot be reversed, because there is no "last element" to be the image of the first element, which is 0. However, you can map N to -N, by the mapping n --> -n. This mapping is order reversing, and the first element of the first structure, which is 0, goes to the last element of the second structure, which is 0. The same mapping reverses the order over Z. But one can do even more, in analogy with {1,2,3,4}. Consider the set N U -N, ordered such that every element in the first half is smaller than every element in the second half. Now there is a last element, and it is something called "-0", at the right end of the second half. A new mapping n --> -n, where this time 0 --> "-0", the new element, is now order reversing!

Mihal,

Of course, the order of the integer set Z is reversible. In addition, the map n -> (-n) is "pointwise" defined, therefore order-independent. By contrast, positional map definitions based on a hash table are order-dependent.

Notice, that the definition n -> (-n) uses the additive group structure of Z, but the order is neglected. However, defining a map by means of a hash-table, the group structure is disregarded, but the definition depends on the order under which the codomain is arranged.

This is why, dealing with infinite sets, some structure must be preserved, depending of the definition method. Accordingly, unlike the situation with finite sets, dealing wit infinite ones, map definitions cannot be arbitrary.

Dear Juan-Esteban,

for N and Z, the order and the algebraic structures are deeply connected, because those structures are free (free semigroup with one generator, free group with one generator). Surprises does not stop here: on the additive group G generated by 1 and sqrt(2) [these are numbers a + b sqrt(2), with a and b in Z] one can define a dense order. It is the order inherited from the real numbers! And now comes the big surprise: there are infinitely many order preserving bijections between this group G and the additive group Q of rational numbers, but: None of them can be given explicitely and none of them is a Group morphism!!! They are only order preserving bijections, whose inverses are also order preserving. As to say, they are only isomorphisms of order types. Moreover, any two countable discrete orderings without end-points are isomorphic (like Q and Q \ {0}) but almost none such isomorphism can be given explicitly!

Dear Michael,

You're right. Everything in your post is accurately right. But do not forget the title of this thread. The title is whether or not bijections between infinite sets can be arbitrary.

Any answer must be connected with the definition I have stated for the expression "arbitrary map" that is the following one.

A bijection f:X->Y is arbitrary provided that its codomain can be arranged in any linear order.

Notice that handling finite sets every bijection is arbitrary. For instance, consider the identity id:{1,2,3} -> {1,2,3}. You can reverse its codomain obtaining f*:{1,2,3}->{3,2,1} and the result is again a bijection. In fact, if the codomain is of cardinality n you can arrange it in n! different linear orders. By contrast, with infinite sets bijections cannot be arbitrary. As you have pointed out before, the order of the codomain of the identity id:N -> N cannot be reversed, because of (N,≤) has no last element, while (N,≥) has no first one. This is all.

Excuse me Juan-Esteban, but is still unclear what do you exactly mean. Bijections are functions. Functions are sets of pairs (x, y) = (x, f(x)); so a Special case of relation. Relations between sets A and B are subsets of A x B (of the set of all pairs). A relation is a function if and only if every x in A occurs in exactly one pair. Now, seen so, one can always permute pairs in the function as one does intend. This has no influence on the fact that the function does exist or not. Non-isomorphic order types do not accept isomorphisms between them. I think, that this is the point .

However, very nice topic to discuss. Thank you.

@  Ans Schapendonk

I guess that your work is prepairing for the secondary role as Mentaculus in Brothers' Coen movie "A serious man", see here:

http://10oclockdot.tumblr.com/post/62330414030/the-mentaculus-as-featured-in-the-coen-brothers

Unhappilly the role has been given to another masterpiece. Do not discourage. Just continue to pet the petagram (sorry, I mean pentagram... too many unknowns in the equation...) and believe me, cause I'm sagitarius.

@  Ans Schapendonk

Ans, it is very funny indeed how you write. For most poeple "calambours" are the worst sense of humor. For me they are the best. I understand that 26.09.14 something serious will happen - and I just hope that it is not too serious.

Now back to work. Münzen sind nur kleines dämliches Spielzeug, und es kann nur das Werk von Madog (my dog) sein, dass so viele Schicksale dafür zugrunde gegangen sind. Rumänen sagen, dass die Münze das Auge von Satan sei. Kann gut sein. Zugrunde gehe ich auch, wenn ich auf dem Strand liege, aber diese Typen hören nicht auf, bis sie unter die Erde landen. Landen ist auch zu viel gesagt, denn sie gehen wirklich darunter. Jetzt zu den Bildern. Wenn Religion das Opium der Völker sei, warum brennen die Leute eigentlich nur Weihrauch? Ich glaube, dass der, der Anfangsfehler ist (the original sin). Es heißt also: dir ist die Trance verboten, aber du musst dich selbst überzeugen, dass du in Trance bist und beten kannst.  das führt vielleichtt zum Doppeldenken. Habe ich mir ein gutes BILD der RELIGION gemalt? Dann nimm es nicht zu BARE MÜNZE. Nächstes Mal geht es um Ans Selbstdritt, und übernächstes Mal töten wir den Drachen.

Maybe we must find another way to communicate as this sequence of answers about bijections. We make people angry, and they are right. If you want to continue and write me a personal message through RG, we will then find the best way. M

In fact we can consider the function f : Z --> Z given by f(k) = -k. This is an order reversing bijection of Z. Restricted on N, this is a bijection between N and -N. -N is the set of natural numbers, if we count towards the left direction, instead of right direction. Here -1 is the biggest element (or 0, it depends if you consider it natural), -2 is smaller, -3 is even smaller, and so on.

Mihai,

You example is only one instance. A counterexample rejects those statements that use universal quantifier. My question is built by universal quantification implicitly, for "arbitrary" means that all choices are adequate. Since I have shown an instace in which no bijection exists, the question is closed, unless you can prove that my counterexample is wrong. However, you have shown a different case. Notice that in my example both the domain and co-domain are the same, while in your example the domain consists of positive integers while every member in the co-domain is negative. Thus, your example does not contradict mine.

Clarifying my earlier point, and relating more closely to Juan-Esteban's example:

The natural numbers as such have the property that any subset has a least element, but not a greatest element.  Juan-Esteban's point is that because of this, there can be no bijection which actually reverses the order of the naturals, and he is, of course, correct.

I think this is a messy discussion. And the reason is because the question is not clear. What does it means "arbitrary"? Please, set the question as a precise mathematical statement to avoid messy discussuions. To sum up the situation, in my opinion:

There are lots of bijections from N to N. You can start by sending 0 to any natural number f(0). Then you can send 1 to any natural number in N-{f(0)}. Then you can choose the image f(2) of 2 as any number in N-{f(0),f(1)} And so on. A counting argument shows that there are 2 to the power of Aleph_0 many possible bijections. This is the cardinality of the continuum. In other words, there are as many bijections as real numbers.  

But If you ask as extra condition "reversing the order" there is clearly no such bijection. And if you ask "preserving the order" there is only one: the identity.

Juan-Esteban claims there are lots of mathematicals proofs diregarding this impossiblity(which one? there is no bijection from N to N reversing the order?). I do not know any one. I'm interested in such examples. Can you give a precise one?

Note: by  "preserving the order" I mean:    a

Dear Rafel

I copy-paste the definition from English dictionary:

Arbitrary: Depending on will or discretion; not governed by any fixed rules.

Of course, natural languages are context dependent and my counterexample leads to interpret the term arbitrary as "in any order".

In any case I'll try to be more accurate. Consider any finite set E = {1,2,3..n} and the identity map id:E -> E. We can rearrange the codomain in any order and we obtain another bijection. There are just n! possible bijections. This procedure cannot be applied to infinite sets. My counterexample is sufficient to prove that the codomain cannot be rearranged in any order.

I can state a more sophisticated example. Consider the identity map

id:N -> N that can be denoted in the following table

1 -> 1

2 -> 2

3 -> 3

4 -> 4

......

......

The result of any transposition of two members of its image is again a bijection. For instance, substituting 1 by 2 and 2 by 1, the identity map becomes the following bijection B1:

1 -> 2

2 -> 1

3 -> 3

4 -> 4

5 -> 5

.....

.....

Now, suppose that in this bijection we transpose the first odd integer k  in the image by the first even one located in the table below k. We obtain the biyection B2:

1 -> 2

2 -> 4

3 -> 3

4 -> 1

5 -> 5

......

......

Iterating the process we obtain a bijection sequence B1, B2, B3.....Bn....such that, the n first members in the image of Bn are even integers. If we assume that the infinite process can be completed, we obtain a non-bijective map

B:N -> {2n | n in N}

each member in its image is even, and every odd interger vanished, in spite of being every Bn a bijection, for each positive integer n.

This fact shows that to prove that there is no bijection between N and other set E, the proof cannot be performed using an endless rearrangement sequence in the corresponding proving procedure. Nevertheless, this lack of accuracy can be found in mathematical literature.......