# Showing a set is countable or not.

Let $A=\{x\in\mathbb{R}:\forall n\in\mathbb{Z}^+,\lfloor x^n \rfloor \text{ is odd} \}$

where $\lfloor x \rfloor$ is the largest integer equal or less than $x$.

Is $A$ countable?

• It seems that $A$ only consists of odd integers, but I don't have a proof of that at the moment. Dec 16, 2013 at 8:23
• I also have no examples beyond appropriate roots of odd integers, but in the other direction I only think I could argue that $A$ has measure zero. Dec 16, 2013 at 8:34
• @Leitingok $\big\lfloor\sqrt{3^7}\big\rfloor=46$, and thus $\sqrt{3}\not\in A$. Dec 16, 2013 at 8:38
• I felt at first that it was only odd integers, but now I get the feeling that there is a cantor-like set of these guys whose floored $n^{th}$ powers are odd numbers. Dec 16, 2013 at 8:50

The answer is NO. Indeed, I show below that you can find a subset of $A$ paramatrized by an infinite binary tree with $2^{\aleph_0}$ nodes.

Definition Say that a finite (or infinite) sequence of odd integers $(a_1,a_2,a_3,\ldots,a_n)$ (or $(a_i)_{i\geq 1}$) is good if $a_1 \geq 5$, $a_i^{\frac{i+1}{i}} \leq a_{i+1} \leq a_{i+1}+1 \leq (a_i+1)^{\frac{i+1}{i}}$ for every $i$ between $1$ and $n-1$ (or every $i$ if the sequence is infinite).

Lemma 1. If $(a_i)$ is good, then $a_i \geq 5^i$ for every $i$.

Proof of lemma 1. Use induction on $i$ and $a_i^{\frac{i+1}{i}} \leq a_{i+1}$.

Lemma 2. If $(a_i)$ is good, then $(a_i+1)^{\frac{i+1}{i}}-a_i^{\frac{i+1}{i}} \geq 5$ for every $i$.

Proof of lemma 2. Let $f(x)=(x+1)^{\frac{i+1}{i}}-x^{\frac{i+1}{i}}$ for $x>0$. Then $f’(x)=\frac{i+1}{i}\big((x+1)^{\frac{1}{i}}-x^{\frac{1}{i}}\big)$ so $f$ is increasing. Thanks to lemma 1, it will suffice to show that $f(5^i)\geq 5$, which follows easily from Bernoulli’s inequality.

Lemma 3. If a finite sequence $(a_i)_{1\leq i\leq n}$ is good, then there are least two good sequences of length $n+1$ that extend it.

Proof of lemma 3. Consider the interval $I=[a_n^{\frac{n+1}{n}},(a_n+1)^{\frac{n+1}{n}}]$. By the preceding lemma it has length at least $5$, so there are at least two odd integers $j$ such that the interval $[j;j+1]$ is contained in $I$.

Lemma 4. There are uncountably many infinite good sequences.

Proof of lemma 4. Iterate the preceding lemma a countable number of times, and starting from the good sequence $(5)$ we built an infinite binary tree, that will contain $2^{\aleph_0}$ nodes.

Finally, if $a=(a_i)_{i\geq 1}$ is an infinite good sequence, by construction the sequences $u_i=a_i^{\frac{1}{i}}$ and $v_i=(a_i+1)^{\frac{1}{i}}$ are “adjacent” : $(u_i)$ is nondecreasing, $(v_i)$ is nonincreasing, and $u_i \leq v_i$ for every $i$. Then, we will have a real number $x_a \in A$ such that $u_i \leq x_a \leq v_i$ for every $i$.

Now, we have $x_a\neq x_b$ if the sequences $a$ and $b$ are different. Indeed, if $i$ is the smallest index such that $a_i \neq b_i$, then the intervals $I_a=[a_i,a_{i}+1]$ and $I_b=[b_i,b_{i}+1]$ are disjoint, the first contains $x_a^i$ and the other contains $x_b^i$.

So $A$ is uncountable.

UPDATE The axiom of choice can be avoided in the construction, as follows. There are two places where the axiom of choice seems to be needed :

1) In the construction of the binary tree, at each step we must choose two new possible values for $a_{n+1}$. To fix this, take the smallest two possible values each time.

2) In the definition of the injective map $a\mapsto x_a$, we must choose a value $x_a$ in the interval $[{\sf sup}(u_i),{\sf inf}(u_i)]$. To fix this, simply set $x_a={\sf sup}(u_i)$.

• @Leitingok : you’re right, the axiom of choice can be avoided. I'll update my answer. Dec 16, 2013 at 11:46
• @Leitingok answer updated. Dec 16, 2013 at 11:52
• Ewan Delanoy, I see. thanks. Dec 17, 2013 at 4:34

This is not a solution. It is just a first step.

The first obvious observation is that $A$ has Lebesgue measure zero.

Take for example $A_1=A\cap [1,2)$. Set $A_{1,n}=\{b^n: b\in A_1\}$. We know that $A_{1,2}\subset [1,2)\cup [3,4)$, and thus $A_1\subset [1,\sqrt{2})\cup [\sqrt{3},2)$. Similarly, since the elements of $A_{1,4}$ have odd integer part, then $A_1\subset [1,\sqrt[4]{2})\cup[\sqrt[4]{3},\sqrt{2})\cup[\sqrt[4]{5},\sqrt[4]{6})\cup[\sqrt[4]{7},2)$, and in general $$A_1 \subset \bigcup_{k=1}^{2^{n-1}} \big[\sqrt[2^n]{2k-1},\sqrt[2^n]{2k}\big)=C_n,$$ which implies that $$A_1 \subset \bigcap_{n=1}^\infty\bigcup_{k=1}^{2^{n-1}} \big[\sqrt[2^n]{2k-1},\sqrt[2^n]{2k}\big)=C.$$ In order to see that $m(C)=0$, observe that we go from $C_n$, which is a union of intervals, to $C_{n+1}$ by taking off a bit less than half form each interval.

Note that this is obtained by just using the fact that $\lfloor x^{2^n}\rfloor$ is odd, for all $x\in A$.

• If you try to extend this method to $x^n$ instead of $x^{2^n},$ it doesn't work in the way you might expect. Dec 16, 2013 at 10:06