Ideal Analytic sets

This paper establishes the descriptive complexity of various mathematical structures by proving that the Hindman ideal, the ideal $\mathcal{D}$, and specific families of trees are $\mathbf{\Pi}_1^1$-complete, while also exploring the connections between ideals on $\omega$ and classical tree types like Sacks and Miller.

The Gist

Imagine you are a detective trying to sort through an infinite library of books. Some books are simple and easy to categorize (like "Fiction" or "Non-Fiction"), but others are so complex that no standard filing system can ever fully capture them. In mathematics, specifically in a field called Descriptive Set Theory, researchers study these "impossible to categorize" collections.

This paper by Łukasz Mazurkiewicz and Szymon Żeberski is about finding natural examples of these super-complex collections. They want to prove that certain groups of mathematical objects are as complicated as it gets.

Here is a breakdown of their work using simple analogies:

1. The Goal: Finding the "Ultimate Puzzle"

The authors are looking for sets that are $\Sigma^1_1$-complete or $\Pi^1_1$-complete.

• The Analogy: Imagine a "Master Key" that can open any lock in the universe. If you have a set that is "complete," it means it is so complex that any other complex problem can be translated (or "reduced") into a problem about this specific set.
• The Benchmark: The authors use a known "Master Key" called Ill-Founded Trees.
  • Think of a Tree as a family tree or a decision tree.
  • A Well-Founded Tree is one that eventually stops; every branch hits a leaf. It's finite in depth.
  • An Ill-Founded Tree is one that has a branch that goes on forever, never stopping.
  • The collection of all trees that have an infinite branch is the "Master Key" for complexity. If you can prove your new collection is just as hard to solve as finding an infinite branch, you've proven it's "complete."

2. Part 1: The Ideals (The "Trash Bins")

The first half of the paper looks at Ideals on natural numbers.

• What is an Ideal? Imagine a "Trash Bin" for numbers.
  • Rule 1: If you throw a number in the bin, you must also throw in all its smaller parts (subsets).
  • Rule 2: If you throw two piles of trash in, their combination is also trash.
  • The Catch: The bin cannot contain everything (the whole set of numbers).
• The Question: Is the collection of "Trash Bins" that satisfy certain weird rules simple to describe, or is it a "Master Key" level of complexity?

The authors use a Unified Approach (a single, clever recipe) to prove that several specific types of "Trash Bins" are indeed $\Pi^1_1$-complete (the "Master Key" level of complexity). They show this by taking the "Infinite Branch" problem and translating it into these trash bin problems.

Here are the specific "Trash Bins" they analyzed:

• The Ramsey Ideal: Deals with pairs of numbers. If you have an infinite set of numbers, can you always find a pair that fits a specific pattern? The authors prove that deciding if a set fails this pattern is incredibly complex.
• The Hindman Ideal: Deals with sums. If you take an infinite set of numbers and add up any finite group of them, do you get a new set of numbers? The "Hindman Ideal" contains sets that don't have this property. The authors prove that checking for this property is a "Master Key" level of difficulty.
• Variations: They also looked at sums of exactly $k$ numbers and differences between numbers. They proved these are also incredibly complex (with a footnote mentioning a colleague later proved this for all variations).

The Metaphor: It's like trying to find a specific needle in a haystack. The authors proved that for these specific types of haystacks (Ideals), finding the needle is as hard as finding an infinite path in a maze that never ends.

3. Part 2: Trees and Codes (The "Blueprints")

The second half of the paper connects these "Trash Bins" to Trees and Codes.

• The Connection: In math, you can describe a shape (like a closed set of points) by drawing a "Tree" that leads to it.
• The Discovery: The authors showed that the "Trash Bin" problems they solved in Part 1 are actually the same as asking: "Does this tree contain a specific, very special type of branch?"

They applied their "Master Key" proof to three famous types of trees:

1. Mathias Trees: Trees that look like a specific forcing structure used in logic.
2. Miller Trees: Trees where every branch eventually splits into infinitely many new paths.
3. Laver Trees: Similar to Miller trees but with a specific "stem" at the bottom.

The Result:
They proved that the collection of all "Codes" (blueprints) for sets that do not contain these special trees is $\Pi^1_1$-complete.

