Proving The Hamming Metric: Open Subsets and Basis of X

[Metric_Space]

Oh...does |X_k-a_k|=1 for k=1..infinity?

 

[micromass]

Yes! Very good!

So, if |x_k-a_k|=1, then what will x_k be? (Remember that x_k and a_k can only take on 0 and 1 here).

 

[Metric_Space]

x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?

 

[micromass]

x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?

Very nice! So, basically, a_k has the opposite value of x_k...
Remark that this correspons nicely with the previous thingies where a was (0,0,0,...), then x was (1,1,1,...).

So, the ball around a with radius 1 is just everything except the "opposite of a")!

Now, we're going to make it a little harder. We're going to figure out what the ball around (0,0,0,...) is with radius 1/2. So, for which vectors does

\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}<\frac{1}{2}

As above, you may remark that it suffices to calculate when equality holds, thus

\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=\frac{1}{2}

Since if x has a distance of 1/2 of 0, then all vectors with less 1's than x, have distance <1/2. And this is exactly what we wanted...

 

[Metric_Space]

Would (x_1,x_2,x_3...) = (0,1,1,...)?

 

[micromass]

Would (x_1,x_2,x_3...) = (0,1,1,...)?

Yes that's good, but there is one more possibility!

 

[Metric_Space]

oh right...or (1,0,0,0..)

 

[micromass]

Yes, very good! So elements in the ball around 0 with radius 1/2 consist of those elements with more zeroes than either (1,0,0,...) or (0,1,1,...).

Now, can you describe the ball around an arbitrary a with radius 1/2?

 

[Metric_Space]

balls of radius (1/2)^k have elements

with 1's starting in the kth position and 0's afterwards OR 1's in the (K+1)st position...right?

 

[micromass]

balls of radius (1/2)^k have elements

with 1's starting in the kth position and 0's afterwards OR 1's in the (K+1)st position...right?

No, but you have the right idea. What you describe are the sequences such that

\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=\frac{1}{2^n}

To describe the balls, you'll need < instead of =. So the balls would be the elements which has less 1's than the elements that you describe.

Also, that only describes the balls around 0. It would be fun if you would find the balls around arbitrary elements...

 

[Metric_Space]

around an arbitrary element...wouldn't it be similar to before.

ie. (sum,k=1..infinity, (x_k-a_k)/2^k) < (1/2)^n

either x_k is with 1's starting in the kth position and 0's afterwards
and a_k is ..not sureOR 1's in the (K+1)st position

and a_k is not sure

 

[micromass]

Well, the balls around a with radius 1/2 are either:

1) elements which agree with a in it's first coordinate
2) elements which agree with a except possibly in it's first coordinate.

Can you see why?
Can you extend this to balls with radius (1/2)^k??

 

[Metric_Space]

no...I don't follow

 

[micromass]

Can you see why it is true for a=0?

 

[Metric_Space]

I think so?

 

[micromass]

OK, npw apply the same reasoning to arbitrary a instead of 0...

 

[Metric_Space]

...I think I need a hint

 

[micromass]

Well, when does

\sum_{k=1}^{+\infty}{\frac{|x_k-a_k|}{2^k}}=\frac{1}{2}

??

 

[Metric_Space]

x_k=(1,0,0,0,0...) and a_k=(0,0,0,...)

or

x_k=(0,1,0,0...) and a_k=(0,0,0,...)

or

a_k=(1,0,0,0,0...) and x_k=(0,0,0,...)

a_k=(0,1,0,0...) and x_k=(0,0,0,...)

 

[micromass]

No, can you show my how you got that?

If

\sum_{k=1}^{+\infty}{\frac{|x_k-a_k|}{2^k}}=\frac{1}{2},

then what must hold for |x_k-a_k|.

 

[Metric_Space]

I have a new question.

How would I show that the metric space defined by the Hamming metric is complete?