# Does k(X) have a k-basis for every set X, without AC?

This question is inspired by Pace Nielsen's recent question Does a left basis imply a right basis, without AC?.

For any field $k$, the field $k(x)$ of rational functions in one variable has an explicit $k$-basis given by partial fractions: the set $$B(x,k)=\left\{x^i:i\geq 0\right\}\cup \left\{\frac{x^i}{m(x)^j}:\mbox{m(x) monic irreducible, } 0<j, 0\leq i<\operatorname{deg}(m)\right\}$$ is a basis.

By induction, $k(x_1,\dots,x_n)$ has a $k$-basis for any $n$, without needing to assume the axiom of choice. The obvious way of doing this gives a basis that depends on the choice of an order for the variables.

In ZF set theory without choice, must $k(X)$ have a $k$-basis for an arbitrary set $X$?

The existence of such a basis certainly doesn't need the full strength of AC. The statement that every set has a total order is known to be independent of ZF but not to imply AC (see for example the various references in Are all sets totally ordered ?). If $X$ has a total order, and for $y\in X$ we let $$X_{<y}=\left\{x\in X: x<y\right\},$$ then the set of finite products $t_1t_2\dots t_n$, where $$1\neq t_i\in B\left(y_i,k(X_{<y_i})\right)$$ for some $y_1<\dots < y_n$, is a $k$-basis of $k(X)$.

• So we need to choose canonically whether $1/(x-y)$ or $1/(y-x)$ goes in the basis. That may take the axiom of choice after all. Jan 9, 2015 at 16:39
• Is it known how the axiom "every set $X$ satisfies $Or(X)$: there is a section of the projection $(x,x')\mapsto \{x,x'\}$ from the set of pairs of $X$ to the set of 2-elements subsets" is related to AC? of course $Or(X)$ is strictly weaker than the existence of a well-ordering on $X$.
– YCor
Jan 13, 2015 at 14:26
• @YCor: A shorter way of saying that is that every set carries a tournament. I believe it’s equivalent to the axiom of choice for 2-element sets: on the one hand, it allows you to select one element from each unordered pair from a given set (e.g., the first in the ordered pair given by your section); in the opposite direction, you can take a selector on $\{\{(x,y),(y,x)\}:x\ne y\in X\}$. Jan 13, 2015 at 14:50
• I’m not an expert on these matters, however “every set has a total order” must be strictly stronger, as it in fact implies the axiom of choice for (unbounded) finite sets. The axiom of choice for pairs doesn’t even imply the axiom of choice for triples, see e.g. rjlipton.wordpress.com/2010/04/12/… . Jan 13, 2015 at 15:12
• @PaceNielsen: Define the monoid $M_X$ of monomials to consist of functions $X\to\mathbb N$ that are $0$ for all but finitely many $x\in X$, with pointwise addition, and then the ring $k[X]$ as the set of functions $M\to k$ that are $0$ for all but finitely many arguments, with pointwise addition, and convolution as multiplication. No choice is involved. Jan 17, 2015 at 20:11

I will show that, if $k$ is countable and has characteristic $0$, then $k(X)$ has a basis. (This whole proof takes place without choice.)

For any $x \in X$, and any $f \in X$, we define an element $r_x(f)$ of $k(X \setminus \{ x \})$ as follows: We have $k(X) \cong k(X \setminus \{ x \})(x)$, which embeds into the field of formal Laurent series $k(X \setminus \{ x \})((x))$. Let $r_x(f)$ be the coefficient of $x^0$ in this Laurent series. For a finite subset $I$ of $X$, let $r(I)$ be $$\{ f \in k(I) : r_x(f) =0\ \forall_{x \in I} \}.$$

