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.

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,

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.

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.

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