Hallo, in the PS to his mail on duality, John Baez wrote:
Briefly, while the existence of an algebraic closure of Q can be shown without choice, it uniqueness-up-to-isomorphism seems to require choice. Also, while arithmetic operations in Qbar are computable, they seem to present interesting challenges.
it would look interesting to me to show that uniqueness up to isomorphism requires some kind of choice, e.g. by proving that it implies some choice principle. I started thinking about this and came to the following observation: Let K be the field obtained from Q by adjoining all square roots of (positive) primes or - equivalently - of all positive rational numbers. Then an algebraic closureof K is obviously the same as an algebraic closure of Q - even without choice. Now consider an arbitrary sequence of two element sets S(n), w.l.o.g. pairwise disjoint, and let S be their union. Now consider the polynomial ring Q(S) over Q in variables x(s) for all s in S. For each natural number n let p(n) be the n-th prime and consider the poynomials f_n:=x(s)+x(t) and g_n:=x(s)x(t)+p(n) in Q(S) where S(n) consists of the two elements s and t. Now let K' be the factor ring obtained from Q(S) by dividing out all f_n and g_n. If we have a choice function which assigns to each n an element s(n) in S(N), then there is a unique isomorphism from K' to K that maps each s(n) to the (positive) square root of p(n). Conversely, if we have an arbitrary isomorphism j from K' to K, we get a choice function which chooses for the each n unique s(n) in S(n) with j(n)>0. Thus existence of an isomorphism is equivalent to existence of a choice function. If the existence of an algebraic closure of K' could be shown without choice, then an isomorphism fom this algebraic closure to the set of algebraic complex numbers would restrict to an isomorphism between K and K' and thus render a chioce function for the S(n). Thus the uniqueness-up-to-isomorphism would imply choice for countable families of two-element sets. Maybe refinement oft his argument could even be used to get stronger choice principles. Greetings Reinhard Boerger
Hallo, in the PS to his mail on duality, John Baez wrote:
Briefly, while the existence of an algebraic closure of Q can be shown without choice, it uniqueness-up-to-isomorphism seems to require choice. Also, while arithmetic operations in Qbar are computable, they seem to present interesting challenges.
it would look interesting to me to show that uniqueness up to isomorphism requires some kind of choice, e.g. by proving that it implies some choice principle. I started thinking about this and came to the following observation: Let K be the field obtained from Q by adjoining all square roots of (positive) primes or - equivalently - of all positive rational numbers. Then an algebraic closureof K is obviously the same as an algebraic closure of Q - even without choice. Now consider an arbitrary sequence of two element sets S(n), w.l.o.g. pairwise disjoint, and let S be their union. Now consider the polynomial ring Q(S) over Q in variables x(s) for all s in S. For each natural number n let p(n) be the n-th prime and consider the poynomials f_n:=x(s)+x(t) and g_n:=x(s)x(t)+p(n) in Q(S) where S(n) consists of the two elements s and t. Now let K' be the factor ring obtained from Q(S) by dividing out all f_n and g_n. If we have a choice function which assigns to each n an element s(n) in S(N), then there is a unique isomorphism from K' to K that maps each s(n) to the (positive) square root of p(n). Conversely, if we have an arbitrary isomorphism j from K' to K, we get a choice function which chooses for the each n unique s(n) in S(n) with j(n)>0. Thus existence of an isomorphism is equivalent to existence of a choice function. If the existence of an algebraic closure of K' could be shown without choice, then an isomorphism fom this algebraic closure to the set of algebraic complex numbers would restrict to an isomorphism between K and K' and thus render a chioce function for the S(n). Thus the uniqueness-up-to-isomorphism would imply choice for countable families of two-element sets. Maybe refinement oft his argument could even be used to get stronger choice principles. Greetings Reinhard Boerger
Andrej Bauer wrote:
Reinhard Boerger wrote:
For each natural number n let p(n) be the n-th prime and consider the poynomials f_n:=x(s)+x(t) and g_n:=x(s)x(t)+p(n) in Q(S)
What precisely is the status of the expressions "x(s)+x(t)" and "x(s)x(t)" here? It is not clear to me that, given a two-element set which possibly cannot be ordered, we can form a sum or a product indexed by the set. I am afraid you're covertly ordering the two element set when you name its elements s and t, then form the sum x(s)+x(t). After all, a polynomial in Q[S] is going to be an (equivalence class of) sequence of pairs (coefficient, monomial). So if we could form x(s)+x(t) we could (perhaps) also order s and t by looking at the sequence which represents x(s)+x(t). Am I raising any doubts in your mind? I think some details need to be worked out here.
You are right; without choice we should be careful, and several classically equal things become distinct. I am used to the following way of defining the polynomial ring over a ring A in variables x(s) for all s from a given set S: Monomials are maps from S to the set of nonnegative integers, which map all but finitely many elements to 0. The images under this map are considered as exponents, and monomials are multiplied by adding the exponents, and x(s) is the monomial that maps s to 1 and all other elements to 0. Then x(s)x(t) is literally the same as x(t)x(s). Analogously, we can define polynomials as maps from the set of all monomials to A, which are 0 almost every where; the images are interpreted as coefficients. Then we also have x(s)+x(t)=x(t)+x(s). However, also another definition should turm the polynomial ring into a commutative rings; so the elements could also be defined as equivalence classes of (first-order) terms. The point is that x(s)x(t) should bet taken as an element of the (commutative) polynomial ring, not as a term; the terms x(s)x(t)and x(t)x(s) are indeed different. The algebraic closure of Q (or of a finite field) can be constructed by successively adding zeros of polynomials. Since the set of all polynomials can be numbered, an isomorphism between two different algebraic closures can be found, if on each step we find a bijection between the finte sets of zeros of a given polynomials in both closures. This choice usually depends on the privious choices; so countable dependent choice in finite sets (or König's Lemma) should render the desired isomorphism. On the other hand, the situation is very specific, I do not see how König's Lemma should follow from the existence of isomorphism between algebraic closures of Q. So I considered an easier case: The choices of square roots of different primes are independent. So the isomorphism between K and K' in my example can be obtained uniquely if for every prime you have bijectin between the set of the two square roots of a prime p in K and the set of the square roots of p in K'. ButK is ordered by construction; so you obtain the bijection if fir each p you choose which one of the two square roots of p shall be mapped to the positive square root in K': If you have the isomorphism, you get an ordering of K' and therefore a choice of positive square roots. So had to build the field K' for a given sequence of two-element sets without using a choice for these sets. Of course the result is not satifactory; it was just my first idea when I read John Baez' mail. Since there are also irreducible polynomials of degrees >2, I think that the sock axiom (i.e. countable choise for sequences of two-element sets, i.e. choosing a left one for countably many pairs of symmetric socks) should not imply the uniqueness of the algebraic closure of Q up to isomorphism. In order to getthe converse, we should need a way to extend an isomporphism between K and K' to an isomorphism between algebraic closures without using choice again. Greetings Reinhard
Andrej Bauer wrote:
Reinhard Boerger wrote:
For each natural number n let p(n) be the n-th prime and consider the poynomials f_n:=x(s)+x(t) and g_n:=x(s)x(t)+p(n) in Q(S)
What precisely is the status of the expressions "x(s)+x(t)" and "x(s)x(t)" here? It is not clear to me that, given a two-element set which possibly cannot be ordered, we can form a sum or a product indexed by the set. I am afraid you're covertly ordering the two element set when you name its elements s and t, then form the sum x(s)+x(t). After all, a polynomial in Q[S] is going to be an (equivalence class of) sequence of pairs (coefficient, monomial). So if we could form x(s)+x(t) we could (perhaps) also order s and t by looking at the sequence which represents x(s)+x(t). Am I raising any doubts in your mind? I think some details need to be worked out here.
You are right; without choice we should be careful, and several classically equal things become distinct. I am used to the following way of defining the polynomial ring over a ring A in variables x(s) for all s from a given set S: Monomials are maps from S to the set of nonnegative integers, which map all but finitely many elements to 0. The images under this map are considered as exponents, and monomials are multiplied by adding the exponents, and x(s) is the monomial that maps s to 1 and all other elements to 0. Then x(s)x(t) is literally the same as x(t)x(s). Analogously, we can define polynomials as maps from the set of all monomials to A, which are 0 almost every where; the images are interpreted as coefficients. Then we also have x(s)+x(t)=x(t)+x(s). However, also another definition should turm the polynomial ring into a commutative rings; so the elements could also be defined as equivalence classes of (first-order) terms. The point is that x(s)x(t) should bet taken as an element of the (commutative) polynomial ring, not as a term; the terms x(s)x(t)and x(t)x(s) are indeed different. The algebraic closure of Q (or of a finite field) can be constructed by successively adding zeros of polynomials. Since the set of all polynomials can be numbered, an isomorphism between two different algebraic closures can be found, if on each step we find a bijection between the finte sets of zeros of a given polynomials in both closures. This choice usually depends on the privious choices; so countable dependent choice in finite sets (or König's Lemma) should render the desired isomorphism. On the other hand, the situation is very specific, I do not see how König's Lemma should follow from the existence of isomorphism between algebraic closures of Q. So I considered an easier case: The choices of square roots of different primes are independent. So the isomorphism between K and K' in my example can be obtained uniquely if for every prime you have bijectin between the set of the two square roots of a prime p in K and the set of the square roots of p in K'. ButK is ordered by construction; so you obtain the bijection if fir each p you choose which one of the two square roots of p shall be mapped to the positive square root in K': If you have the isomorphism, you get an ordering of K' and therefore a choice of positive square roots. So had to build the field K' for a given sequence of two-element sets without using a choice for these sets. Of course the result is not satifactory; it was just my first idea when I read John Baez' mail. Since there are also irreducible polynomials of degrees >2, I think that the sock axiom (i.e. countable choise for sequences of two-element sets, i.e. choosing a left one for countably many pairs of symmetric socks) should not imply the uniqueness of the algebraic closure of Q up to isomorphism. In order to getthe converse, we should need a way to extend an isomporphism between K and K' to an isomorphism between algebraic closures without using choice again. Greetings Reinhard
participants (1)
-
Reinhard Boerger