Use Binary expansion to show (0,1) ≈ all infinite subsequences of {X_n}

[Wildcat]

Homework Statement

{xn} is an infinite sequence and xi ≠ xj if i ≠j. Let A and B denote all finite subsequences of {xn} and all infinite subsequences of {xn}, respectively.

Show that B ≈ (0,1).

Homework Equations

The Attempt at a Solution

Using binary expansion, given a from (0,1) we have a=0.a1a2a3... where ai is either 0 or 1. You can map a to a subsequence which consists of those xi whose corresponding ai=1 where do I go from here?

 

[Stephen Tashi]

Using binary expansion, given a from (0,1) we have a=0.a1a2a3... where ai is either 0 or 1. You can map a to a subsequence which consists of those xi whose corresponding ai=1

That doesn't handle the case where we have a number like 0.10000... since it would map to a finite subsequence instead of an infinite subsequence. You need to make an infinite string of zeroes do something also.

In practical digital communications transmitting a along run of 0's or 1's is prone to errors when hardware uses the change from 0's to 1's to update the syncrhonization of the transmitter and receiver clocks. So there are schemes to avoid this. (See http://en.wikipedia.org/wiki/Run_length_limited) They might provide some ideas.

 

[Wildcat]

That doesn't handle the case where we have a number like 0.10000... since it would map to a finite subsequence instead of an infinite subsequence. You need to make an infinite string of zeroes do something also.

In practical digital communications transmitting a along run of 0's or 1's is prone to errors when hardware uses the change from 0's to 1's to update the syncrhonization of the transmitter and receiver clocks. So there are schemes to avoid this. (See http://en.wikipedia.org/wiki/Run_length_limited) They might provide some ideas.

In the original statement B is all infinite subsequences, so would that automatically exclude anything like the case you mentioned? wouldn't that case be in A??


I think I need to find a bijection between (0,1) and B. For example, 1/3 is.01010101... so we will map it to the subsequence x2,x4,x6,... does that make sense??

 

[Dick]

In the original statement B is all infinite subsequences, so would that automatically exclude anything like the case you mentioned? wouldn't that case be in A??


I think I need to find a bijection between (0,1) and B. For example, 1/3 is.01010101... so we will map it to the subsequence x2,x4,x6,... does that make sense??

Makes perfect sense. The problem Stephen Tashi is referring to is 0.1000000... and 0.011111... correspond to the same number in (0,1). But they correspond to two different sets. Just like 0.1 and 0.09999999... are the same number in decimal. They are both 1/10. In binary, they are two different ways of representing 1/2. So it's not quite a bijection. But it's a purely technical problem. The number of exceptions to the bijection is countable.

 

[Wildcat]

Makes perfect sense. The problem Stephen Tashi is referring to is 0.1000000... and 0.011111... correspond to the same number in (0,1). But they correspond to two different sets. Just like 0.1 and 0.09999999... are the same number in decimal. They are both 1/10. In binary, they are two different ways of representing 1/2. So it's not quite a bijection. But it's a purely technical problem. The number of exceptions to the bijection is countable.

Thank you, that is very helpful!

 

[Stephen Tashi]

In the original statement B is all infinite subsequences, so would that automatically exclude anything like the case you mentioned? wouldn't that case be in A??

Yes, 0.10000... would map to an element of A, but I thought you were trying to map into B. You didn't explain your intent. The ambiguity between 0.1000... and 0.0999... may come to your rescue if you specify that all the numbers in [0,1] are to be written as non-terminating strings of digits.

I think I need to find a bijection between (0,1) and B. For example, 1/3 is.01010101... so we will map it to the subsequence x2,x4,x6,... does that make sense??

It's nice to solve problems like this with bijections, but its often easier to show each set maps 1-1 into a subset of the other. Is there a theorem like that your materials that would show that using two maps that way is sufficient for a proof?

I've just noticed that you started other threads about this problem. (Naughty!) In another thread you stated the hints you were given and that part of the problem is to prove A is countable. Maybe the method the instructor has in mind is to show that the union of A and B has the same cardinality of [0,1] and then argue that B alone is also uncountable.