Hi, I'm having a bit of difficulty with this question:

Can we define a sub-set X of [0,1] such that for any 0 < a < b < 1 there are

1) uncountably many members y of X satisfying a < y < b
2) uncountably many numbers z satisfying a < z < b which AREN'T a member of X.

My guess is that the answer is no. Or certainly it won't be possible to describe or define the set in a finite (or even countable) amount of words.

Any help would be gratefully appreciated,

Michael

How about this set:

X is the set of real numbers in [0,1] which have no odd digits in their decimal expansion after the Nth place for some integer N.

This set is uncountable, and so is the complement of the set. It is uncountable because the set of all decimal expansions with only even numbers is uncountable, and this is contained in the set. The complement is uncountable because the set of decimal expansions with only odd digits is uncountable and contained in the set. Also, if 0 < a < b < 1. Choose an integer N such that 10^-N < b-a. Divide [0,1] into subintervals of width 10^-N , one of these subintervals will be contained in (a,b). If the interval contained in (a,b) is I=[A x 10^-N ,(A+1) x 10^-N ) where A an integer. The first N places of the decimal representation of any number in I is the same, and you can continue the decimal expansion after that in any way you please, so both I intersect X and (I complement) intersect X are uncountable. So clearly (a,b) intersect X and ([0,a) union (b,1]) intersect X are uncountable.

SO this set has the property you are looking for. Moreover it is easily defined, and you don't need the Axiom of Choice to define it which is nice given the slightly uncertain nature of that axiom.

Hi Dan! Thanks for your reply.

What I am saying is that once we have defined the set, my properties must hold for ALL a and b s.t. 0 < a < b < 1. (We can't define the set after we know the values of a and b). So we are not allowed to say choose any integer N s.t. 10^-N < b-a because b - a can be arbitrarily small.

(By the way, perhaps a clearer way of phrasing the problem is: we want to split the set [0,1] into two sub-sets each with uncountably many values in every possible sub-interval of [0,1])

Thanks,

Michael

I thought this when I first read Dan's reply, but then realised that what he meant was the set X of all numbers with only finitely many odd digits.

Then given any a and b you can find an N, and then uncountably many numbers in the subset of X that has no odd digits after the Nth place.

Similarly there are uncountably many numbers in the complement, because there are uncountably many which only have odd digits after the Nth place.

Note that we have not used N to define the set, merely to help us find some numbers that are in it.

Oh, sorry. I was confused by the N being used twice. Yes, that ought to work very nicely, thanks. I had realised that the set required some property that you couldn't deduce from the first n decimal places (for any n) but I gave up there! Incidentally can we define the set if we further stipulate that the Lebesgue measure of the set in the region [a,b] is equal to (b-a)/2? (I don't know too much about Lebesgue measure so this may be a silly question.)

Many thanks for your replies,

Michael

Sorry about the confusion there, should have used M and N or something like that.

As regards Lebesgue measurability, I think that you won't be able to find any set with the property you mentioned above. The "outer measure" of a set is defined as the infimum of the sum of the lengths of a countable number of intervals whose union covers the set. The "inner measure" is defined as the outer measure of the whole set ([0,1]) minus the outer measure of the complement of your set. A set X is "measurable" if the outer and inner measures agree. However, because there are an uncountable number of points of both X and X^c any countable set of intervals covering either X or X^c must contain the whole interval [0,1] so the sum of the lengths of these intervals must be > = 1. So the outer measure of X and X^c must be > =1 (in fact, equal to 1). So the inner measure of X is the outer measure of [0,1] (=1) minus the outer measure of X^c (=1), so the inner measure of X is 0. So X is not measurable.

This is not a rigorous argument, but I think it is right, if no-one else corrects me here, I'll check with my functional analysis supervisor at my next supervision and get back to you.

Thanks a lot - this has been very helpful.

I can understand why you're saying that a measurable set that satisfies the properties cannot be found. But is it okay to define a set by random methods - can we define a set randomly such that that each number in [0,1] has a 1/2 chance of being in the set? It would take an uncountable number of seconds to decide what the set is, but if it were possible somehow then it should really satisfy the properties (though I'm not sure if Lebesgue measure goes this far) I'm after. That's why I'm wondering whether these sets do exist and maybe it is just that we cannot define them precisely in a countable number of words.

Many thanks,

Michael

