Eyal's Protein Conjecture

This is the how Eyal originally described the problem:
Given a -cube of points in a space of dimensions, i.e. all the points in the square of , , , etcetera, is it possible to put every point from this region somewhere in the infinite -dimensional plane, so no two points will be put in the same place (a.k.a one-to-one correspondence), and that in the new arrangement, every point will be "isolated", i.e. there will exist a neighborhood of that point which contains no other points?
This is the more impressive wording I thought of:
Given a space of -dimensionality, is there a way to take all the points from that space and map them back into that space, so no two points will be put in the same place (a.k.a one-to-one correspondence), so that in the new arrangement, every point will be "isolated", i.e. there will exist a neighborhood of that point which contains no other points?
We will refer to this theorem as , where is a free variable that represents the dimensionality of the space.

Now I will try to isolate the peculiarity of this problem into a more analyzable context. Actually, the first step would be to show that this theorem is equivalent to Eyal's original description of the problem--which will be referred to as . This is quite easy: Since the cardinality of the "unit square" in is , and the cardinality of the entire is also , set theory guarantees there exists a one-to-one mapping between them. So if is true, we can slightly alter the mapping that satisfies it to satisfy , and vice-versa. Therefore, for any , .

The next step would be to prove that for any , . One direction is trivial, the other more subtle.

First the easy direction: . Whatever mapping was good enough to satisfy in , we can use it for on one axis of and put zeroes into all the other coordinates. More formally:
We take the set of points on which satisfies . We build a mapping from it to the set on , defined as the set of all members of for which the first coordinate is a member of and all the other coordinates are zero--a trivial one-to-one mapping. If all the points in were isolated, all the points in are isolated, and satisfies . The full mapping is : From to (bound to exist since they are both ),  from to isolated points in (we assume its existence by assuming ), and from isolated points in to isolated points in (which is the mapping we described in this paragraph).
QED: .

Now the hard part: . One might think that finding a mapping for , where , will be ��easier�� since there are more dimensions to play with and there’s more room for all the points and their luxurious, empty neighborhoods. However we shall prove that given a mapping that satisfies , we can construct a mapping that satisfies , e.g. relocates these points to the straight Real Avenue while still making sure everyone’s got elbow room.
A digression. We must understand, that in our efforts to map a set of points to another set of points with certain restrictions, it doesn’t really matter from which set we are trying to map--as long as that set’s power is . This is because the only restriction we have to obey, namely the empty neighborhoods around each point, is concerned only with the range of the mapping. Since there are one-to-one mappings between any two sets with cardinality, we do not have to bother to show the whole mapping from the original domain, , to the final set of isolated points, we just need to show that they are of the same cardinality, , and set theory guarantees us there’s a one-to-one mapping between them.
Back to proving . For this proof we shall use a function based on the Alternating Digits function. If you are not familiar with it, these are the essentials: we’ll call our function , its domain is , and it is onto its range of . It is continuous. It is not one-to-one, but, and this is important, each point in its range has not more than points from the domain leading to it.
We are assuming . There is a one-to-one mapping from all the points in to a subset of such that all the points are isolated. Or, as we noted in our digression, we can say that we have a set of isolated points in which is of cardinality. In the course of this proof we will build an set on , and prove that is satisfies by contradiction: we will prove that if it does not satisfy our original set did not satisfy .
Enough with the foreplay and let’s prove it. We define as all the members of which satisfy . Of course is of cardinality, as we have a function from it onto another set (namely, onto ). All the points in are isolated--to prove it we will assume the opposite. Assume there’s a point in which is not isolated, i.e. it does not have a neighborhood in which there are no other points from , i.e. for every neighborhood of there are some points from in it. Now the trick is, we can build a sequence, made entirely from members of , which converges to . We will call this sequence . To recap: We have a sequence of numbers from which converges to our point which also belongs to , and most importantly, all the members of are different from , or in other words does not appear in the sequence.
Now to show that our original set does not satisfy the empty neighborhood condition. Observe the point . It is a member of . And now we will show it is not isolated. We will build another sequence: . Since all members of are members of , all members of are members of . And since the function is continuous, the limit of is . Only one thing left to settle in order to show the contradiction and complete the proof. We want to show that for every neighborhood of , there is a member of different from inside it. The sequence almost gives us that, but not quite! While it was true for that all its members were different from its limit , it is not necessarily true that all the members of are different from its limit, ! Why is that? That is because the function f is not one-to-one. Even though there is no member of which is equal to , there might be members of which lead to the same point in as , i.e. there might be a point for which , or maybe infinitely many points like that.
Fortunately, there’s a workaround. Remember in our introduction to , we noted that for every point in its range, there are a finite amount of points in its domain which lead to it? So it follows, that we can take our series , and form a sub-sequence by omitting those values which are equal to ; and since we now know there is merely a finite number of them, this is possible.
So there we have it: A sequence of numbers from converging to a member but all different from it. Thus will never be alone and isolated, as it will always have the members of getting infinitesimally close to it. So the points in are not isolated, i.e. if does not satisfy does not satisfy , from which follows that if satisfies satisfies , from which finally follows , QED.

