# explicit big linearly independent sets

In the following, I use the word "explicit" in the following sense: No choices of bases (of vector spaces or field extensions), non-principal ultrafilters or alike which exist only by Zorn's Lemma (or AC) are needed. Feel free to use similar (perhaps more precise) notions of "explicit", but reasonable ones! To be honest, I'm not so interested in a discussion about mathematical logic. If no example is there, well, then there is no example. ;-)

Can you give explicit large linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$? For example, $\{\ln(p) : p \text{ prime}\}$ is such a set, but it's only countable and surely is no basis. You can find more numbers which are linearly independent, but I cannot find uncountably many. AC implies $\dim_\mathbb{Q} \mathbb{R} = |\mathbb{R}|$. Perhaps $ZF$ has a model in which every linearly independant subset of $\mathbb{R}$ is countable?

The same question for algebraically independent subsets of $\mathbb{R}$ over $\mathbb{Q}$? Perhaps the set above is such a subset? But anyway, it is too small.

Closely related problems: Can you give an explicit proper subspace of $\mathbb{R}$ over $\mathbb{Q}$, which is isomorphic to $\mathbb{R}$? If so, is the isomorphism explicit? Same question for subfields.

That would be great if there were explicit examples. :-)

-

Here is a linearly independent subset of $\mathbb{R}$ with size $2^{\aleph_0}$.

Let $q_0, q_1, \ldots$ be an enumeration of $\mathbb{Q}$. For every real number $r$, let $$T_r = \sum_{q_n < r} \frac{1}{n!}$$ The proof that these numbers are linearly independent is similar to the usual proof that $e$ is irrational. (It's a cute problem; there's spoiler below.)

I think a similar trick might work for algebraic independence, but I don't recall having seen such a construction. Actually, John von Neumann showed that the numbers $$A_r = \sum_{n=0}^\infty \frac{2^{2^{[nr]}}}{2^{2^{n^2}}}$$ are algebraically independent for $r > 0$. [Ein System algebraisch unabhängiger zahlen, Math. Ann. 99 (1928), no. 1, 134–141.] A more general result due to Jan Mycielski seems to go through in ZF + DC perhaps just ZF in some cases. [Independent sets in topological algebras, Fund. Math. 55 (1964), 139–147.]

As for subspaces and subfields isomorphic to $\mathbb{R}$, the answer is no. (Since I'm not allowed to post any logic here, I'll refer you to this answer and let you figure it out.)

Well, I'll bend the rules a little... Consider a $\mathbb{Q}$-linear isomorphism $h:\mathbb{R}\to H$, where $H$ is a $\mathbb{Q}$-linear subspace of $\mathbb{R}$ (i.e. $h$ is an additive group isomorphism onto the divisible subgroup $H$ of $\mathbb{R}$). If $h$ Baire measurable then it must be continuous by an ancient theorem of Banach and Pettis. It follows that $h(x) = xh(1)$ for all $x \in \mathbb{R}$ and therefore $H = \mathbb{R}$. Shelah has produced a model of ZF + DC where all sets of reals have the Baire property, so any such $h$ in this model must be Baire measurable. A similar argument works if Baire measurable is replaced by Lebesgue measurable, but Solovay's model of ZF + DC where all sets of reals are Lebesgue measurable uses the existence of an inaccessible cardinal, and this hypothesis was shown necessary by Shelah.

Spoiler

Suppose for the sake of contradiction that $r_1 > r_2 > \cdots > r_k$ and $a_1,a_2,\ldots,a_k \in \mathbb{Z}$ are such that $a_1T_{r_1} + a_2T_{r_2} + \cdots + a_kT_{r_k} = 0$. Choose a very large $n$ such that $r_1 > q_n > r_2$. If $n$ is large enough that $$(|a_1| + |a_2| + \cdots + |a_k|) \sum_{m=n+1}^\infty \frac{n!}{m!} < 1$$ then the tail terms of $n!(a_1T_{r_1}+\cdots+a_kT_{r_k}) = 0$ must cancel out, and we're left with $$a_1 = -\sum_{m=0}^{n-1} \sum_{q_m < r_i} a_i \frac{n!}{m!} \equiv 0 \pmod{n}$$ If moreover $n > |a_1|$, this means that $a_1 = 0$. Repeat to conclude that $a_1 = a_2 = \cdots a_k = 0$.

