# Set theory and rational numbers

A set $Q$ contains $0$, $1$ and the average of all elements of every finite non-empty subset of $Q$. Prove that $Q$ contains all rational numbers in $[0,1]$.

This is the exact wording, as it was given to me. Obviously, the elements that correspond to the average, are rational, since they can be expressed as $\frac{(q_1+q_2+\dots q_k)}{k}$, where $0\leq k\leq1$. But I don't know how to proceed.

• @5xum thanks for the edit! I am new here and not very familiar with the editor! – Carlos Lopez Sep 29 '17 at 10:10
• Just a quick comment - I would change your subscript on the $q_k$ to avoid using $k$ with two different meanings :-) – TheMathsGeek Sep 29 '17 at 10:12
• You shouldn't have $0\leq k\leq 1$, it's the $q$'s that are between $0$ and $1$, not the index. – Michael Burr Sep 29 '17 at 10:32

Let's explore the first few possibilities to see what's going on.

• You already know that $Q$ contains $0$ and $1$.

• The average of $0$ and $1$ is $\frac{1}{2}$, so this is in $Q$ too.

• The average of $0$ and $\frac{1}{2}$ is $\frac{1}{4}$ and the average of $\frac{1}{2}$ and $1$ is $\frac{3}{4}$.

• For $\frac{1}{3}$, we see that this is the average of $0$, $\frac{1}{4}$, and $\frac{3}{4}$. Similarly, $\frac{2}{3}$ is the average of $1$, $\frac{3}{4}$, and $\frac{1}{4}$.

Now, let's prove this more completely (although somewhat sketchy because the complete rigor is somewhat messy).

Step 1: Prove that all dyadic numbers are in this set. A dyadic number is a fraction of the form $\frac{a}{2^n}$ for integer $a$ and some natural number $n$. For our case, it is safe to assume that $a$ is odd and that $0<a<2^n$.

Proof by induction on $n$, the only dyadic number (satisfying the conditions) when $n=1$ is $\frac{1}{2}$, which is the average of $0$ and $1$.

Inductive step, consider the dyadic number $\frac{a}{2^{n+1}}$. We can observe that this is the average of $\frac{a+1}{2^{n+1}}$ and $\frac{a-1}{2^{n+1}}$. Note that both $a+1$ and $a-1$ are even, so these are actually dyadic numbers with smaller denominators, so they are in the set by the inductive hypothesis (if $a+1=2^{n+1}$ or $a-1=0$, then these numbers are $0$ or $1$, which are given to be in the set).

Step 2: Prove that all rational numbers are in the set using dyadic numbers.

Let $\frac{p}{q}$ be an arbitrary rational number. To get this rational number, it must be an average of $q$ numbers whose sum is $p$. We can write $p$ as a sum of dyadic numbers in the following way:

Choose $p$ dyadic numbers that are all near $1$, for example, $\frac{2^n-1}{2^n}$. With various $n$'s large enough, the difference between the sum of these numbers and $p$ is a small (close to zero) dyadic number. It would be of the form $\frac{a}{2^n}$ for $a$ relatively small.

We now need to write $\frac{a}{2^n}$ as a sum of $q-p$ dyadic numbers. We can rewrite this fraction as $\frac{a2^m}{2^{n+m}}$ so that $a2^m$ is larger than $q-p$, let this be $\frac{b}{2^{n+m}}$, observe that this is the sum of $\frac{b-1}{2^{n+m+1}}$ and $\frac{b+1}{2^{n+m+1}}$. By repeatedly splitting the smallest element of the set in this way until you have $q-p$ elements, you have a collection whose average is $\frac{p}{q}$. Note that by the choice of $b$, you'll never reach $0$ using this splitting technique (and that all of the numbers are distinct).

• you are a genius! – Carlos Lopez Sep 29 '17 at 10:48
• You might want to try alternate constructions for $\frac{p}{q}$, different approaches might give an expression that's easier to write down. – Michael Burr Sep 29 '17 at 11:04

By successively taking midpoints we can produce all numbers of the form $${k\over2^n}\qquad(n\geq0, \ 0\leq k\leq 2^n)\ .$$ Now let two numbers $0<p<q$ be given. Write $q-p=:p'$ for simplicity. Choose a sufficiently large $n$ (see below), and put $$k_i:=i-1\quad(0< i\leq p'),\qquad k_{q-i}:=2^n-i\quad(0\leq i<p)\ .$$ One then has $$\sum_{i=1}^q k_i=p\cdot 2^n+{(p'-1)p'\over2}-{(p-1)p\over2}=:p\cdot 2^n+\Delta\ .$$ Note that $|\Delta|<{q^2\over2}$. If $\Delta>0$ replace the first "large" $k_i\,$, namely $k_{p'+1}$, by $\ k_{p'+1}^{\rm new}:=k_{p'+1}-\Delta$. If $n$ is large enough then one still has $k_{p'+1}^{\rm new}>k_{p'}$. Make a similar correction if $\Delta<0$. The numbers $$x_i:={k_i\over 2^n}\in Q\quad(1\leq i\leq q)$$ now form an increasing sequence of $q$ different numbers, and one has $${1\over q}\sum_{i=1}^q x_i={1\over q\cdot 2^n}\sum_{i=1}^q k_i={p\cdot 2^n\over q\cdot 2^n}={p\over q}\ ,$$ hence ${p\over q}\in Q$.