• Translation: If you want to know if a closed shape in a mathematical space is "Ramsey-null" (a specific type of smallness), or "Sigma-compact" (a specific type of finiteness), checking this is as hard as the hardest problems in mathematics.

4. The Exceptions (The "Easy" Cases)

To make their point stronger, the authors also looked at two other famous types of trees:

• Sacks Trees (Perfect Trees): Trees where every branch splits into two forever.
• Silver Trees: Trees with a very rigid, predictable pattern.

They proved that checking for these is $\Sigma^1_1$-complete (still very hard, but a different flavor of hard).

Finally, they looked at Meager Sets (sets that are "thin" or "sparse") and Measure Zero Sets (sets that take up "no space").

• The Surprise: Unlike the others, the codes for these sets are Borel.
• The Metaphor: While the other problems were like trying to solve a Rubik's cube blindfolded, these are like sorting a deck of cards by color. They are complex, but they are solvable with a standard algorithm. They are not the "Ultimate Puzzle."

Summary

This paper is a tour de force in mathematical logic. The authors built a universal translator (the unified approach) to show that:

1. Many specific "Trash Bin" collections (Ideals) are as complex as the hardest problems in math.
2. This complexity translates directly to the difficulty of recognizing certain types of shapes (closed sets) in mathematical spaces.
3. However, not all complex-looking sets are equally hard; some (like thin or empty sets) are actually manageable.

They essentially drew a map of the "Complexity Universe," showing us exactly which islands are the most treacherous and which ones we can actually navigate.

Technical Summary

Here is a detailed technical summary of the paper "Ideal Analytic Sets" by Łukasz Mazurkiewicz and Szymon Żeberski.

1. Problem Statement

The primary objective of the paper is to provide natural, concrete examples of sets that are $\Sigma^1_1$-complete (analytic-complete) and $\Pi^1_1$-complete (coanalytic-complete) within the context of descriptive set theory.

Specifically, the authors aim to:

• Establish the descriptive complexity of various ideals on $\omega$ (the set of natural numbers).
• Determine the complexity of families of trees (such as Miller, Laver, Sacks, and Silver trees).
• Analyze the complexity of codes for closed sets in Polish spaces (specifically the Baire space $\omega^\omega$ and Cantor space $2^\omega$) belonging to specific$\sigma$-ideals (e.g., Ramsey-null,$\sigma$-compact, strongly dominating, and measure zero sets).

The paper seeks to unify these disparate examples under a single framework to prove their completeness properties without relying on ad-hoc reductions for each case.

2. Methodology: The Unified Approach

The core methodological innovation is the application of a unified reduction approach introduced in a previous work [3]. The authors construct a general mechanism to reduce the set of ill-founded trees ($IF_\omega$), which is a known $\Sigma^1_1$-complete set, to various target sets.

The Reduction Mechanism:

1. Setup: Let $\Lambda$ be a countable infinite set and $\rho: \mathcal{P}(\omega) \to \mathcal{P}(\Lambda)$ be a monotone function.
2. Target Ideal: Define an ideal $I_\rho = \{A \subseteq \Lambda : (\forall F \in [\omega]^\omega)(\rho(F) \not\subseteq A)\}$. The complement $I_\rho^+$ consists of sets containing a "large" image of an infinite set under $\rho$.
3. Encoding: Fix an injection $\alpha: \omega^{<\omega} \to \omega$ that preserves the prefix order ($\sigma \subseteq \tau \implies \alpha(\sigma) \le \alpha(\tau)$).
4. The Function $\phi$: For any tree $T \in \text{Tree}_\omega$, define:
   $$\phi(T) = \bigcup_{\sigma \in T} \rho(\{\alpha(\sigma \upharpoonright k) : k \le |\sigma|\})$$
5. Logic of Reduction:
   • If $T$ is ill-founded (has an infinite branch), the image $\phi(T)$ contains the image of that branch, ensuring $\phi(T) \in I_\rho^+$.
   • If $\phi(T) \in I_\rho^+$ (i.e., it contains $\rho(B)$ for some infinite $B$), the specific properties of $\rho$ and $\alpha$ are used to reconstruct an infinite branch in $T$, proving $T$ is ill-founded.
   • Thus, $\phi^{-1}[I_\rho^+] = IF_\omega$, proving that $I_\rho^+$ is $\Sigma^1_1$-complete and $I_\rho$ is $\Pi^1_1$-complete.