The problem with a definition like "each number has a 0.5 chance of being in the set" is that it doesn't define a set, both the empty set and the whole of [0,1] could be defined by this, although both would have a 0 probability of happening. Measure theory (at least, the amount I know of it) won't be able to give you a set that you want as any set which has the property you are looking for would not be measurable, however there may be another branch of maths that might help.

Thanks. Basically it was the kind of ideas in your latest message that prompted me to ask the question initially. (It is possible to have an alternating set with any positive difference between terms but it is hard to generalise this to a continuously alternating set). What I didn't realise was that to make the question really interesting it was not enough to demand that both sets were uncountable in each sub-interval.

On the subject of choosing the sets at random, it is certainly true that the empty set and [0,1] are two possibilities. However the probability that the resulting set satisfies the criteria in the first message should be one. Intuitively there should also be probability = 1 that it satisfies the measure criteria, but unfortnately you have already shown that the sets were unmeasurable. (I didn't know that the definition of a measurable set was one in which the outer measure of the set = 1 - outer measure of the complement of the set - I thought that all sets were Lebesgue measurable).

Thanks,

Michael

Yup, it's in an interesting problem, it seems somehow wrong that there isn't a branch of mathematics that lets you have a continuously alternating set. It's possible that this is in some sense a property of the reals. However, bear in mind that measure theory is relatively new (compared to most of the math's one learns which is usually hundreds of years old) so it possible that it might be superseded. Certainly, knowing mathematicians, it's hard to believe people aren't scribbling away trying to find a generalised measure theory in which all sets are measurable. But we'll have to wait, perhaps you could do a doctoral thesis on it later in life? I'll ask a real expert here about some of these questions and get back to you in a week or so.

Sorry, I didn't read the above. How about this subset of [0,1]?

{x is a real number such that (a+b)/2 < x < 1}

There are infinitely many different collections of subsets of [0,1] that we can call measurable. (Such a collection is called a sigma-algebra and has to satisfy certain properties such as: if A and B are measurable then A intersect B is measurable.) For each of these sigma-algabras, there are infinitely many ways of defining a measure (i.e. a "size") on the measurable sets.

The smallest sigma-algebra containing all of the intervals [a,b] is called the Borel sigma-algebra.
There is only one measure on this such that the measure of [a,b] is b-a. There is no measure with this property on sigma-algebras bigger than the Borel one. (Well, I know that if you make the sigma-algebra big enough this is true, but I'm not absolutely sure that it's true for all sigma-algebras bigger than the Borel one.)

If you take all subsets of [0,1] to be measurable then there are no "nice" measures at all. This isn't entirely straightforward to prove, so I won't try here!

Jonathan

I'll try and find out more soon, it's quite interesting stuff this.

Hi, thank you for asking about this problem.