-
Very nice!!!!!! – Steven Gubkin May 1 '10 at 21:49
It depends where you put the word "explicit" ... $\mathbb{R}$ is explicitly ismorphic to a subspace of $\mathbb{R}^2$, right? Well, according to AC, $\mathbb{R}^2$ is also (non-explicitely) isomorphic to $\mathbb{R}$. – Gerald Edgar May 1 '10 at 23:40
perfect ! – Martin Brandenburg May 2 '10 at 9:57
@FrançoisG.Dorais: Dear François, does this trick (for constructing a large $\mathbb{Q}$-linearly independent subset) above belong to you? If not, do you know who should be credited if someone is to use this cute trick? – Burak Apr 1 '15 at 22:49
@Burak: I couldn't honestly claim ownership of this trick. I might have extracted it from earlier (and broader reaching) work by Jan Mycielski. I do recall that the first time I presented the trick was at a graduate student seminar at Dartmouth (over a decade ago). Unfortunately, I don't recall why or how I came up with the trick. At best, I rediscovered a trick which was known decades before I was even born... – François G. Dorais Apr 1 '15 at 23:40

Here's an answer that's similar in spirit to Pietro Majer's, but not quite the same.

As a first step, choose an uncountable family of infinite subsets of positive integers such that any two distinct sets in the family have finite intersection. This can be done explicitly in many ways. One I like is as follows. Since one can take an explicit bijection between $\mathbb{N}$ and $\mathbb{Z}^2$, it's good enough to create a family of subsets of $\mathbb{Z}^2$ instead. And to do that, for each real number $\alpha\in[0,\pi)$ take the set of all points in $\mathbb{Z}^2$ that are within a distance 2 (say) of the line that makes an angle $\alpha$ with the x-axis.

Once we have such a family F, we define a real number $r_X$ for each X in F as follows. It is a number between 0 and 1 that has only 0s and 1s in its decimal expansion. And it has a 1 at the nth place if and only if $n=m^2$ for some $m\in X$. (The reason for restricting to the squares is simply that we want the gaps between successive places where there might be a 1 to get larger and larger, so that we can ignore carrying problems.)

The numbers $r_X$ are linearly dependent over $\mathbb{Q}$ only if we can find a non-zero integer combination of finitely many of them that gives zero. But we can't: if we've got a non-zero coefficient t, then after a while the gaps will be longer than the number of digits of t (or even of the sum of the absolute values of the coefficients, say), and we'll be able to find an element of the corresponding set $X\in F$ that belongs to none of the other sets, thereby proving that that integer combination is not zero.

-

Here is an example in the spirit of the combinatorics of binary expansions. The moral is again that AC is not needed to exhibit uncountable linearly independent sets, even though it is needed to find bases.

Consider the family $\{ u_\alpha\} _ {\alpha\in\mathbb{R _ +}},$ where $u_\alpha$ is the real number whose binary sequence has support in the set $$S_\alpha:=\{ \lfloor \exp{\alpha k}\rfloor \,: \, k\in\mathbb{N} \}\, ,$$

namely $$u_\alpha:=\sum_{k \in S_\alpha} 2^{-k}\, .$$

This family is linearly independent over $\mathbb{Q}$. The relevant fact in order to see it is, that the subsets $S_\alpha\subset \mathbb{N}$ have the property that for any finite collection of them, say with $\alpha_1 < \alpha_2\dots < \alpha_r,$ the relative density of each of them, $S _ {\alpha_j},$ in their union $\cup_{1\leq i\leq r} S _ {\alpha_i}$ is exactly 1 if $j=1,$ and 0 otherwise (the smaller is $\alpha$, the thicker is $S_\alpha$). From this it follows easily that no non-trivial linear combination of $u_{\alpha_1},\dots,u_{\alpha_r}$ with integer coefficients may vanish (otherwise, one starts by looking at the coefficient relative to $u_{\alpha_1}$ and proves it has to be zero, otherwise $u_{\alpha_1}$ would be a linear combination of $u_{\alpha_2},\dots,u_{\alpha_r}$ with integer coefficients. But this implies an inclusion of the supports, up to finitely many translations: $S_{\alpha _ 1} \subset \cup_{2\leq i\leq r} (S _ {\alpha_i}+F_i)$, for some finite sets $F_2,\dots,F_r$, contradicting the above stated density property).

-

It would be a great surprise to me were there a linear relation between the numbers $\pi^x$, as $x$ ranges over reals all of whose digits in base $3$ are $0$ or $1$.... I guess there must be an example for which one can actually prove something :-)

-
This looks good! I've already tried to show that this set (or a similar one, some weeks ago) is linearly independent, but I think this is quite hard. – Martin Brandenburg May 1 '10 at 21:32
I think I agree! – Ben Green May 1 '10 at 21:48