3. Key Contributions and Results

Part I: Ideals on $\omega$

The authors apply the unified approach to prove the $\Pi^1_1$-completeness of several specific ideals:

• Ramsey Ideal ($R$): Defined via $r(B) = [B]^2$. The paper provides a new proof (using the unified approach) that $R$ is $\Pi^1_1$-complete.
• Hindman Ideal ($H$): Defined as the family of non-IP-sets (sets not containing finite sums of an infinite set). The authors prove $H$ is $\Pi^1_1$-complete.
• Generalized Hindman Ideals ($H_k$): Ideals of non-$IP_k$-sets (sets not containing sums of exactly $k$ elements).
  • They establish the inclusion hierarchy: $H_n \subseteq H_m \iff n | m$.
  • They prove $H_2$ is $\Pi^1_1$-complete.
  • Note: A footnote mentions that a proof for $H_k$ for all $k \ge 2$ was provided by Jacek Tryba during the review process, though the paper's main text only details the $k=2$ case due to technical difficulties in the binary expansion argument for higher $k$.
• Difference Ideal ($D$): The family of non-D-sets (sets not containing differences of an infinite set). The authors prove $D$ is $\Pi^1_1$-complete.

Part II: Trees and Coding of $\sigma$-Ideals

The authors extend the reduction technique to families of trees and their corresponding closed sets in Polish spaces.

A. Families of Trees
They prove that the family of trees containing a specific type of "subtree" is $\Sigma^1_1$-complete:

• Mathias Trees: Trees containing a "Mathias bush" (related to Mathias forcing).
• Miller Trees: Trees where every node has an extension with infinitely many immediate successors.
• Laver Trees: Trees with a stem such that every extension has infinitely many successors.
• Sacks Trees (Perfect Trees): Trees where every node has a splitting extension.
• Silver Trees: Trees defined by a coinfinite domain and a fixed function on that domain.

B. Codes for Closed Sets in $\sigma$-Ideals
By linking the existence of specific trees to the non-membership of closed sets in certain $\sigma$-ideals, they derive the complexity of the sets of codes for these closed sets:

1. Ramsey-null sets: The set of codes for closed Ramsey-null sets is $\Pi^1_1$-complete.
2. $\sigma$-compact sets: The set of codes for closed $\sigma$-compact sets is $\Pi^1_1$-complete.
3. Non-strongly dominating sets: The set of codes for closed sets that are not strongly dominating is $\Pi^1_1$-complete.
4. $G$-independent sets: The set of codes for closed sets positive with respect to the $\sigma$-ideal generated by Borel $G$-independent sets is $\Pi^1_1$-complete.

C. Counter-Examples (Borel Sets)
The paper also identifies cases where the set of codes is Borel (and thus not $\Pi^1_1$-complete), highlighting the boundary of complexity:

• The set of codes for closed meager subsets of the Cantor/Baire space is Borel.
• The set of codes for closed measure zero subsets of the Cantor space is Borel.

4. Significance

• Unification: The paper demonstrates that a single, elegant reduction framework can handle a wide variety of complex sets in descriptive set theory, ranging from combinatorial ideals on $\omega$ to topological properties of trees and closed sets.
• Natural Examples: It provides "natural" examples of $\Sigma^1_1$ and $\Pi^1_1$-complete sets, moving beyond abstract existence proofs to concrete mathematical structures (ideals, forcing notions).
• Complexity Classification: It settles the descriptive complexity of coding problems for several important $\sigma$-ideals (Ramsey, $\sigma$-compact, dominating), showing that determining if a closed set belongs to these ideals is maximally complex (coanalytic-complete).
• Distinction: By contrasting these results with the Borel complexity of meager and measure-zero codes, the paper clarifies the structural differences between "small" sets in the sense of category/measure versus those defined by combinatorial or forcing properties.

In summary, Mazurkiewicz and Żeberski successfully map the landscape of analytic and coanalytic sets through the lens of ideals and trees, providing a robust toolkit for proving completeness in this domain.