Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Call two real numbers equivalent if their binary decimal expansion differ in a finite amount of places, if S is a set which contains an element of every equivalence class, must S contain an interval?

How to show that every interval contains an (uncountable number of?) element of every equivalence class?

share|cite|improve this question
Given relation is an equivalence relation all right. But to say that "every" interval contains all equivalence classes seems strange. For example, does the interval $[\sqrt{2},\sqrt{3}\mathbf{]}$contain the equivalence class of $4$ completely? it contains only a part of equivalence class of $4$. – NikBels Jan 5 '12 at 17:18
Every equivalence class is countable. – Asaf Karagila Jan 5 '12 at 17:30
hmm got it, thanks. – NikBels Jan 6 '12 at 9:34
up vote 2 down vote accepted

First, a technical point: for terminating expansions in binary, such as 1 or ½, we must choose one of the two valid binary expansions for representing them: for instance, either 1.000... or 0.111... in the case of 1. This is necessary for the equivalence classes to be well-defined. We may establish the convention of always choosing the terminating expansion.

Then, you can solve your problem by making the following observations:

  • For a given equivalence class E and a fixed representative e ∈ E, how can you characterize an arbitrary x ∈ E relative to e? What are the implications for the cardinality of E?

  • Is there any particularly simple sort of interval which is guaranteed to contain at least one representative from each equivalence class? Can you show that any interval strictly contains such an interval (and therefore, also contains infinitely many)?

  • Consider a partitioning of ℝ into the rational and irrational numbers. Can you find a way of selecting representatives for each equivalence class of the rationals, and also for the irrationals, such that their union does not contain any intervals?

I think that this approach should be fairly straightforward.

share|cite|improve this answer

Added part: We produce a bounded set $S$ that contains a member of every equivalence class but does not contain an interval. Every equivalence class meets $[0,1]$, since for any $x$, we can, by making a finite number of changes to the bits of $x$, produce an $x'\in [0,1]$.

Use the Axiom of Choice to select $S\subset [0,1]$ such that $S$ contains precisely one member of each equivalence class. Any two dyadic rationals (expressed in ultimately $0$'s form) belong to the same equivalence class, so $S$ contains exactly one dyadic rational. Since the dyadic rationals are dense in the reals, this means that $S$ cannot contain an interval of positive length. (End of added part)

Every non-empty interval $I$ contains a member of every equivalence class. For let $I$ be a (finite) interval, and let $a$ be its midpoint. Suppose that $I$ has length $\ge 2\times 2^{-n}$. Let $x$ be any real number. By changing the initial bits of $x$ so that they match the initial bits of $a$, up to $n$ places after the "decimal" point, we can produce an $x'$ equivalent to $x$ which is at distance less than $2^{-n}$ from $a$.

Edit: The question has changed to ask whether every interval contains an uncountable number of members from every equivalence class. Minor modification of the first paragraph shows that every interval contains a countably infinite number of members from every equivalence class. As Asaf Karagila points out, one cannot get more, since every equivalence class is itself countable. (The set of places where there is "change" can be identified with a finite subset of the integers, and $\mathbb{N}$ has only countably many finite subsets.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.