R Some algebraic equivalent forms of ⊆ L Silvia Steila Abstract We study Σ1 definable counterparts for some algebraic equivalent forms of the 2 Continuum Hypothesis. All turn out to be equivalent to “all reals are constructible”. 1 Introduction 6 1 0 Sierpinski showed that the Continuum Hypothesis (CH) holds if and only if there are sets 2 A,B ⊆ R2 such that A∪B = R2 and for any a,b ∈ R the sections A = {y : (a,y) ∈ A} a n and Bb = {x : (x,b) ∈ B} are countable [9]. In [10, 11] Törnquist and Weiss studied many a Σ1 definable versions of some equivalent forms of CH which happen to be equivalent to J 2 “all reals are constructible”. For instance, they proved the Σ1 counterpart of Sierpinski’s 8 2 1 equivalence: R ⊆ L if and only if there are Σ12 sets A,B ⊆ R2 such that A1∪A2 = R2 and for any a,b ∈ R all sections A = {y : (a,y) ∈ A} and Bb = {x : (x,b) ∈ B} are countable. a ] O We follow their scheme to get some algebraic forms of R ⊆ L. While Törnquist and L Weiss considered Σ2 statements of the form “there exist finitely many objects such that 1 . somethinghappens”,thefirstalgebraicstatementsweanalyze,namelytheΣ1 counterparts h 2 t ofErdősandKakutani’sequivalence[1]andofZoli’sequivalence[12], requiretheexistence a of countably many objects. m [ Theorem 1.1. The following are equivalent: 1 1. R ⊆ L; v 3 2. there is a countable partition of R into Σ1-uniformly definable subsets consisting only 3 2 4 of rationally independent numbers; 4 0 3. the set of all transcendental reals is the union of countably many uniformly Σ1 de- 2 . 1 finable algebraically independent subsets. 0 6 As side results, the proof we present for the Σ1 definable versions provides a general- 2 1 ization of both the equivalences by Erdős-Kakutani and Zoli, where CH and “countably : v many” in the original theorems are replaced by 2ℵ0 ≤ κ+ and “κ-many”. i X Then we study the Σ1 version of polynomial avoidance and Schmerl’s results [8], by 2 r introducing a Σ1 version of m-avoidance, for m ∈ ω. As a corollary we obtain the Σ1 2 2 a counterpart of a theorem by Erdős and Komjáth [2]: Theorem 1.2. R ⊆ L if and only if there exists a Σ1 coloring of the plane in countably 2 many colors with no monochromatic right-angled triangle. Plan of the paper. The main results are organized in three sections. In Section 3 we prove the first part of Theorem 1.1 (i.e. (1) iff (2)) and in Section 4 we prove the second part of Theorem 1.1 (i.e. (1) iff (3)). Schmerl’s results and Theorem 1.2 are shown in Section 5. Each section starts with a short introduction and a generalization of the classical result, before presenting the definable counterpart. 1 2 Preliminaries A set is Σ1 if there exists a Σ1 predicate which defines it, and a function is Σ1 if its graph 2 2 2 is. A set is ∆1 if both it and its complement are Σ1. Observe that all notions are intended 2 2 lightface. For details we refer to [6]. Definition 2.1. A∆1 well-ordering≺isstrong ifithaslengthω andifforanyP ⊆ R×R 2 1 which is Σ1, 2 ∀z ≺ yP(x,z) is Σ1 as well. 2 Forshortwedenotex = {z : z ≺ x}. Givena∆1 strongwell-ordering≺,P ⊆ R<ω×R ≺ 2 Σ1 and x,y ∈ R, ∀s ∈ (x )<ωP(s,y) is Σ1. The existence of a ∆1 strong well-ordering of 2 ≺ 2 2 R is equivalent to requiring that the initial segment relation IS ⊆ R×R≤ω defined by IS(x,y) ⇐⇒ ∀z(z ≺ x ⇐⇒ ∃n(y(n) = z))∧∀i,j(y(i) = y(j) =⇒ i = j), is ∆1. We also use the function IS∗ : R → R≤ω which defines the initial segment of a given 2 real: IS∗(x) = v ⇐⇒ IS(x,v)∧(∀w ≺∗ v)¬IS(x,w). where ≺∗ is the product order in R≤ω induced by ≺. If R ⊆ L then there exists a ∆1 2 strong well-ordering of reals which is the usual well-ordering of R in L (see e.g. [3]). Forshort,letS beanequivalentformofCH.AsshownbyTörnquistandWeiss,proving that CH implies S can often be directly made into a proof of the effective implication, using the ∆1 strong well-ordering of reals. 2 Vice versa, from a proof of “S implies CH” we cannot usually extract a proof of the effective implication. To this end, we need some properties of L, mainly a corollary of a theorem by Mansfield and Solovay: if a Σ1 set contains a non-constructible real then 2 it is uncountable. This result does not explicitly appear in this paper, since the use of the perfect set property is hidden in the proof of the Σ1 version of two partition results, 2 proved by Törnquist and Weiss, that we are going to apply. Both are Σ1 counterparts of 2 partition results by Komjáth and Totik [4]. Proposition 2.2 (Komjáth, Totik). 1. Let κ be an infinite cardinal, |A| = κ+, |B| = (κ+)+, and k ∈ N. If f : A×B → κ, then there exist A0 ⊆ A, B0 ⊆ B, |A0| = |B0| = k such that A0×B0 is monochromatic. 2. If ¬CH, then for any coloring g : R → ω there are distinct x ,x ,x ,x ∈ R of 00 01 10 11 the same color such that x +x = x +x . 00 11 01 10 Proposition 2.3 (Törnquist, Weiss). 1. There is a non-constructible real if and only if for any x ∈ R∩L, for any Σ1(x) 2 coloringf : R×R → ω andforanyk ∈ ω thereareC, D ⊆ Rsuchthat|C| = |D| = k and f (cid:22) C ×D is monochromatic. 2. Thereisanon-constructiblerealifandonlyifforanyΣ1 coloringg : R → ω thereare 2 four distinct x ,x ,x ,x ∈ R of the same color such that x +x = x +x . 00 01 10 11 00 11 01 10 We mainly work in R, but sometimes we also work in different recursively presented Polish spaces, as R≤ω. This is not a problem in our setting, since between any two recursively presented Polish spaces there is a ∆1 bijection. 1 2 3 Rationally independent sets In[1]ErdősandKakutaniprovedthereisacloseconnectionbetweenCHandtheexistence ofsomespecialrationallyindependentsubsetsofreals. WeproveageneralizationofErdős and Kakutani’s equivalence. Recall that a set X ⊆ R is rationally independent if for any n ∈ N, x ,...,x ∈ X and for any q ,...,q ∈ Q\{0} we have: 0 n−1 0 n−1 n−1 X q x 6= 0. i i i=0 First of all, following Komjáth and Totik, we get a straightforward generalization of Proposition 2.2.2. Proposition 3.1. If 2ℵ0 ≥ (κ+)+, then for any coloring g : R → κ there are distinct x ,x ,x ,x ∈ R of the same color such that x +x = x +x . 00 01 10 11 00 11 01 10 Proof. Assume that 2ℵ0 ≥ (κ+)+ and consider any g : R → κ. Take an injection i : (κ+)+ ,→ R and define i0 : (κ+)+ ,→ R such that ran(i0) is rationally independent. Put i0(α) = i(β) for β = µγ ∈ (κ+)+(∀s ∈ (Q \ {0})<ω∀t ∈ γ<ω(dom(s) = dom(t) =⇒ Pdom(s)s(j)i(t(j)) 6= i(γ))). Let j=0 n o n o a : α < κ+ ∪ b : β < (κ+)+ α β be a rationally independent set, and define the following coloring: f : κ+×(κ+)+ −→ κ (α,β) 7−→ g(a +b ) α β Thanks to Proposition 2.2.1 there exist α ,α ∈ κ+ and β ,β ∈ (κ+)+ such that 0 1 0 1 {α ,α } × {β ,β } is monochromatic. Define x = α + β for any i,j ∈ 2. They 0 1 0 1 ij i j are distinct and they satisfy x +x = x +x . 00 11 01 10 Recall that H ⊆ R is a Hamel basis if both H is rationally independent and H is a basis of R over Q. Theorem3.2. Wehave2ℵ0 ≤ κ+ ifandonlyifR\{0}canbecoveredbyκ-manyrationally independent sets. Proof. “⇒”. Assume that 2ℵ0 ≤ κ+, and let H be a Hamel basis for R. Take an injection f : R ,→ κ+ and define the order(cid:67)of length≤κ+ ofRbyx (cid:67) y if and only iff(x) < f(y). For any natural number n > 0 and for any s ∈ (Q\{0})n, define ( n−1 !) s·Hn = x : ∃h (cid:67) ··· (cid:67) h ∈ H x = Xs(i)h . (1) 0 n−1 i i=0 First notice that as H is a Hamel basis, R \ {0} is covered by all sets s · Hn for s ∈ (Q\{0})n. So it suffices to show the result for all sets s·Hn. From now on fix n ∈ N and s ∈ (Q\{0})n. Note if n = 1 as H is rationally independent the result is trivial, so assume that n > 1. Given x ∈ s·Hn, define last(x) as the greatest element of H which appears in (1) (i.e. h ). For any h ∈ H define n−1 s·(Hn−1h) = {x ∈ s·Hn : last(x) = h}. 3 Given h ∈ H let γ = |s·(Hn−1h)|. Observe that γ ≤ κ since |H| = κ+. Therefore for h h any h ∈ H we can fix an enumeration: n o s·(Hn−1h) = xh : α < γ . α h Finally, for any α < κ let S be the set of α-th elements of any s·(Hn−1h) for h ∈ H; s,α i.e. n o S = xh : h ∈ H ∧α < γ . s,α α h Therefore we have R\{0} = [(cid:8)S : s ∈ (Q\{0})<ω ∧α < κ(cid:9). s,α We claim that for any α < κ, S is rationally independent. Indeed, assume by contra- s,α diction that k X p x = 0, (2) i i i=0 where for any i ∈ k+1: • x ∈ S ; i s,α • for any j ∈ k+1, x 6= x ; i j • p is a not null integer. i By construction, for any two distinct elements x ,x ∈ S , last(x ) 6= last(x ). Then 1 2 s,α 1 2 there would exist an integer i ∈ k+1 for which last(x ) > last(x ) for any i ∈ k+1\{i }. 0 i0 i 0 Hence in the expansion (1) of all x , last(x ) would appear only once, which is impossible i i0 because of (2) and H rationally independent. “⇐.” Let R \ {0} = S{S : α ∈ κ}, where each S is a rationally independent set. α α Assume by contradiction that 2ℵ0 > κ+ and define g : R → κ such that g(0) = 0 and for any x ∈ R\{0} g(x) = α+1 ⇐⇒ x ∈ S ∧∀β < α(x ∈/ S ). α β ApplyingProposition3.1wegetx , x , x , x ∈ R\{0}suchthatx , x , x , x ∈ 00 10 01 11 00 10 01 11 S for some α ∈ κ which are rationally dependent. Contradiction. α TheproofofthefirstimplicationfollowstheonebyErdősandKakutani’sresult, while the argument for the vice versa, as far as we know, is new. The original proof uses a tree argument, which cannot be easily adapted to the Σ1 version. 2 Remark 3.3. Note that in the proof of Theorem 3.2 the subsets S , for s ∈ (Q\{0})<ω s,α and α ∈ κ, are disjoint. 3.1 Definable counterpart We prove that R ⊆ L holds if and only if R\{0} can be decomposed in countably many rationally independent subsets of reals which are uniformly definable by a Σ1 predicate. 2 The proof follows very closely the one of Theorem 3.2: we need only to check that if there is a ∆1-strong well-ordering of R then the sets provided by Erdős and Kakutani’s 2 argument are uniformly Σ1. For the opposite implication we apply Proposition 2.3.2, the 2 Σ1 counterpart of Proposition 3.1. 2 As a first step we considered a Hamel basis for R. In [5] Miller proved that if V = L then there is a Π1 Hamel basis. For our goal it is sufficient to provide a ∆1 one, under 1 2 the condition R ⊆ L. The proof is straightforward and it should be well-known. However, since we have not found any reference for this proof, we show the argument. 4 Lemma 3.4. If R ⊆ L then there exists a ∆1 Hamel basis for R. 2 Proof. Let ≺ be a ∆1-strong well-ordering of R. Define 2 dom(s) h ∈ H ⇐⇒ ∀s ∈ (h )<ω ∀t ∈ (Q\{0})<ω(dom(s) = dom(t) =⇒ h 6= X t(i)s(i)). ≺ i=0 By definition H is rationally independent. We prove that H generates R. Take x ∈ R and prove that there exist n ∈ N, h ,...,h ∈ H and q ,...,q ∈ Q such that 0 n−1 0 n−1 x = Pn−1q h . Proceed by induction on ≺. If x has no ≺-predecessors then it belongs i=0 i i to H. Assume that the assertion holds for any y such that y ≺ x. If x ∈ H we are done. Otherwise there exist some n ∈ N, x ≺ ··· ≺ x ≺ x and q ,...,q ∈ Q\{0} such 0 n−1 0 n−1 that x = Pn−1q x . As all x are generated by H, so is x. i=0 i i i Theorem 3.5. R ⊆ L if and only if there is a countable decomposition of R\{0} into Σ1-uniformly definable subsets consisting only of rationally independent numbers. 2 Proof. “⇒”. Assume that R ⊆ L, and let H be a ∆1 Hamel basis for R, which exists 2 thanks to Lemma 3.4. For any natural number n, for any sequence s ∈ (Q\{0})n and for any h ∈ H define s·Hn and s·(Hn−1h) as in the proof of Theorem 3.2. Then R\{0} = Gns·Hn−1 : n ∈ ω,s ∈ (Q\{0})no. AsobservedinRemark3.3thisisadisjointunion. Fixanaturalnumbernandasequence s ∈ (Q\{0})n. We want to define countably many disjoint subsets of s·Hn such that each one contains at most one element of s·(Hn−1h) for any h ∈ H. To this end, given an increasingfinitesequenceofnaturalnumberst ∈ Nn−1,defineS tobethesubsetofs·Hn s,t which consists of elements of the form x = Pn−1s(i)h for some h ≺ ··· ≺ h ∈ H i=0 i 0 n−1 such that for any i ∈ n−1, h is the t(i)-th predecessor of h . Therefore i n−1 S = {x : ∃h ∈ H∃v ∈ R≤ω(IS∗(h) = v∧∀i ∈ n−1(v(t(i)) ∈ H) s,t n−2 X ∧x = s(i)v(t(i))+s(n−1)h)}. i=0 By construction last(x ) 6= last(x ) for any x , x ∈ S such that x 6= x . Moreover 1 2 1 2 s,t 1 2 we have s · Hn = F(cid:8)S : t ∈ Nn−1(cid:9). The sets S , where s ∈ Q<ω and t ∈ N<ω, are s,t s,t uniformly definable by the following Σ1 formula. 2 ψ(x,n,s,t) ⇐⇒ s ∈ Q<ω ∧t ∈ N<ω ∧dom(s) = n∧dom(t) = n−1 h ∧∀i ∈ n−2(t(i) < t(i+1))∧∃h∃v ∈ R≤ω h ∈ H ∧IS∗(h) = v n−2 X i ∧∀i ∈ n−1(v(t(i)) ∈ H)∧x = s(i)v(t(i))+s(n−1)h . i=0 Notice to conclude that rationally independence of the set S holds with the same s,t argument of Theorem 3.2. “⇐”. Let R \ {0} = F{S : i ∈ ω}, where S are uniformly Σ1 definable rationally i i 2 independent sets. Let define g : R → ω such that g(0) = 0 and for any x ∈ R\{0} g(x) = i+1 ⇐⇒ x ∈ S . i Since by hypothesis the S are uniformly definable by a Σ1 formula, g is Σ1. Suppose by i 2 2 contradictionthatR (cid:42) L,thenbyapplyingProposition2.3.2thereexistx ,x ,x ,x ∈ 00 01 10 11 R\{0} such that x ,x ,x ,x ∈ S for some i ∈ ω and x +x = x +x . So there 00 01 10 11 i 00 11 01 10 are four distinct elements of S which are rationally dependent. Contradiction. i 5 4 Algebraically independent sets Zoli in [12] proved a connection between CH and the existence of a decomposition of transcendental reals in algebraically independent sets. We provide a generalization of Zoli’s result. Given two fields K ⊆ K , we say that x ∈ K is algebraic over K if there exists 1 2 2 1 a polynomial p in K [X] (not null) such that p(x) = 0. If x ∈ K is not algebraic over 1 2 K , then it is called transcendental over K . We denote by alg K the subfield of K 1 1 K2 1 2 consisting of algebraic elements over K . Given x ∈ K , K (x) is the field extension 1 2 1 generated by x. S ⊆ K is algebraically dependent over K if there exist x ,...,x ∈ S 2 1 0 n such that x is algebraic over K (x ,...,x ). A transcendence basis T is a subset of n 1 0 n−1 reals which is algebraically independent over Q and maximal. Lemma 4.1 (Folklore). Let K ⊆ K be a field extension. 1 2 • Let S ⊆ K . If x ∈ alg K (S)\alg K , then S is algebraically independent over 2 K2 1 K2 1 K (x). 1 • Let T be a transcendence basis for K over K . To each x ∈ K there corresponds a 2 1 2 unique minimal (finite) subset S of T such that x ∈ alg K (S). K2 1 For a proof we refer to [12]. Theorem 4.2. We have 2ℵ0 ≤ κ+ if and only if the set of all transcendental reals is union of κ-many algebraically independent sets. Proof. “⇒”. Assume that 2ℵ0 ≤ κ+, and let T be a transcendence basis. Fix f : R ,→ κ+ and define a well ordering of length κ+ of reals: x (cid:67) y if and only if f(x) < f(y). By Lemma 4.1 each x ∈ R \ alg (Q) corresponds to a unique n(x) ∈ ω and a sequence R t (x) < ··· < t (x) ∈ T such that 0 n(x) x ∈ alg Q(cid:0)t (x),...,t (x)(cid:1)\ [ alg Q(T \{t (x)}). (3) R 0 n(x) R i i∈n(x)+1 Foranyn ∈ ω,definethesetT ofalltranscendentalnumbersforwhichthecardinality n of the minimum subset provided by Lemma 4.1 is n+1; i.e. T = {x ∈ R\alg (Q) : n(x) = n}. n R n o Thus R\alg (Q) = S T : n ∈ ω . For any n ∈ N, t ∈ R define T as: R n n,t T = {x : x ∈ T ∧t (x) = t}. n,t n n Notice that T has cardinality κ+ and therefore T has cardinality at most κ. Hence fix n,t an enumeration T = (cid:8)xn,t : α < κ(cid:9) and define n,t α S = {xn,t : n ∈ ω∧t ∈ T}, α α Observe that R\alg (Q) is covered by all sets S for α ∈ κ. In order to complete this R α proof we have to show that any set S is algebraically independent. Fix α ∈ κ in order to α prove that any x ,...,x ∈ S are algebraically independent. We prove it by induction 0 k−1 α over k. Assume that k = 0, then since S ⊆ R\alg (Q) we are done. Now assume that it α R holds for k and prove it for k+1. Therefore consider x ,...,x ∈ S . By construction, 0 k α for any two elements of S we have t (x) 6= t (y). Thus without loss of generality we α n n can assume that t (x ) > t (x ) for any i ∈ k. Assume by contradiction that there exists n k n i i ∈ k+1 such that x ∈ alg Q(x ,...,x ,x ,...,x ). There are two cases. i R 0 i−1 i+1 k 6 • If i = k. Therefore x ∈ alg Q(x ,...,x ) ⊆ alg Q({t (x ) : i ∈ n,j ∈ k}) k R 0 k−1 R i j ⊆ alg Q(T \{t (x )}). R n k This is a contradiction with (3). • Ifi 6= k. Byinductivehypothesistheset{x ,...,x }isalgebraicallyindependent, 0 k−1 therefore it must exist q ∈ Q[X ,...,X ]\Q[X ,...X ,X ,...,X ] 0 k 0 i−1 i+1 k−1 such that q(x ,...,x ) = 0. But this yields that x ∈ alg Q(x ,...,x ) and this 0 k k R 0 k−1 is impossible as proved in the previous case. “⇐”. Apply Theorem 3.2, since any algebraically independent subset is rationally independent. Note that the algebraically independent sets provided in the proofs from 2ℵ0 ≥ κ+ are disjoint. InTheorem4.2, asinZoli’soriginalargument, weprovedthatthetranscendental reals are a disjoint union of κ-many algebraically independent sets. However, since any algebraically independent set is contained in some transcendence basis, we obtain the following. Corollary 4.3. 2ℵ0 ≤ κ+ if and only if the set of all transcendental reals is union of κ-many transcendence bases for R. 4.1 Definable counterpart The first step we need to show that if all reals are constructible, then there is a ∆1 2 transcendence basis. Lemma 4.4. Assume that R ⊆ L. 1. For any y ,...,y ∈ R, alg Q(y ,...y ) is Σ1. 0 n R 0 n 1 2. There exists a ∆1 transcendence basis. 2 Proof. Let ≺ be a ∆1-strong well-ordering of R. 2 1. By definition x ∈ alg Q(y ,...,y ) if and only if R 0 n ∃(x ,...,x ) ∈ R<ω(x ,...,x ∈ Q(y ,...,y )∧x +x x+···+x xm = 0). 0 m 0 m 0 n 0 1 m The assertion follows by induction over n, since x ∈ Q(y ,...,y ) if and only if 0 n a +···+a yh ∃(a ,...,a ,b ,...,b ) ∈ Q(y ,...,y )<ω(x = 0 h n). 0 h 0 k 0 n−1 b +···+b yk 0 k n 2. Define x ∈ T ⇐⇒ x ∈ R\alg (Q)∧∀(x ,...,x ) ∈ (x )<ω(x ∈/ alg Q(x ,...,x )). R 0 n ≺ R 0 n We claim that T is a transcendence basis for R. T is algebraically independent by definition. Moreover R is algebraic over Q(T). Indeed we show that for any 7 x ∈ R \ alg (Q) there exist x ,...,x ∈ T such that x ∈ alg Q(x ,...,x ). By R 0 n R 0 n induction on ≺. Let x = min (R\alg (Q)), then by definition x ∈ T. Assume 0 ≺ R 0 that x ∈ R \ alg (Q) and that for any y ≺ x the assertion holds. We have two R possibilities: either x ∈ T or there exists some n ∈ N such that ∃x ,...,x ≺ 0 n x(x ∈ alg Q(x ,...,x )). Both in the first case and whether in the second one R 0 n x ,...,x ∈ T we have the assertion. Then assume that we are in the second case 0 n and x ,...,x ∈/ T. As all x are algebraic over T, then also x is. 0 n i Theorem 4.5. R ⊆ L if and only if the set of all transcendental reals is the disjoint union of countably many algebraically independent sets uniformly definable by a Σ1 predicate. 2 Proof. “⇒”. Assume that R ⊆ L, then by Lemma 4.4 there exists T which is a ∆1 2 transcendence basis. For any x ∈ R\alg (Q) and any n ∈ ω define n(x), t (x) and T R i n as in the proof of Theorem 4.2. Fix a natural number n. We define countably many disjoint subsets of T which contain at most one element of T for any t ∈ T. To this n n,t end fix t ,...,t ≺ t. For any x ∈ alg Q(t ,...,t ,t) there exists a polynomial p ∈ 0 n−1 R 0 n−1 Q[X ,...,X ,X] such that p(t ,...,t ,t,x) = 0. Thus for any p ∈ Q[X ,...,X ,X], 0 n 0 n−1 0 n t ∈ R and for any v ∈ Rn define T = {x : x ∈ S ∧∀i ∈ n(v(i) = t (x))∧t = t (x)∧p(t (x),...,t (x),x) = 0}. n,t,p,v n i n 0 n Observe that T is uniformly ∆1 definable by the following formula. n,t,p,v 2 ϕ(x,t,n,p,v) = x ∈/ alg (Q)∧dom(v) = n∧x ∈/ alg Q({v(j) : j ∈ n}) R R ∧∀i ∈ n(x ∈/ alg Q({v(j) : j ∈ n,j 6= i}∪{t}))∧p(v(0),...,v(n−1),t,x) = 0. R Up to now the sets T are not disjoint, since any x belongs to T for several n,t,p,v n,t,p,v polynomials p. However since p ∈ Q[X ,...,X ,X], it can be coded with a natural 0 n number by a ∆1 map m : Q<ω → N. Therefore we can define a ∆1 formula which provides 1 2 a partition of T , by choosing the polynomial with the minimal code: n ϕ∗(x,t,n,p,v) = ϕ(x,t,n,p,v) ∧ ∀q ∈ Q<ω(m(q) < m(p) =⇒ ¬ϕ(x,t,n,q,v)). Put T∗ = {x : ϕ∗(x,t,n,p,v)}. Since p(t ,...,t ,t,X) ∈ Q[X], it has finitely many n,t,p,v 0 n−1 roots. Givenarootx,letlbethenumberrootswhicharesmallerthanxwithrespectto≺. Hence there is a 1-1 correspondence between T and the set of tuples (t ,...,t ,p,l) n,t 0 n−1 for some t ,...,t ≺ t, p ∈ Q[X ,...,X ,X] and l ≤ deg(p(v(0),...,v(n−1),t,X)). 0 n−1 0 n Foranyn,l ∈ N,p ∈ Q[X ,...,X ,X]andforanyincreasingfinitesequenceofnatural 0 n numbers s ∈ N<ω define S = {x : ∃w ∈ R≤ω∃v ∈ Rn(IS∗(t (x)) = w∧∀i ∈ n(v(i) = w(s(i))) n,p,s,l n ∗ ∗ ∧x ∈ T ∧|{y : y ≺ x}∩T | = l)}, n,tn(x),p,v n,tn(x),p,v By construction x,y ∈ S and t (x) = t (y) yield x = y. Moreover S can be n,p,s,l n n n,p,s,l uniformly defined by the following Σ1 formula. 2 ψ(x,n,p,s,l) ⇐⇒ ∃t ∈ R∃w ∈ R≤ω∃v ∈ R<ω(IS∗(t) = w∧∀i ∈ n(w(s(i)) = v(i)) ∧ϕ(x,t,n,p,v)∧∃u ∈ R≤ω[IS∗(x) = u∧dom(u) ≥ l∧(∃s0 ∈ Nl (∀i ∈ l−1(s0(i) < s0(i+1))∧∀i ∈ lϕ(u(s0(i)),t,n,p,v))∧(dom(u) > l =⇒ ∀s0 ∈ Nl+1(∃i ∈ l(s0(i) ≥ s0(i+1))∨∃i ∈ l+1¬ϕ(u(s0(i)),t,n,p,v))))]. 8 We have R\alg (Q) = G(cid:8)S : n,l ∈ N,s ∈ N<ω,p ∈ Q[X ,...,X ,X](cid:9). R n,p,s,l 0 n In order to complete this proof we have to show that any set S is algebraically n,p,s,l independent. Since, by construction for any two elements x,y ∈ S , t (x) 6= t (y), the n,p,s,l n n argument is exactly the one shown in Theorem 4.2. “⇐”. Since any algebraically independent subset is rationally independent, the asser- tion follows by Theorem 3.5, In his work Zoli proved that CH holds if and only if the set of all transcendental reals is the disjoint union of countably many algebraically independent sets S . Corollary 4.3 i follows since if S is algebraically independent then we can define a transcendence basis i T which contains S as follows: i i x ∈ T ⇐⇒ x ∈ S ∨(x ∈/ alg Q(S )∧∀y ,...,y ≺ x(x ∈/ alg Q(S ∪{y ,...,y }))). i i R i 0 n R i 0 n However this basis is Π1 and up to now we did not find a Σ1 formula which defines it. 2 2 Therefore our definable version of Zoli’s result deal with algebraically independent sets and not with transcendence bases. 5 Polynomial avoidance We present some results by Schmerl [8] about polynomial avoidance and an equivalence by Erdős and Komjáth [2] in order to obtain the correspondent Σ1 definable counterparts. 2 We say that a polynomial p ∈ R[X ,...,X ] is a (k,n)-ary polynomial if every 0 k−1 X is a n-tuple of variables. Given a (k,n)-ary polynomial p(x ,...,x ), a coloring i 0 k−1 χ : Rn → ω avoids it if for any r ,...,r ∈ Rn distinct and monochromatic with respect 0 k−1 to χ, p(r ,...,r ) 6= 0. Moreover the polynomial p(x ,...,x ) is avoidable if there 0 k−1 0 k−1 exists a coloring which avoids it. Definition 5.1 (Schmerl). Let m ∈ ω and k ∈ ω\{0,1}. • A function α : A ×A ×···×A → B ×B ×···×B is coordinately induced 0 1 m−1 0 1 m−1 if for every i ∈ m there is a function α : A → B such that i i i α(a ,...,a ) = (α (a ),...,α (a )). 0 m−1 0 0 m−1 m−1 • Afunctiong : Am → B isone-one in each coordinate ifwhenevera ,...,a ,b ∈ A 0 m−1 and b 6= a for some i ∈ m, then i g(a ,...a ,a ,a ,...,a ) 6= g(a ,...,a ,b,a ,...a ). 0 i−1 i i+1 m−1 0 i−1 i+1 m−1 • Assume that p(x ,...,x ) is a (k,n)-ary polynomial. For each m ∈ ω we say 0 k−1 that p(x ,...,x ) is m-avoidable if for each definable function g : Rm → Rn 0 k−1 which is one-one in each coordinate and for distinct e ,...,e ∈ (0,1)m there is a 0 k−1 coordinately induced α : Rm → Rm such that p(gα(e ),...,gα(e )) 6= 0. 0 k−1 Instead of Rm we can use also (0,1)m, (a,b)m or any open m-box, since there is a ∆1 1 bijection between them. Theorem 5.2 (Schmerl). 1. If CH does not hold then every avoidable polynomial is 2-avoidable. 2. If CH holds then every 1-avoidable polynomial is avoidable. 9 5.1 Schmerl’s equivalences InfactthestatementsstudiedbySchmerlareequivalencesrespectivelywith¬CHandCH. To show it we need to recall Erdős-Komjáth’s equivalence. Erdős and Komjáth proved that CH holds if and only if the plane can be colored with countably many colors with no monochromatic right-angled triangle, where a right-angled triangle is monochromatic if its vertices are. Notation 5.3. Let p˜(x ,x ,x ) be the following (3,2)-ary polynomial: 0 1 2 p˜(x ,x ,x ) = kx −x k2+kx −x k2−kx −x k2. 0 1 2 1 0 2 0 1 2 Observe that given distinct a ,a ,a ∈ R2, p˜(a ,a ,a ) = 0 if and only if a , a and 0 1 2 0 1 2 0 1 a form a right-angled triangle. Hence 2 Theorem 5.4 (Erdős, Komjáth). CH holds if and only if p˜(x ,x ,x ) is avoidable. 0 1 2 In [8], Schmerl also proved that p˜(x ,x ,x ) is 1-avoidable and it is not 2-avoidable. 0 1 2 Since this result is crucial to prove our goal, let us recall the proof. Lemma 5.5 (Schmerl). The (3,2)-ary polynomial p˜(x ,x ,x ) is 1-avoidable and it is not 0 1 2 2-avoidable. Proof. First of all we prove that it is 1-avoidable. Indeed given g : R → R2 and e 6= e 6= 0 1 e ∈ R define α : R → R as follows: 2 α(x) = y ⇐⇒ (x = e ∧y = e ) ∨ (x 6= e ∧y = x). 2 1 2 Hence α(e ) = e , α(e ) = e and α(e ) = e , therefore g(α(e )) 6= g(α(e )) = g(α(e )) 0 0 1 1 2 1 0 1 2 since g is one-one in each coordinate. This yields p(g(α(e )),g(α(e )),g(α(e ))) 6= 0. 0 1 2 To prove that it is not 2-avoidable let g : R2 → R2 be the identity function and put e = (0,0), e = (1,0)ande = (0,1). Theyformaright-angledtriangle. Letα : R2 → R2 0 1 2 be any coordinately induced function, hence α(e ), α(e ) and α(e ) form a right-angled 0 1 2 triangle, eventually degenerate. So p˜(g(α(e )),g(α(e )),g(α(e ))) = p˜(α(e ),α(e ),α(e )) = 0. 0 1 2 0 1 2 Proposition 5.6. 1. If any avoidable polynomial is 2-avoidable then ¬CH holds. 2. If any 1-avoidable polynomial is avoidable then CH holds. Proof. 1. Assume that CH holds, then by Erdős and Komjáth’s equivalence p˜(x ,x ,x ) is 0 1 2 avoidable. Then, by hypothesis it is 2-avoidable. Contradiction by Lemma 5.5. 2. By Lemma 5.5, p˜(x ,x ,x ) is 1-avoidable. Then, by hypothesis, it is avoidable. 0 1 2 Therefore, again by Erdős-Komjáth equivalence, CH holds. 10