LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 2026-09-27

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Ideal Tukey morphisms control additivity and cofinality

Statement

Let $X$ be a set and let $I, J \subseteq P (X)$ be proper ideals: each contains $\emptyset$ , is closed under taking subsets, and does not contain $X$ . Let $add$ and $cof$ be defined for a family of subsets of $X$ by the minimum clauses of Add, cov, non and cof for null and meagre ideals, $add (J) = \min {∣ A ∣ : A \subseteq J, ⋃ A \notin J}$ and $cof (J) = \min {∣ A ∣ : A \subseteq J, \forall B \in J \exists A \in A (B \subseteq A)}$ . Assume these minima exist for both $I$ and $J$ ; equivalently for additivity, each family has a subfamily whose union lies outside it. Suppose $u : I \to J$ and $v : J \to I$ are functions satisfying

$u (A) \subseteq B ⟹ A \subseteq v (B) for all A \in I, B \in J .$

Then $add (J) \leq add (I)$ and $cof (I) \leq cof (J)$ . The same two inequalities hold in the weaker form in which $I_{0} \subseteq I$ and $J_{0} \subseteq J$ are inclusion-cofinal $^{*}$ subfamilies (every member of $I$ is contained in a member of $I_{0}$ , and similarly for $J$ ) and the morphism is given only between $I_{0}$ and $J_{0}$ , with the Axiom of Choice available to extend it.

The relevant instances are $I, J \in {N, M}$ on the real line and their coded cofinal subfamilies on Cantor space; the inequalities are used below in exactly the direction displayed, with no reversal.

Facts & Assumptions

Given: A set $X$ , proper ideals $I, J \subseteq P (X)$ , functions $u : I \to J$ and $v : J \to I$ with the displayed property, and the attained $add$ and $cof$ minima for both families as assumed in the Statement.

[F1]

For a family $K \subseteq P (X)$ of subsets of $X$ , $add (K)$ is the least cardinality of a subfamily of $K$ whose union is not in $K$ , and $cof (K)$ is the least cardinality of an inclusion-cofinal subfamily of $K$ ; for $K = N$ and $K = M$ the two minima exist and are attained. (Add, cov, non and cof for null and meagre ideals)

[F2]

The Axiom of Choice supplies a choice function for every family of nonempty sets, and under it every set has a cardinality and cardinalities are cardinals. (The Axiom of Choice, A set equinumerous with some ordinal has a least such ordinal, that ordinal is a cardinal, and equinumerous sets get the same one; no choice principle is used, Cardinal (initial ordinal) and cardinality)

Proof

technique · direct

1.1

If $κ < add (J)$ and $(B_{i})_{i < κ}$ is a family of members of $J$ , then $⋃_{i < κ} B_{i} \in J$ : otherwise that subfamily would be a subfamily of $J$ of cardinality at most $κ$ whose union is not in $J$ , and its cardinality would be a candidate in the minimum defining $add (J)$ strictly below that minimum.

givenF1

1.2

$cof (I) \leq cof (J)$ : let $B \subseteq J$ be inclusion-cofinal in $J$ with $∣ B ∣ = cof (J)$ . For every $A \in I$ , cofinality of $B$ gives some $B \in B$ with $u (A) \subseteq B$ , and the displayed morphism property gives $A \subseteq v (B)$ . Thus the image ${v (B) : B \in B} \subseteq I$ is inclusion-cofinal without simultaneously selecting a witness for each $A$ , and $cof (I) \leq ∣ {v (B) : B \in B} ∣ \leq ∣ B ∣ = cof (J)$ .

givenF1

2.1

$add (J) \leq add (I)$ : let $κ < add (J)$ and let $(A_{i})_{i < κ}$ be a family of members of $I$ ; by step 1.1 the set $B : = ⋃_{i < κ} u (A_{i})$ is a member of $J$ , and $u (A_{i}) \subseteq B$ gives $A_{i} \subseteq v (B)$ for every $i$ by the displayed property, so $⋃_{i < κ} A_{i} \subseteq v (B)$ ; since $v (B) \in I$ and $I$ is closed under subsets, $⋃_{i < κ} A_{i} \in I$ . Hence no subfamily of $I$ of size below $add (J)$ has its union outside $I$ , and the minimum clause for $add (I)$ gives $add (I) \geq add (J)$ .

step 1.1givenF1

3.1

The cofinal-subfamily form: assume $I_{0} \subseteq I$ and $J_{0} \subseteq J$ are inclusion-cofinal and that $u : I_{0} \to J_{0}$ , $v : J_{0} \to I_{0}$ satisfy the displayed property there. By [F2] choose for every $A \in I$ a member $A^{+} \in I_{0}$ with $A \subseteq A^{+}$ and for every $B \in J$ a member $B^{+} \in J_{0}$ with $B \subseteq B^{+}$ , and put $\overset{ˉ}{u} (A) : = u (A^{+})$ and $\overset{ˉ}{v} (B) : = v (B^{+})$ ; if $\overset{ˉ}{u} (A) \subseteq B$ for $A \in I$ , $B \in J$ , then $u (A^{+}) \subseteq B^{+}$ with $A^{+} \in I_{0}$ and $B^{+} \in J_{0}$ , so the cofinal-subfamily property gives $A^{+} \subseteq v (B^{+}) = \overset{ˉ}{v} (B)$ and hence $A \subseteq \overset{ˉ}{v} (B)$ ; thus $\overset{ˉ}{u} : I \to J$ and $\overset{ˉ}{v} : J \to I$ satisfy the hypotheses of steps 2.1 and 1.2, which give $add (J) \leq add (I)$ and $cof (I) \leq cof (J)$ .

step 2.1step 1.2givenF2

4.1

Steps 2.1 and 1.2 prove the two inequalities for a morphism defined on the full ideals without a simultaneous witness selection, and step 3.1 transfers them to morphisms defined only on inclusion-cofinal subfamilies, with the Axiom of Choice used for the two selections in step 3.1; the cardinal minima themselves are interpreted in ZFC. This is the statement. ∎

step 2.1step 1.2step 3.1

Depends on

Used by

Null-to-meagre Tukey inequalities Lemma

Dependency tree · two levels

36 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Tomek Bartoszynski, Invariants of Measure and Category, Lemma 2.2 and the surrounding Tukey discussion, printed pp.2-3 (standard reference, not scraped)