Eyal's Protein Conjecture
This is the how Eyal originally described the problem:Given aThis is the more impressive wording I thought of:-cube of points in a space of
,
,
, etcetera, is it possible to put every point from this region somewhere in the infinite
Given a space ofWe 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.
, 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 setOur 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,
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.
, 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 setYou deserve a beer.
There does not exist a set
There does not exist a set
We have proved that Eyal's Protein Conejcture is false: It is impossible to rearrange all the points in a