Now we have proven that for all d, , and we are allowed the luxury of referring to as simply .
Let’s review where we are standing in our efforts to isolate the problem. We already ��compressed�� the problem by taking it from the -dimensional space into the one-dimensional . Now we shall isolate the problem further by taking it from the realm of the infinite to the (hopefully) easier to analyze open segment . Introducing :
There exists a set of real numbers in the open segment , such that the cardinality of is and all the points in are isolated.
Our next mission is to prove that . Again, one easy direction and one harder direction.

The easy direction, . We are assuming the existence of the set of cardinality, and that all the points in are isolated. It doesn’t even matter that all the points in are between 0 and 1, since the proof comes without it: Since the cardinality of is , we can map into it, and this mapping will satisfy since all the points are isolated. We have proved .

Now we will prove . Assume there’s a one-to-one mapping from to a subset of such that all the points in are isolated. Now we will create , a set which will satisfy . We define as all the numbers expressible as , where is a member of . This is a kind of a compression function, and we shall refer to it as in this proof. The domain of is , and its range is . It is a one-to-one, continuous, strictly increasing function.
Now to prove that satisfies . We know that every point in is isolated. Let’s take a point in , call it . We know is isolated, so we can say there exists a positive real number such that in the open segment , the only member of is . What this gives us, is that the point is isolated: There are no other members of in the open segment . Since f is a strictly increasing function, we know that is smaller than and that is bigger than , and it is impossible for any member of to ��squeeze�� between them, because that would mean there would be a corresponding member of between and , which would violate our original assumption. Therefore is isolated.
Since we did not have any requirements from , we can apply this argument to all the points in , and deduce that all points in are isolated. Therefore,

Now we shall prove that is false. We will need to define several objects for this proof. Firstly, a function we will call , from to . Intuitively, returns the radius of "empty" space around each point. Formally:
The well-definedness of is not totally trivial. One might suspect that the set in question does not have a maximum. Let me reassure you that it does have a maximum for every , but even if it didn't, the proof would work the same if returned the supremum of that set (which can be shown to be equal to the maximum.)

Now we will define a sequence of sets. For this we will utilize a sequence, , of real numbers in , such that is decreasing and its limit is zero. Any sequence of this kind will do, for example, 1/2, 1/4, 1/8, 1/16... will work. The sequence of sets is defined as thus:
Do you understand what we’re getting at? Let’s say we use the sequence of as . will contain all the points in that have a clear neighborhood of at least 0.5 radius around them. will contain all the points in with at least 0.25 clear around them. will contain all the points with 0.125 clear around them. Now there are some vital things we have to prove about .
First off: For every , is finite. This is intuitively correct: Take all the points which have this much space around them in the bounded segment of , you just can’t have too many otherwise they won’t fit in. can not have more than members. We shall give a formal proof:

Firstly for the sake of convenience we shall define . Assume that has at least members. Therefore we can find two members, we will notate the smaller one and the bigger one , that have at least members in the open segment between them. We will notate these members as according to size, e.g. is the smallest member, is next etcetera. Now observe:



Because b is an increasing finite sequence, we can add absolute values:



Now, because we know that all these are members of , we know that the distance between each pair of them is at least .



Therefore:



But the distance between two points on cannot be 1! Contradiction, is finite for every and bounded by , QED.

The second important thing about , is that every member of belongs to for some . This is simple to understand: any member of is isolated, so it has a clear neighborhood. Since converges to 0, it eventually becomes smaller than that neighborhood, for some . And for that , belongs to . It will also belong to all the following sets for all the following ’s, but that’s not important. We settled it: every member of belongs to for some .
Now we have these two facts: That every is finite, and every member of belongs to for some . We can now deliver the final blow of countability. We will catalog all members of with a vector of two natural numbers. For every member of , we can say that it appears in for some ; So for the first it appears in, that smallest will be the first natural number in our vector. For the second natural number, we will order all the members in the aforementioned according to their size, increasing or decreasing order, it doesn’t matter. There are only finitely many members, so we can catalog all the members according to size and give each a natural number according to which ��place�� it is on the ladder. That number will be the second natural number in our vector. If two members of both appeared for the first time on the same , they will differ by that number in the vector.
So since every member of has a vector of two naturals associated with it, and no two members can have the same vector as we have shown, the cardinality of cannot exceed the cardinality of the vector space . However, since can be mapped to , it is countable, therefore cannot be uncountable, and cannot be . QED:
There does not exist a set of real numbers in , such that is and all the points in are isolated;

There does not exist a set of real numbers, such that is and all the points in are isolated;

There does not exist a set of points in -dimensional space, such that is and all the points in are isolated;

We have proved that Eyal's Protein Conejcture is false: It is impossible to rearrange all the points in a -dimensional space and map them back into that space, without putting two points in the same place, and that in the new arrangement every point will be isolated.
Back to Ram Rachum's Site

All content in this website is copyright © 1986-2011 Ram Rachum.