Proving The Hamming Metric: Open Subsets and Basis of X

[Metric_Space]

Homework Statement

I'm stuck on how to start this. The Hammin metric is define:
http://s1038.photobucket.com/albums/a467/kanye_brown/?action=view&current=hamming_metric.jpg

and I'm asked to:
http://i1038.photobucket.com/albums/a467/kanye_brown/analysis_1.jpg?t=1306280360

a) prove the set U(d1,...,dp) is an open subset of X.


b) Prove that U is a basis of open sets for (X, d).

c) Say whether the statement is true or false.

Consider the following statement: “For every p 2 N and every d1, . . . , dp ϵ {0, 1},
the set U(d1,...,dp) is a closed subset of X.”
Is the statement true? Justify your answer (with a proof or counterexample).

Any ideas?

Homework Equations

The Attempt at a Solution

I'm not sure where to start. I know (X,d) is a metric space but that's about it so far.

 

[micromass]

You can start by describing the balls in this space. Let's first answer an easy question:

given x=(0,0,0,...), can you find me all sequences y such d(x,y)<1/2?

 

[Metric_Space]

What I've figured out is the set is almost an open ball around the sequence d1,d2,d3...d_p of
radius (1/2)^p.

I think there may be a special case where everything is the same except for x_p

 

[micromass]

Well, maybe your open set is the union of two balls?

 

[Metric_Space]

I'm not sure I fully follow -- could you elaborate?

 

[micromass]

Well, can you first tell me what the ball around (0,0,0,...) with radius 1/2 looks like?

 

[Metric_Space]

not sure...just a point?

 

[micromass]

No, you'll need to find all $$(x_1,x_2,x_3,...)$$ such that

$$\sum_{i=1}^{+\infty}{\frac{x_i}{2^i}}<\frac{1}{2}$$

For example, (0,1,0,0,...) is such a point, (0,1,0,1,0,1,0,1,...) too...

 

[Metric_Space]

Still a bit stuck...

 

[micromass]

OK, let's investigate the situation. For which vectors (x₁,x₂,x₃,...) does

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

 

[Metric_Space]

I guess ones whose infinite sum is one, ie. Things of the form 1/2 + 1/4 + ...

Not sure how to get that back into the corresponding x_k

 

[micromass]

Well, once you figured that out, we can take the next step!

 

[Metric_Space]

Thanks -- what about b) ...

I don't really understand the concept of basis of open sets

 

[micromass]

Thanks -- what about b) ...

I don't really understand the concept of basis of open sets

To solve (b), you will also need to know what the open balls look like. So you'll need to figure that out first.

A basis is just a collection of open sets, such that every open set can be shrunk to a basis open set. More formally: for every x and for every set G around x, we can find a basis element B such that $x\in B\subeteq G$.

The trick is that we don't need to show this for open sets in general (this would be too hard), but it suffices to look at balls. But of course, you'll need to know the balls for that...

 

[Metric_Space]

...care to give me a hint on what the balls look like?

I must admit, I find the notation confusing

 

[micromass]

Well, I want to figure out together what the balls look like. But for that, you'll first need to answer my post 10, since this is the first to find what the balls look like...

 

[Metric_Space]

Is it points with the only the even entries allowed to equal to 1 and the odd entries equal to 0?

so the 2nd, 4th, 6th, etc could be 1 or 0
but 1st, 3rd, 5th, etc can only be 0?

 

[micromass]

No, because (0,1,0,1,0,1,0,1,...) would correspond to

$$\sum_{k=1}^{+\infty}{\frac{1}{2^{2k}}=\sum_{k=1}^{+\infty}{\frac{1}{4^k}}=\frac{1}{3}$$

and this is not 1.

 

[Metric_Space]

Hmm...I'm stuck

 

[Metric_Space]

any suggestions on materials I can read? I'm not sure I can visualize this

 

[micromass]

I'm not sure you can visualize this, though. But let me give you just another step on how to proceed. Can you give me one sequence such that

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

Just one will do!

Hint: what is

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

 

[Metric_Space]

It's just 1, isn't it?

 

[micromass]

Yes! So, can you give me sequence $(x_n)_n$ such that

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

 

[Metric_Space]

the sequence of 1's?

 

[micromass]

the sequence of 1's?

Yes! Now, can you show that there is no other sequence such that

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

 

[Metric_Space]

maybe ...by contradiction?

 

[micromass]

Could work... Try it!

 

[Metric_Space]

...but how does that help?

 

[micromass]

Well, if a sequence is not (1,1,1,1,1,...), then there must be a zero somewhere. Thus...

 

[Metric_Space]

at the jth position, say?

 

[micromass]

at the jth position, say?

For example, yes.

 

[Metric_Space]

I'm thinking it can be written as a combination of other elements in U?

 

[micromass]

I don't see how that would help. You need to show that if $(x_1,x_2,x_3,...)$ contains a zero, then

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

This is really not difficult...

Let's say I have positve real numbers x,y,z>0 such that x+y+z=1, can I infer that x+y<1?

 

[Metric_Space]

yes, that makes sense

 

[Metric_Space]

yes, so one of x_k is 0 then?