Skip to main content
clarified and qualified
Source Link
user44143
user44143

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.

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.)

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.

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.

Source Link
user44143
user44143

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.)

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.