For any finite set $I$, we have $k(I) = \bigoplus_{J \subseteq I} r(J)$ so, since $k(X)$ is the union of the $k(I)$ for $I$ finite, we have $k(X) = \bigoplus_{I \subseteq X,\ \# I < \infty} r(I)$. So it is enough to show $\bigoplus_{I \subseteq X,\ \# I < \infty} r(I)$ has a basis. For this purpose, it is enough to show that $r(\{ x_1, x_2, \ldots, x_n \})$ has an $S_n$ invariant basis. One can then transport this basis to each of the $r(I)$ with $\#I = n$. (More precisely, look at all $n!$ bijections between $\{ 1, \ldots, n \}$; each of them gives a transported basis in $r(I)$. Using the $S_n$ invariance, their union is also a basis in $r(I)$. Thus, we get a basis in $r(I)$ without having to choose an ordering of $I$.)

We fix particular representatives $Sp_{\lambda}$ for the irreducible representations of $S_n$. This can be done in a choice free way by, for example, writing down formulas with Young tableaux. For any $S_n$-representation $W$, let $W_{\lambda} = \mathrm{Hom}_{S_n}(Sp_{\lambda}, W)$. Then there is an obvious map $\bigoplus_{|\lambda| = n} W_{\lambda} \otimes Sp_{\lambda} \longrightarrow W$ and representation theory tells us this map is an isomorphism. We will show that $r(\{ x_1, \ldots, x_n \})_{\lambda}$ has a countably infinite basis for each $\lambda$, and we will pick a particular one without choice. Thus $$r(\{x_1, \ldots, x_n \}) \cong \bigoplus_{|\lambda| = n} k^{\oplus \omega} \otimes Sp_{\lambda} \cong (k S_n)^{\bigoplus \omega}$$ as $S_n$ representations, and the latter has an obvious permutation basis.

Lemma: Any subspace $V$ of $k^{\oplus \omega}$ has a countable or finite basis, which can be found with no choices.

Proof: Let $e_i$ be the standard basis vectors of $k^{\oplus \omega}$. Let $k^n$ be the subspace of $k^{\oplus \omega}$ spanned by $e_1$, $\dots$, $e_n$. Let $S \subseteq \omega$ be the set of $n$ for which $V \cap k^n \neq V \cap k^{n-1}$. For each $s \in S$, there is a unique $v_s \in V$ such that $v_s \in k^n \cap V$, the coefficient of $e_s$ in $v_s$ is $1$, and $v_s$ does not contain the basis vectors $e_{s'}$ for $s' \in S$, $s < n$. These $v_s$ form a basis. (In other words, we use row reduced echelon form.) $\square$

Now, $k(x_1, \ldots, x_n)$ has a countable basis. So $r(\{ x_1, \ldots, x_n \})$ has a countable or finite basis by the lemma. The Specht module $Sp_{\lambda}$ has an explicit finite basis which can be written down using standard Young tableaux, so $\mathrm{Hom}(Sp_{\lambda}, r(\{ x_1, \ldots, x_n \}))$ has a basis (note that this is $\mathrm{Hom}$ of vector spaces). The $S_n$ equivariant maps are a subspace of this so, using the lemma again, $\mathrm{Hom}_{S_n}(Sp_{\lambda}, r(\{ x_1, \ldots, x_n \}))$ has an explicit finite or countable basis, as desired.

Finally, we must check that $\mathrm{Hom}_{S_n}(Sp_{\lambda}, r(\{ x_1, \ldots, x_n \}))$ is infinite dimensional. The easiest way is probably to note that, for any distinct positive integers $(a_1, \ldots, a_n)$, the span of $x_1^{a_{\sigma(1)}} \cdots x_n^{a_{\sigma(n)}}$ forms a copy of $k S_n$ inside $r(\{ x_1, \ldots, x_n \})$, and these are all linearly independent.

• $k(x)$ has an independent subset $\{(x-a)^{-1}:a\in k\}$ of size $|k|$, hence $k(x_1,\dots,x_n)$ only has a countable basis if $k$ itself is countable. Or am I missing something? Jan 20, 2015 at 13:43
• Oh, uggh, you're right. I thought through a lot of this with $\mathbb{Q}$ and then switched at the last moment. Editing now... Jan 20, 2015 at 13:45
• Very nice! ---- Jan 20, 2015 at 17:54
• The argument I gave in essence exploits the field structure of $W=k(x_1,\dots,x_n)$ to provide an explicit isomorphism $W\simeq W_\lambda\otimes kS_n$, where $\lambda=(n)$ corresponds to the trivial representation. I don’t know whether such a thing stands a chance of working for $r(I)$, but if so, it would considerably alleviate the need for $k$ to be countable. Jan 20, 2015 at 21:49
• This argument also works for any well-orderable $k$; you just have to find $|k|$ copies of the regular representation in each $r(I)$. In particular, assuming choice, this shows $k(X)$ has a symmetric basis for any $k$ of characteristic zero. Jan 21, 2015 at 1:26

If $k= \mathbb{F}_2$, I will show that this implies the axiom of choice for pairs. Suppose $k(X)$ has a basis and let $f$ be a basis element. For any $x$ and $y$ in $X$, let $c(x,y)$ be the coefficient of $f$ in $\frac{x}{x+y} f$. Since $\frac{x}{x+y} f + \frac{y}{x+y} f = f$, we have $c(x,y)+c(y,x)=1$, so one of $c(x,y)$ and $c(y,x)$ is $0$ and the other is $1$; this gives a choice function $X^2 \to X$.

On the other hand, I believe I can show $k(X)$ has a basis without choice whenever $k$ has characteristic zero. It's a long one -- I'll try to write it up later tonight.

• A similar argument shows that for $k=\mathbb{F}_3$, you get choice for 3-element sets (if three elements of $\mathbb{F}_3$ add to 1, two must be equal and the other one is a canonical choice). More generally, for $k=\mathbb{F}_p$ you get a choice of a nontrivial partition of every $p$-element set, which surely requires choice. Jan 20, 2015 at 2:46
• Very nice! More generally this shows (if we stick to characteristic 2) that if there's no choice function for pairs of elements of $X$, but there is for pairs of elements of $k$, then $k(X)$ can't have a basis. I wonder what happens if there's no choice function for pairs of elements of $k$? It would seem a bit weird if $k$ having bad choice properties made it easier to find a basis, although I suppose that for particular (related) $k$ and $X$, there might be a construction of a basis that avoids choice. Jan 20, 2015 at 10:02
• Essentially the same argument also gives a direct proof that if $k$ is a field of positive characteristic, then $k(x_1,x_2,\dots)$ does not have an almost symmetric basis. If $f$ is any basis element of such an almost symmetric basis, pick $p$ variables not occuring in $f$ (or the finite set your permutations must fix) and apply this argument to get a contradiction. Jan 20, 2015 at 11:55
• Why is $c(x,y)$ independent of $f$? Suppose the basis includes 1, $x$, $x/(x+y)$, $xy/(x+y)$. Then $c(x,y\,|\,f=1) = 0$ but $c(x,y\,|\,f=x) = 1$. Jan 21, 2015 at 1:49
• @MattF. It's not. We choose one $f$, once and for all, and then define $c(x,y)$ using it. Jan 21, 2015 at 2:28

As a generalization of David Speyer's argument, here is a proof that if $k(X)$ always has a basis, then the axiom of choice for finite sets of bounded cardinality holds. In fact, to get the axiom of choice for sets of size at most $n$, we will only use the existence of a nontrivial linear map $\mathbb{F}_p(X)\to \mathbb{F}_p$ for each prime $p\leq n$.

Fix $n$, let $X$ be any set, and suppose there exists a nontrivial linear map $\mathbb{F}_p(X)\to \mathbb{F}_p$ for all $p\leq n$. Then I claim there is a function that takes any subset $X$ of cardinality between $2$ and $n$ and gives a nonempty proper subset. By iterating this function until we reach a singleton, we get a choice function for subsets of $X$ of size at most $n$.

For each $p\leq n$, fix a nontrivial linear map $T_p:\mathbb{F}_p(X)\to\mathbb{F}_p$ and an element $f_p\in \mathbb{F}_p(X)$ that is not in the kernel of $T_p$. Let $S\subseteq X$ be a subset with $2\leq|S|\leq n$ and let $p$ be the least prime dividing $|S|$. Define a function $g:S\to \mathbb{F}_p$ by $$g(s)=T_p\left(\frac{s}{\sum_{t\in S}t}f_p\right).$$ By linearity of $T_p$, $\sum_s g(s)=T_p(f_p)\neq 0$. In particular, since $p$ divides $|S|$, the $g(s)$ cannot all be the same. Let $C(S)=g^{-1}(\{k\})$ for the least $k\geq 0$ for which this set is nonempty. Then $C(S)$ is a nonempty proper subset of $S$, and $S\mapsto C(S)$ is the desired function.

While the question is still unanswered, let me make a couple of observations, showing that the problem is essentially equivalent to construction of symmetric bases (this is already alluded to in Is there a symmetric basis for $\mathbf{Q}(x,y)$? , however we really need infinitely many variables).

Any permutation $\pi$ of $X$ extends uniquely to a $k$-automorphism of $k(X)$, which I will also denote $\pi$. Let me say that a basis $B$ of $k(X)$ is symmetric if $\pi(B)=B$ for every permutation $\pi$, and almost symmetric if there is a finite set $X_0\subseteq X$ such that $\pi(B)=B$ for every permutation $\pi$ fixing $X_0$ pointwise.

Proposition 1: ZF proves that if $k(\{x_n:n\in\mathbb N\})$ has an almost symmetric basis, then $k(X)$ has a basis for every set of variables $X$.

Proof: Pick a basis $B$ of $k(\{y_n:n\in\mathbb N\})$ invariant under all permutations fixing $Y_0=\{y_1,\dots,y_m\}$. If $X$ is finite, $k(X)$ has a basis by induction on $|X|$, for example the one in the question, hence we can assume $X$ is infinite. Fix distinct elements $x_1,\dots,x_m\in X$, and put $$B_X=\{f(x_1,\dots,x_n):n\ge m,f(y_1,\dots,y_n)\in B,x_{m+1},\dots,x_n\in X\}$$ where the $x_{m+1},\dots,x_n$ are pairwise distinct and disjoint from $\{x_1,\dots,x_m\}$ (this did not fit into the displayed line).

Since any element of $k(X)$ is contained in $k(x_1,\dots,x_n)$ for some $x_1,\dots,x_n$ as above, $B_X$ generates $k(X)$. On the other hand, any finite subset $B_0\subseteq B'$ is also included in some $k(x_1,\dots,x_n)$, and then the symmetry of $B$ implies that $\{f(y_1,\dots,y_n):f(x_1,\dots,x_n)\in B_0\}\subseteq B$, hence it is linearly independent.

Proposition 2: Conversely, if ZF proves that every $k(X)$ has a basis, then ZF(C?) proves that $k(\{x_n:n\in\mathbb N\})$ has an almost symmetric basis.

Proof: Assume (in a model of ZF) that $k(\{x_n:n\in\mathbb N\})$ has no almost symmetric basis, we will extend the universe into a permutation model of ZFA where some $k(X)$ has no basis. This can be made into a model of ZF by the Jech–Sochor embedding theorem; however, I suspect that the forcing involved in that step may need some choice in the ground model, which is why I put the half-hearted C in the statement.

As for the permutation model: we extend the universe with a countable set of atoms $A=\{a_n:n\in\mathbb N\}$. We take the group of all permutations of $A$, and the normal filter generated by stabilizers of finite subsets of $A$. In the resulting permutation model, $k(A)$ has no basis $B$: otherwise $B$ would also be a basis of $k(A)\simeq k(\{x_n:n\in\mathbb N\})$ in the ground model, and it would have finite support, which is exactly what I called almost symmetric above.

Proposition 3: ZF proves that $k(x_1,\dots,x_n)$ has an explicitly definable symmetric basis for every field $k$ and $n\in\mathbb N$.

Proof: Let $B_0$ be any basis of $k(y_1,\dots,y_n)$, which exists by induction on $n$ (e.g., we can take the one described in the question). Let $s_k(x_1,\dots,x_n)$ denote the $k$th elementary symmetric polynomial, and put $$K=k(s_1(x_1,\dots,x_n),\dots,s_n(x_1,\dots,x_n))\subseteq k(x_1,\dots,x_n).$$ Since the $s_k(\vec x)$ are algebraically independent, $K$ is isomorphic to $k(y_1,\dots,y_n)$, and $$B_1=\{f(s_1(x_1,\dots,x_n),\dots,s_n(x_1,\dots,x_n)):f(y_1,\dots,y_n)\in B_0\}$$ is a basis of $K$ over $k$. The field $L=k(x_1,\dots,x_n)$ is the splitting field of the degree $n$ polynomial $$h(x)=(x-x_1)\cdots(x-x_n)$$ over $K$, hence $[L:K]\le n!$. (Actually, it is easy to see that $\mathrm{Gal}(L/K)=S_n$, hence the degree is exactly $n!$.)

I claim that $$B_2=\{x_1^{\pi(1)}\cdots x_n^{\pi(n)}:\pi\in S_n\}$$ is a $K$-basis of $L$, hence $B=B_1B_2$ is a $k$-basis of $L$, and it is obviously symmetric.

Since we already know $|B_2|\ge[L:K]$, it suffices to show that $B_2$ is $K$-linearly independent. I have no high-level argument for that, but one can prove it by induction on $n$. It will be more convenient to label the variables as $x_0,\dots,x_{n-1}$, and consider $S_n$ as permutations on $\{0,\dots,n-1\}$.

The case $n=1$ is trivial, so assume the statement holds for $n$, we will show it for $n+1$. Aiming for contradiction, let $$\sum_{\pi\in S_{n+1}}f_\pi(x_0,\dots,x_n)\prod_{i=0}^nx_i^{\pi(i)}=0,\tag{*}$$ where the $f_\pi\in K$ are not all zero. We may assume without loss of generality that the rational functions $f_\pi$ are in fact polynomials, and that $x_0\cdots x_n$ does not divide all $f_\pi$.

Let $i_0\le n$. If we substitute $0$ for $x_{i_0}$ in $(*)$, and rename $x_{i_0+1},\dots,x_n$ to $x_{i_0},\dots,x_{n-1}$, we get $$x_0\cdots x_{n-1}\sum_{\pi'\in S_n}f_{\pi}(x_0,\dots,x_{i_0-1},0,x_{i_0},\dots,x_{n-1})\prod_{i=0}^{n-1}x_i^{\pi'(i)}=0,$$ where $$\pi(i)=\begin{cases} \pi'(i)+1&i<i_0,\\ 0&i=i_0,\\ \pi'(i-1)+1&i>i_0. \end{cases}$$ By the induction hypothesis, we obtain that $f_\pi(x_0,\dots,x_{i_0-1},0,x_{i_0+1},\dots,x_n)=0$ whenever $\pi(i_0)=0$. Thus, any $f_\pi$ is divisible by $x_{\pi^{-1}(0)}$, and as it is symmetric, by $x_0\cdots x_n$. This contradicts one of our assumptions.

• I don't even know what a symmetric basis (or an almost symmetric basis) is; but I do know that it was a strange move to go from $\sf ZF$ to $\sf ZFA$ back to $\sf ZF$. Especially since it seems to me that all you did was to add an amorphous set (which we can easily do using a Cohen forcing, so no appeals to choice are needed there). Jan 19, 2015 at 13:21
• (1) Is there anything unclear about the definition of almost symmetric I gave? (2) I could have used just ZFA for the ground model, if I were happy with ZFA in the constructed model. The original question is about ZF, not ZFA. (3) The set I’m adding is in particular amorphous, but as far as I can see, the property I’m using is much stronger, it pretty much forces $A$ to behave as if it were added by the exact model I’m using. (4) It’s perfectly possible that no choice is needed, but unfortunately I’m thoroughly unfamiliar with forcing over ground models without choice, so I cannot tell. Jan 19, 2015 at 14:39
• (1) I'll have to admit to have skipped over that part :-P (3) I don't see how, you took the first Fraenkel model, with the sets satisfying ZF and the addition hypothesis; there were no particular permutations or support structure chosen to ensure something, just the most basic example. (4) Well, the Cohen forcing is countable, so it admits all the choice-familiar structure (which include chain conditions and their consequences, choice function from dense sets, etc.) so it should work out just fine. Jan 19, 2015 at 15:01
• (3) Yes, the construction is the first Fraenkel model, but the set arising from Fraenkel’s model is not uniquely characterized by its being amorphous. There are various amorphous sets with various properties. What I need is roughly this. Let $F$ be the set of finite partial functions from $V_\omega(A)$ to $k$. Then, for every $B\subseteq F$, there is a finite subset $A_0\subseteq A$ such that any permutation of $A$ identical on $A_0$ extends to a permutation $\pi$ on $F$, identical on $k$, such that $\pi(B)=B$. This certainly does not follow just from $A$ being amorphous; to begin with, ... Jan 19, 2015 at 15:32
• ... $k$ itself could include an amorphous set without further information. Jan 19, 2015 at 15:33

No: if we just have ZF, then we can not construct a basis for every $k(X)$.

From a basis we could prove the axiom of choice for sets of pairs, but Cohen proved that axiom independent of ZF in the same book where we proved independence for the usual AC (Set Theory and the Continuum Hypothesis, p. 142.)

[UPDATE: This all depends on the meaning of "every $k(X)$ has a basis", roughly either: $$\forall k\, \forall X\, \exists B\,\, \exists f:V \rightarrow \{(k_i),(b_i)\}\,\forall v \,\,v=\sum_{i=1}^n k_i b_i$$ or: $$\forall k\, \forall X\, \exists B\,\, \forall v \, \exists k_1,\ldots,k_n, \exists b_1,\ldots b_n\,\, v = \sum_{i=1}^n k_i b_i$$ The proof goes through under the first interpretation, but not the second.]

Here is some intuition for the proof below. A basis of $k(X)$, as standardly defined, gives any element of $k(X)$ as a finite sum of elements of $k$ times elements of the basis, which is to say a sum indexed by some $1...n$, which is to say an ordered sum. So if $x$ and $y$ are elements of the basis, then we can choose between them by looking at the expression for $x+y$ in terms of the basis, and whether $x$ or $y$ appears first in that expression. Even if $x$ and $y$ are not elements of the basis, we can still look at the expression for $x+y$ to see if it starts more like $x$ or more like $y$.

Proof of AC for pairs from the existence of a basis: Let $k$ be an ordered field, and suppose we have a basis for $k(X)$. We define a function $f:X\times X \rightarrow X$, where $f(x,y)$ is determined as follows:

Suppose $x,y$ are in $X$. Write $x+y$ in terms of the basis for $k(X)$ as $\sum_{i=1}^m c_i v_i$. Write $x$ in terms of the basis, as $\sum_{i=1}^n a_i v_i$, where some of the initial $a_i$ may be 0 and $n$ may be larger than $m$ if $x$ needs more basis elements. Now we can write $x=\sum_{i=1}^n a_i v_i,\, y=\sum_{i=1}^n b_i v_i,\, x+y=\sum_{i=1}^n c_i v_i$.

For some $i$, we may have $c_i = (a_i+b_i)\,/\,2$, and this is true for all $i>m$. If that is true for all $i$ then $x+y=(x+y)\,/\,2$, so $x+y=0$, which is impossible. So find the first $i$ for which $c_i$ is not $(a_i+b_i)\,/\,2$. If $c_i$ is closer to $a_i$ then let $f(x,y)=x$, otherwise let $f(x,y)=y$.

Now $f(y,x)=f(x,y)$. So therefore $f$ defines a choice function on the unordered pair $\{x,y\}$, QED.

• As standardly defined, a basis $B$ gives any element of $k(X)$ as a linear combination of elements of the basis: that is, a sum $\sum_{b\in B}a_bb$ where $a_b\in k$, and all but finitely many $a_b$ are $0$. This does not impose any order on the sum. Jan 13, 2015 at 13:38
• I see that while I was considering my comment, @EmilJeřábek said pretty much the same thing. Yes, the finite set of basis elements $v_i$ for each pair $\{x,y\}$ can be put in bijection with $\{1,\dots,n\}$ for some $n$, but to define the function $f$, you need to choose such a bijection for each pair $\{x,y\}$, and it's not clear how to do this without AC, unless the whole basis has a total order. Jan 13, 2015 at 14:02
• Matt, you need to argue that the outcome of the decision is the same regardless of how the finite sums are ordered. Otherwise, you are choosing such an ordering for each pair $x,y$! Jan 13, 2015 at 14:03
• Reading Matt's answer more carefully, I think he's right if you accept his definition of "basis": i.e., that the basis "gives" an ordered linear combination expressing each vector, rather than just that for every vector there is such an expression. Of course, with AC there's no difference, but where I disagree is whether his definition is "standard", although I admit the distinction hadn't previously occurred to me. Jan 13, 2015 at 14:57
• By this definition of "basis", the set of formal linear combinations of elements of a set $B$ does not have $B$ as a basis unless there is a choice function for finite subsets of $B$! Jan 13, 2015 at 18:07