explicit big linearly independent sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T02:55:06Z http://mathoverflow.net/feeds/question/23202 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23202/explicit-big-linearly-independent-sets explicit big linearly independent sets Martin Brandenburg 2010-05-01T21:20:15Z 2012-11-24T09:35:08Z <p>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. ;-)</p> <p>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?</p> <p>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.</p> <p>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.</p> <p>That would be <em>great</em> if there were explicit examples. :-)</p> http://mathoverflow.net/questions/23202/explicit-big-linearly-independent-sets/23205#23205 Answer by Ben Green for explicit big linearly independent sets Ben Green 2010-05-01T21:29:17Z 2010-05-01T21:29:17Z <p>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 :-)</p> http://mathoverflow.net/questions/23202/explicit-big-linearly-independent-sets/23206#23206 Answer by François G. Dorais for explicit big linearly independent sets François G. Dorais 2010-05-01T21:42:31Z 2010-05-02T02:46:20Z <p>Here is a linearly independent subset of $\mathbb{R}$ with size <code>$2^{\aleph_0}$</code>. </p> <p>Let $q_0, q_1, \ldots$ be an enumeration of $\mathbb{Q}$. For every real number $r$, let $$T_r = \sum_{q_n &lt; 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.)</p> <p>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] A more general result due to Jan Mycielski seems to go through in ZF + DC perhaps just ZF in some cases. [<a href="http://matwbn.icm.edu.pl/ksiazki/fm/fm55/fm55112.pdf" rel="nofollow">Independent sets in topological algebras</a>, Fund. Math. 55, 1964]</p> <p>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 <a href="http://mathoverflow.net/questions/16666/does-conzf-imply-conzf-aut-c-z-2z/16683#16683" rel="nofollow">this answer</a> and let you figure it out.) </p> <p>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 <a href="http://en.wikipedia.org/wiki/Property_of_Baire" rel="nofollow">Baire property</a>, 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.</p> <hr> <p><em><strong>Spoiler</em></strong></p> <p>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!} &lt; 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 &lt; 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$.</p> http://mathoverflow.net/questions/23202/explicit-big-linearly-independent-sets/32710#32710 Answer by Pietro Majer for explicit big linearly independent sets Pietro Majer 2010-07-20T22:43:53Z 2012-11-24T09:35:08Z <p>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.</p> <p>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} \}\ ,$$</p> <p>namely $$u_\alpha:=\sum_{k \in S_\alpha} 2^{-k}\ .$$</p> <p>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 &lt; \alpha_2\dots &lt; \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).</p> http://mathoverflow.net/questions/23202/explicit-big-linearly-independent-sets/32780#32780 Answer by gowers for explicit big linearly independent sets gowers 2010-07-21T10:28:16Z 2010-07-21T10:28:16Z <p>Here's an answer that's similar in spirit to Pietro Majer's, but not quite the same.</p> <p>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.</p> <p>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.)</p> <p>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.</p>