{'fraction_non_alphanumeric': 0.07691528684996708, 'fraction_numerical': 0.010228365993214847, 'mean_word_length': 3.1231732776617953, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Canonization of analytic equivalences on the Carlson-Simpson forcing

We prove a canonization result for the Carlson-Simpson forcing in the spirit of \cite{KSZ}. We generalize the weak form of the Carlson-Simpson theorem (\cite{CaSi}) dealing with partitions without free blocks: instead of dealing with finite Borel (resp. Baire-property) colorings we deal with (uncountable) colorings such that the corresponding equivalence relation (two partitions are equivalent if they are colored by the same color) is analytic.


Introduction
In [1], Timothy J. Carlson and Stephen G. Simpson prove a strong combinatorial theorem concerning finite partitions of natural numbers that is in some sense dual to the classical Ramsey theorem. It is usually called the Dual Ramsey theorem or the Carlson-Simpson theorem. In this paper we connect this combinatorial result with the research program from [4] and [3]. We define a forcing notion, resp. a σ-ideal on a certain Polish space, that corresponds to the object studied in the Dual Ramsey theorem and prove a canonization result for this σ-ideal. More specifically, we identify a finite set of equivalence relations that are in the spectrum of this ideal and any other analytic equivalence relation canonizes to one of them. This result can be viewed as a generalization of the weaker form of the Carlson-Simpson theorem dealing with partitions of ω without free blocks (Lemma 2.3 in [1]).
Before defining necessary notions, we can state one immediate interesting consequence of our result.
Theorem 0.1. Let E be any analytic equivalence relation on P(ω) (we identify elements of P(ω) with elements of 2 ω ). Then there exists an infinite sequence (A n ) n∈ω of pairwise disjoint non-empty subsets of ω (finite or infinite) such that either for any two different arbitrary unions of such sets (both containing A 0 though) they are E-equivalent, or for any two different arbitrary unions both containing A 0 they are E-inequivalent.

Preliminaries and basic notions
In order to state and motivate our results we present the general program of [3]: let X be a Polish space, I a σ-ideal on X and E ⊆ X 2 an analytic equivalence relation.
• We say that E is in the spectrum of I if there exists a Borel set B ∈ I + such that ∀C ∈ (I + ∩ Borel(B)) E ↾ C has the same complexity as E on the whole space, i.e. E ↾ C is Borel bireducible with E ↾ X. • On the other hand, I canonizes E to a relation F ≤ B E if for every Borel B ∈ I + there is some Borel C ∈ (I + ∩ Borel(B)) such that E ↾ C is bireducible with F . Now we introduce the original notation of Carlson and Simpson from [1] and state their theorem. Then we define the forcing notion, resp. the σ-ideal and state our result. Definition 1.1. Let A be a finite (at least two-element) alphabet. As in [1], by (ω) α A , where α ∈ (ω \ |A|) ∪ {ω}, we denote the set of all partitions of A ∪ ω into α pieces such that two different elements a = b ∈ A lie in two different pieces of such partitions. For any X ∈ (ω) α A , a piece containing some a ∈ A is called an a-block, a piece not containing any element of A is called a free block.
For Y ∈ (ω) β A and X ∈ (ω) α A , where β ≤ α, we say Y is coarser than X, Y X, if every block of X is contained in some block of Y . For any X ∈ (ω) α A by (X) β A , where β ≤ α, we denote the set {Y ∈ (ω) β A : Y X}.
. Let A be as before. Consider the set (ω) 0 A . We look at it as a set of all partitions of ω into |A| pieces indexed by A. There is a natural correspondence between (ω) 0 A and A ω . The latter carries a product topology if we consider A as a discrete space which is homeomorphic to the topology of the Cantor space. From now on we will not distinguish between these two sets and thus be able to speak about topological properties of (ω) 0 A . Definition 1.3 (Carlson-Simpson forcing/ideal). We shall consider ((ω) ω A , ) as a forcing notion. For X ∈ (ω) ω A we shall write [X] to denote the set (X) 0 A . Note that for any such X, [X] is a closed subset of (ω) 0 A (or A ω ).
Let I Cn ⊆ P(A ω ), where n denotes the cardinality of A, be the set of all Borel subsets of A ω that do not contain [X] for some X ∈ (ω) ω A . The following proposition gives some properties of I Cn .
We postpone the proof until we have proved the main theorem 2.1. The reason for that is that the first item of Proposition 1.4 will follow easily. We do not need any part of the proposition in the proof of the main theorem. However, let us mention that all items of Proposition 1.4 could be proved by a direct argument without applying the main theorem.
Let us state a restricted version of the Carlson-Simpson (Dual Ramsey) theorem for partitions without free blocks. For any X ∈ (ω) ω A and any finite partition [X] = C 0 ∪ . . . ∪ C n into pieces having the Baire property there exists Y ∈ (X) ω A and i ≤ n such that [Y ] ⊆ C i . We conclude this section by the following fact that will serve as a useful tool in the proof of the main theorem by forcing. Fact 1.6 (Analytic absoluteness; see [2] Theorem 25.4). Let a ∈ ω ω be a parameter and φ be a Σ 1 1 formula with free variables. Then φ(a) is absolute for all transitive models of a large enough fragment of set theory containing the parameter a.
In particular, if A ⊆ X is an analytic subset of a standard Borel space X, x ∈ X is arbitrary and M and N are two transitive models of set theory containing A, X (resp. codes for them) and x, then M |= x ∈ A iff N |= x ∈ A.

Canonization
Let A be a finite alphabet such that |A| = n ≥ 2. Let B be a partition of A. Then we can consider the following equivalence relation E B on A ω : for x, y ∈ A ω we set xE B y iff ∀n ∈ ω∀B ∈ B(x(n) ∈ B ⇔ y(n) ∈ B).
It is easy to check that E B is a closed equivalence relation that is in the spectrum of I Cn . For a finite alphabet A let P A denote the set of partitions of A. The main result says that these are the only analytic equivalences in the spectrum of I Cn . Every other analytic equivalence relation canonizes to one of them.
In particular, we have a total canonization for I C 2 .
for B a partition into singletons, and Remark 2.2. This is an "almost generalization" of Theorem 1.5 as this theorem can be viewed as a canonization result for equivalence relations having finitely many classes. We used the term "almost generalization" as the Theorem 1.5 holds for partitions into pieces having the Baire property whereas Theorem 2.1 generalizes only the case with analytic partitions. Definition 2.3. Let A be from the statement of the theorem. For any X ∈ (ω) α A and any a ∈ A, by X(a) we denote the elements of ω belonging to the a-block; i.e. {a} ∪ X(a) is the a-block of X. Similarly, for any n < α by X(n) we denote the elements of ω belonging to the n-th free block where the enumeration of free blocks is determined by their minimal elements.
Thus for instance, if X has two free blocks, Definition 2.4. Let us write A = {a 0 , . . . , a n−1 } and let X ∈ (ω) ω A be a condition and s ∈ n <ω a finite n-ary sequence. By X s we denote the condition Y ∈ (X) ω A for which for every i < n Y (a i ) = X(a i )∪ {X(k) : k < |s| ∧ s(k) = i} and for every m ∈ ω Y (m) = X(m + |s|).
Note that whenever for some X and s there is From that reason for a condition X and a finite n-ary sequence s when we write Z s ≤ X s , then by Z we mean the condition (∈ (X) ω A ) described above. We would like to use fusion of conditions, so in the next definition we define what fusion sequence is.
. Then we define the fusion of such a sequence to be the condition X where X(a i ) = m X m (a i ) for every i < n, and for every m ∈ ω X(m) = j≥m X j (m).
It is easy to check that X m+1 X m for every m.
This motivates the following definition.
Definition 2.6. Let G = (A, E) be an oriented graph with A as a set of vertices. We shall always assume that G contains all loops, i.e. for We use similar concept to define reduced products of two copies of (ω) α A . By G we shall denote the set of all oriented graphs containing all loops with A as the set of vertices.
Moreover, the free blocks of X and Y are equal. Notice the difference from the requirement that X and Y are G-related; in particular, for any such a graph G and any A . Proof of Theorem 2.1. Let n = |A| and again assume that A is enumerated as {a 0 , . . . , a n−1 }.
The following lemma will be the main tool.
(i) Let X ∈ (ω) ω A be any condition, H ⊆ G any subset of the set of graphs G and let M be a countable elementary submodel of some H λ , where H λ is sufficiently large, which contains X and E. Then Before we prove the lemma we show how Theorem 2.1 follows. Note that for each oriented graph G ∈ G the forcing notion (ω) ω A × RG (ω) ω A adds a pair of G-related elements from (ω) 0 A denoted as x L and x R . By G , we mean the forcing relation related to the forcing notion Suppose that Case 1 holds.
We fix some countable elementary submodel M of a large enough structure containing everything necessary and use Lemma 2.8 (i) with this M, condition X and H = G. We get some Y 0 X such that for every z, y ∈ [Y ] if there is some G ∈ G such that z and y are G-related, then the pair (z, ). This is immediate. Let z = y ∈ [Y ] be arbitrary. Let G ∈ G be such that for every a, b ∈ A (a, b) ∈ E iff z(a) ∩ y(b) = ∅ (note that WLOG we can assume that for every a ∈ A (a, a) ∈ E simply by requiring that for every a ∈ A Y (a) ∩ω = ∅). Then z and y are G-related. Since (Y, Y ) G x L Ex R we have that M[z, y] |= z Ey, where M[z, y] is the (ω) ω A × RG (ω) ω A -generic extension of M obtained by adding the M-generic pair (z, y). Since this is a coanalytic formula, using analytic absoluteness (Fact 1.6), we get that z Ey.
Suppose that Case 2 holds.
. From the assumption, G 0 = ∅. Let P ⊆ n <n be the set of all non-increasing sequences of natural numbers less than n of lenght less than n such that for every g ∈ P we have |g|−1 i=0 g(i) = n and there is a graph G ∈ G 0 such that for every i < |g| there is a connected component of g(i) vertices (not necessarily strongly connected; i.e. for every two vertices of that component there is an undirected path from one vertex to the other). Let us order it lexicographically. Note that for every g ∈ P g(0) ≥ 2. Let h ∈ P be a maximal element in P and let H ∈ G 0 witness it; i.e. for every i < |h| there is a connected component of H containing h(i) vertices. Since h is maximal there is no graph G ∈ G 0 having a connected component of more than h(0) vertices. Similarly, among those graphs G ∈ G 0 having a connected component of h(0) vertices there is none having some other connected component of more than h(1) vertices, etc. For every i < |h| let C i ⊆ H be the corresponding connected component of H having We fix some countable elementary submodel M of a large enough structure containing everythin necessary (including (Z ′ , Y ′ )) and use Lemma 2.8 (ii). We get some (Z, Y ) ≤ RH (Z ′ , Y ′ ) such that for every z ∈ [Z] and y ∈ [Y ] such that z and y are H-related the pair (z, y) is y] |= zEy and by analytic absoluteness (Fact 1.6) we obtain zEy. Note that WLOG we may assume that Z and Y are H-related (by strengthening the condition if necessary).
We show that the transitivity of E implies something stronger. We just need one definition before.  Proof of the claim. We prove that for every z ∈ [Z] and y ∈ [Y ] such that ∀m ∈ ω∀C ∈ B(b(z)(m) ∈ C ⇔ b(y)(m) ∈ C) we have zEy. This suffices. To see this, let z, y ∈ [Z] be such that zE B y. Letȳ ∈ [Y ] be the unique element of [Y ] such that for every m ∈ ω b(ȳ)(m) = b(y)(m). Then the pair z,ȳ satisfies the condition above, thus zEȳ. Moreover, since y andȳ are H-related, we have yEȳ, thus from transitivity zEy.
Let z ∈ [Z] and y ∈ [Y ] be a pair as described above; i.e. ∀m ∈ ω∀C ∈ B(b(z)(m) ∈ C ⇔ b(y)(m) ∈ C). We abuse the graph-theoretic terminology and by an alternating path in an oriented graph we mean the path where the orientation of edges alternatively agrees with the orientation of the path and disagrees, loops do not have orientation, thus can occur anywhere in an alternating path. We shall also assume that the orientation of the first edge agrees with that of the path. Since C i , for i < |h|, is a connected component, for every pair a, b ∈ C i there exists an unoriented path from a to b and since H contains all loops there exists an alternating path from a to b. There exists an odd number n H and an alternating path of length n H (consisting of n H edges) between any pair of vertices from C i for every i < |h|. To see this, just realize that we can lengthen any alternating path by adding loops at the end. For every i < |h| and every pair a, b ∈ C i (of not necessarily distinct elements) let p(a, b) : n H + 1 → C i be such a path; i.e. p(a, b)(0) = a, p(a, b)(n H ) = b, for every m ≤ n H p(a, b)(m) ∈ C i and for every even m < n H we have (p(a, b)(m), p(a, b)(m + 1)) ∈ E H (similarly, for every odd m < n H we have (p(a, b)(m + 1), p(a, b) We define a sequence x 0 , . . . , x n H such that x 0 = z, x n h = y, for odd i x i ∈ [Y ], for even i x i ∈ [Z] and for every i < n H x i Ex i+1 . Then we get from transitivity of E that zEy. Let us define the sets To check that for every odd 0 < i ≤ n H we have x i−1 Ex i it again suffices to prove that x i−1 and x i are H-related. This is completely analogous as for i even. This finishes the proof of the claim. X) and that would be a contradiction with the definition of G 0 and the fact that G / ∈ G 0 .
Let us use Lemma 2.8 (i) with the model M, condition Z and H = G\ G 0 . We get some Y ′ 0 Z such that for every G ∈ G \ G 0 and every pair arguing as before we get that z Ey. Finally, let us slightly strengthen the condition Y ′ as follows. We define Y 0 Y ′ as follows: for every a ∈ A Y (a) = Y ′ (a), however for every m ∈ ω, the mth free block of Y (recall that free blocks are ordered by their minimal elements) is obtaining by merging n 2 + 1 free blocks of Y ′ together; more specifically, let the m-the free block of Y be the union of the i-th blocks of Y ′ , where i ranges between (n 2 + 1) · m and (n 2 + 1) · m + n 2 . We recall that n = |A|.
It follows that G ∈ G \G 0 . Otherwise, it would contradict the choice of h as a maximal element of P . Therefore, since y ′ and y are G-related, we have y ′ Ey, a contradiction. This finishes the proof of the claim.
To finish the proof of Theorem 2.1 it remains to prove Lemma 2.8.
Proof of Lemma 2.8. We prove only the item (i), the second one is just a routine modification. What we prove is that for every elementary submodel M of a large enough structure, every condition X ∈ (ω) ω A and G ∈ G there is Y 0 X such that for every z, y ∈ [Y ] if the pair z and y is G-related then this pair is M-generic for (ω) ω A × RG (ω) ω A . Repeating this claim for every G ∈ H gives the item (i) of the lemma.
So let an elementary submodel M of H λ , λ suficiently large, a graph G = (A, E G ) ∈ G and a condition X ∈ (ω) ω A be given. Let us enumerate all open dense subsets of (ω) ω a) : a ∈ A} be the set of all edges of G that are not loops. Let e = |E ′ | and let u, v ∈ n e be a pair of sequences of length e such that {(a u(i) , a v(i) ) : i < e} = E ′ .Certainly we can find e!-many of such sequences, let us enumerate them as (u i , v i ) i<e! ; i.e. for every i = j < e!, u i , v i ∈ n e , u i = u j ∨ v i = v j and for every j < e! {(a u j (i) , a v j (i) ) : i < e} = E ′ . Claim 2.13. Let Z 0 X be arbitrary, i < e! and for every j < e let w j ∈ n <ω . Then there exists T e+|w 0 |+...+|we 1 | Z such that for every z ∈ [T w 0 u i (0)w 1 u i (1)...w e−1 u i (e−1) ], every y ∈ [T w 0 v i (0)w 1 v i (1)...w e−1 v i (e−1) ] such that z and y are G-related, the pair (z, Suppose the claim is proved. We show how, by a fusion process, we can find the desired Y . Using the claim e! times we can find Y 0 e X such that for every i < e! and for every z ∈ [Y ] if z and y are G-related then they are M-generic for (ω) ω A × RG (ω) ω A . Suppose we have already found Y m−1 e+m−1 Y m−2 . Using the claim several times we can find Y m e+m Y m−1 such that for every i < e! and every e-tuple of sequences w 0 , . . . , w e−1 ∈ n <ω (each w i can be empty) such that if z and y are G-related, then this pair is M-generic for (ω) ω A × RG (ω) ω A . Let Y be the limit of the fusion sequence Y 0 e+1 Y 1 e+2 . . .. Let z, y ∈ [Y ] be a pair that is G-related. Realize that it is witnessed by some i < e! and some e-sequence w 0 , . . . , w e−1 ∈ n <ω (each and since z and y are G-related we have guaranteed at the m-th step of the fusion that the pair (z, y) is M-generic for (ω) ω A × RG (ω) ω A . Thus it remains to prove the claim.
Let s, t ∈ n <ω be a pair of sequences of the same length. We say that such a pair (s, t) is good if for every i < |s| = |t| (a s(i) , a t(i) ) ∈ E G (it may be a loop, i.e. s(i) and t(i) may be equal). For every m ∈ ω let (s m i , t m i ) i<|E G | m be an enumeration of all good pairs of sequences of length m. We shall again do a fusion.
Let T be the limit of this fusion sequence. We claim it is as desired. Let z ∈ [T w 0 u i (0)w 1 u i (1)...w e−1 u i (e−1) ] and y ∈ [T w 0 v i (0)w 1 v i (1)...w e−1 v i (e−1) ] be such that they are G-related. Then for every m there is j < |E G | m such that z ∈ [T , thus for every m ∈ ω (z, y) ∈ D m , so the pair (z, y) is M-generic for (ω) ω A × RG (ω) ω A .
We do not know whether an analogous result holds for partitions of ω having free blocks. Let us consider the following ideal I Cn,m , where n ∈ ω and m ≥ 1, on the space (ω) m A : a Borel subset A ⊆ (ω) m A belongs to I Cn,m if there is no X ∈ (ω) ω A such that (X) m A ⊆ A. For any partition B of A ∪ m let us define an equivalence relation E B on (ω) m A : for x, y ∈ (ω) m A we set xE B y iff ∀n ∈ ω∀B ∈ B(x(n) ∈ B ⇔ y(n) ∈ B). The following is our hypothesis concerning canonization for the ideal I Cn,m . Question 2.14. Let X ∈ (ω) ω A be a condition and E an analytic equivalence relation on (X) m A . Does there exist a partition B of A ∪ m and Y ∈ (X) ω A such that E ↾ (Y ) m A = E B ↾ (Y ) m A ? A result of this type would be a generalization of the full Carlson-Simpson theorem.
We finish by providing the proofs of Proposition 1.4 and Theorem 0.1.
Proof of Proposition 1.4. Fix an alphabet A with |A| = n ≥ 2. Let us prove (1). Let A n ∈ I Cn for all n ∈ ω. Suppose that A = n∈ω A n / ∈ I Cn . It must contain [X] for some X ∈ (ω) ω A . We can define a Borel equivalence relation E on [X] with countably many classes such that ∀x, y ∈ [X](xEy ⇔ ∃n ∈ ω(x, y ∈ A n )). Applying Theorem 2.1 we get Y 0 X such that E ↾ [Y ] is the full relation, the identity relation or E B ↾ [Y ] for some B ∈ P A . Since E has only countably many classes only the first case is possible. Thus E ↾ [Y ] = [Y ] × [Y ], i.e. there is n ∈ ω such that [Y ] ⊆ A n which is a contradiction.
The item (2) follows from (1). For any X ∈ (ω) ω A , [X] is a Borel (closed) I Cn -positive subset; conversely, it follows from (1) that any Borel I Cn -positive subset of A ω contains [X] for some X ∈ (ω) ω A . We now prove (3). Consider the suborders m ⊆ m−1 ⊆ . . . ⊆ 0 on (ω) ω A . It is easy to check that (ω) ω A with these relations satisfies Axiom A and thus it is proper (we refer to [2] p. 604, for example).
Proof of Theorem 0.1. This is just a special case of Theorem 2.1 for A = {a 0 , a 1 } and if we consider X to be the biggest condition in (ω) ω A . Theorem 2.1 gives a subcondition Y ∈ (ω) ω A on which E is simple. The condition Y determines the sequence (A n ) n∈ω : A 0 = Y (a 1 ) and A i = A(i − 1) for i ≥ 1.
Let us just note that we cannot eliminate the set A 0 from the statement, i.e. demand it to be empty. Just consider an equivalence relation E on P(ω) where for a, b ∈ P(ω) we have aEb if min a = min b.