What about this variant on the problem which avoids the use of Lebesgue measures (or any others, which Jonathan has shown don't always work) but I think still retains the point.

We'll have the function f(x) = 1 when x is in the set and f(x) = 0 when x is not in the set.

Now suppose that for all integers m, n and k such that 0 < = n and 0 < = m < = 2ⁿ -1, 0 < k < 1 (k =/= 0.5), then:

f(2^-n (m+k)) + f(2^-n (m-k+1) = 1

In other words when n = 0 we find that f(0.001) = 1 - f(0.999), f(0.002) = 1 - f(0.998) etc In other words if you reflect the set you get its complement (except for at 1/2). Then applying n = 1 we see that the set must also reflect to its complement in [0,0.5] and [0.5,1]. Then n = 2, we find the set must reflect to get its complement in each of [0,0.25] [0.25,0.5] [0.5,0.75] and [0.75,1]. And it must also reflect to its complement whenever it is split up into 2ⁿ parts, within each section.

Would the set still be possible?

Many thanks,

Michael

A quick comment (I'm just about to go out, I'll write more later). If there is such a set, then there are at least a countable number of such sets. The reason is, your definition doesn't say anything about what happens to any point of the form 2^-n m, so it can either be in or out of the set for any n,m. Also, your function f is usually called an indicator function and for the set X is written 1 _X .

In fact that means that there must be uncountably many (or zero) sets that satisfy the properties. This is because each 2^-n m is either on or off so can be used to generate an arbitrary binary number.

In fact I believe we can go further than this. Even if you specify the value of f at all 2^-n m there must be at least a countable number of possible functions (or zero).

The set in (0,0.5) cannot be a compressed version of (0,1). If it were then for 0 < x < 0.5, f(2x) = f(x) = 1 - f(1-x). So f(2x) = 1 - f(1-x) which for x = 1/3 yields the contradiction f(2/3)=1/2. So (0,0.5) is not a squashed up version of (0,1). But by stretching out the set in (0,0.5) by a factor of 2 you must get an alternative set. Therefore there must be at least two functions f(x) that satisfy the criteria or none.

The above will now generalise for (0,2^-n ). If this is a squashed up version of the set in (0,1) then for 0 < x < 2^-n then f(2ⁿ x) = f(x) = 1 - f(1-x) in which a contradiction occurs when x = 1/(2ⁿ +1).

Therefore the set in (0,2^-n ) is not the set in (0,1) compressed.

But by the same logic that the set in (0,0.5) is not that in (0,1) compressed we also know that (0,0.25) is not (0,0.5) compressed. And this is also not (0,1) compressed as can be seen by letting n = 2. Continuing this argument we can see that the set in (0,2^-n ) is never an enlargement of the set in (0,2^-m ) for integers m and n. But of course if you do enlarge the set in (0,2^-n ) by a factor of 2ⁿ then you will get an alternative set that could specify f(x). So there are at least a countable number of possible sets f(x) that satisfy the conditions or none at all.

Sorry if this is poorly worded,

Michael

Now it is also very easy to prove that adding 2^-n to x does not change the value of f(x). (As long as x and x + 2^-n are in the domain of f(x), i.e. between 0 and 1 and not equal to m 2^-n ).

So if the functions do indeed exist then they form a sequence of functions, infinite in both directions, none of which are equal and all of which satisfy the properties.

If we denote each function in the sequence by a charcteristic number n then f_n (x) will satisfy the recurrence relationship:

0 < x < 0.5: f_n (x) = f_n (x + 0.5) = f_n-1 (2x)

There must be at least two such infinite sequences because you can reflect each function about the line x = 0.5 and you still get a valid function. And there may well be more than two sequences, but I don't know about this yet.

I've been thinking about how to construct a possible set. We could first of all set f(0.1) = 0 for instance. This would give us the value of f(x) for a countable number of x. If we could now choose another value of x that doesn't fall into the set for which we know f(x), set f(x) = 0 for this, then we would get f(x) for another countable number of x. Continuing this process we could define f(x). All we need is an alogorithm that picks a value of x which is not one that we have already covered.

Many thanks,

Michael

Let G_n (x) be a function taking the point x in (0,1) to the set of points which must be in X due to reflections at the nth level, i.e. all the points x+2^-n m in (0,1) for some m. Let H_n (x) be the set of points which must be in the complement of X, i.e. all the point -x+2^-n m in (0,1) for some m. To prove that your set is possible we need G_n (x) intersect H_m (x) empty for all n,m and x in the domain of f. Once we've proved it possible, we'll probably need the axiom of choice to pick a set of x's which will work. I'll get back to you on this soonish.

Hi. Well the first part is easy enough. If

x + 2^-n m = -x + 2^-p q then

2x = 2^-p q - 2^-n m

So

x = 2^-p-1 q - 2^-n-1 m

which is a impossible because this can be written in the form 2^-a b which have been excluded.

The equations definitely cannot be manipulated to directly obtain a contradiction. However I'm not sure if this necessarily means the sets do exist. I can't offhand think of any algorithm to generate the set, but there probably is one.

Thanks,

Michael

OK, well, if we now let G(x)=union from n=0 to infinity of G_n (x), similarly for H(x). Also G(x) intersect H(x) is empty (by your reasoning above). Let K(x)=G(x) union H(x). The sets K(x) partition [0,1], in other words, if K(x) intersect K(y) is nonempty then K(x)=K(y). We can then use the axiom of choice to pick out a subset Y of [0,1] such that the union over y in Y of K(y) is [0,1]. Therefore, the union over y in Y of G(y) has the property you are looking for I think, check my reasoning on this one...

I think that we actually want the exclusive union over y in Y of K(y) to be (0,1) (except for m 2^-n ). If we take the inclusive union (OR rather than XOR) then we may get the problem that the union may define the same f(x) to be both zero and one. We need to somehow be sure that K(y) gets to (0,1) without duplication. (Or if there is duplication we need to have a system for which value takes precedence.)

Thanks,

Michael

The idea is that if the normal union over all y in (0,1) of K(y) is (0,1) and the sets are all disjoint (K(x) intersect K(y) is empty, or K(x)=K(y)) then there is a subset of Y of (0,1) such that if x and y are in Y and K(x)=K(y) then x=y. Also, if x is in [0,1], then there is a unique y in Y such that x is in K(y). Once we have now got this set, we can then split off the G(Y) to get the set we want. I'm not sure how well I've explained this.

OK, I'm with you now. The hard part now is finding the subset of Y that you're talking about. I can see intuitively why this certainly must exist but I can't immediately think of an algorithm for determining whether or not a number is in the subset. I'll have a think about this now and will write back if I get anywhere.

Thanks,

Michael

---

Quote:

An axiom of set theory that states that for any set S there is a function (called the choice or selection function) such that for any non-empty subset X of S, f(X) is in the set X. The set of values of f is called the choice set. A choice function for S may be regarded as selecting a member from each non-empty subset of S.

---

I think you're probably right that a continuously alternating set depends on the axiom of choice. I wonder if this sort of thing can be proven? In other words, can you prove that there is no algorithm to find the set X. [Disclaimer: what follows is from distant memory, the definitions, etc. may be completely wrong!] I think that this this is to do with recursively enumerable sets. As far as I remember, a recursively enumerable set is one for which there is an algorithm to decide if it is in the set, which stops after a finite time if the point is in the set (it might never stop if the point isn't in the set). A set is recursive if the complement of the set is recursively enumerable. In other words, it is recursive if we can always decide in a finite amount of time whether or not any point is in the set. Ideally, we want our set X above to be recursive, because otherwise we will never be able to decide what points are not in X. I'll see if I can find out how one goes about proving sets are recursive or not.

Thanks for that. Well we know for certain that the set cannot be recursively enumerable. This is because if it is in the set then the algorithm must stop after a finite time. If it is not in the set then after a finite time the algorithm must say that 1-x is in the set, which constitutes an algorithm for saying the x is not in the set. By the symmetry of the situation the algorithm is not recursively enumerable. I can't immediately think of a way to show that the algorithm is not recursive (without the use of random numbers that is).

Michael

I think the problem is the following. Suppose we say that two infinite sequences a_r and b_r are considered the same if and only if m and n exist such that for all natural x:

a_m+x = b_n+x

So we consider

0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 etc

and

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 etc

to be the same.

Now is it possible to explicity set up a one-one correspondence with any sequence of 0s and 1s and the real numbers in [0,1]? The feeling is that it should be as they have the same cardinality but this is turning out to be very hard to show.

Thanks,

Michael

The problem with this is that it doesn't help to construct an algorithm, although it does make it considerably clearer. First of all, you don't have unique representation, although you can get round this by not allowing infinite sequences of 1s. The second problem is there is no algorithm that stops which can tell if two numbers are equivalent. Imagine you have an algorithm P_x (n) which gives the nth place of x. To test if x is equivalent to y, you need to test that for some m, P_x (n)=P_y (m+n) for all n. That is an infinite procedure, so you can only ever tell if they are not equal (there is always the possibility that they differ at some later point however far you go). And so on, the difficulties are enormous. You can thank Alan Turing for introducing all these difficulties!

So are you saying that what I described above is impossible? If so, then that is equivalent to proving that the set I described further above can never be explicitly found. The thing is that although as you say no algorithm can ever tell whether two sequences are the same after a finite time, all we need to do is map the sequence to a real number. Real numbers themselves have the same property - you can not ever find an algorithm to tell if they are exactly the same. So I'm really not sure at how to proceed.

Thanks,

Michael

That's true, there is no algorithm to test the equivalence of two "computable numbers", i.e. numbers x with an algorithm P_x where P_x (n) is the nth digit of n. However, there is another theory of computability due to Blum Shub and Smale, which (I think) assumes that you can have a computer that operates directly on real numbers. In this theory, you still get uncomputable numbers, and non recursive sets still pop up (I think the Mandelbrot set has recently been shown to be non recursive, but I'm not sure). Someone sent me a copy of this paper about "structural complexity theory", it's an overview of work done in this field, following the approach of Blum, Shub and Smale. It's quite hard, but you might find it interesting.
Blum, Shub and Smale followup paper (257 k)

Many thanks for that link. I haven't been able to get hold of Ghostscript yet, but should be able to by tomorrow so I look forward to reading it then. Thanks again,

Michael

Many thanks. I have finally managed to access the paper and there are indeed some very interesting points raised. To be honest I got rather lost from the second page onwards but I've looked up a few of the terms and quite a bit makes sense. Thanks,

Michael