The Setting
In a matroid, an independent set inside a spanning set extends to a base with . Lemma 4.5 is an interpolation of the same shape for subsets of a doubled countable ground set that differ from a fixed set by a set of density zero. Such sets are compared with through , the lower limit of the counting probes of against .
The library states the lemma for the probes of and, beside it, an interpolation theorem for an arbitrary sequence of real functions on the subsets of . It also states the interpolation in three cases (a finite lower limit at , a finite lower limit at , and infinite limits of opposite signs at the two ends) and a deletion stage, which removes finitely many elements from a set lying between two given sets.
Blocks, Densities and Classes
The set is the countable set of pairs of a natural number and a Boolean function .✦ For a natural number , the block of is the set of the pairs with first entry ; it is finite and has elements.✦ The ground set is the disjoint union of a left copy of , the pairs with second entry false, and a right copy , those with second entry true.✦ The doubled block is the finite subset of lying over on both sides.✦
Given a finite subset of a set , the density of a subset of in is , where is the trace of on .✦ The block density of a subset of at is its density in the doubled block , (1)✦ A subset of is small when as ; the small sets form the ideal .✦ The class of a subset of is the family of subsets of with .✦
Probes and Lower Limits
Fix a subset of . For , the prefix is the finite subset of formed by the first doubled blocks, and is its number of elements.✦ The prefix count difference of a subset of is ✦, and its density difference at is ✦. The probe of relative to is the real number that adds to the sum of the tail supremum and the tail infimum of the density differences from on, scaled by : (2)✦
For a sequence of real functions on the subsets of a set , the lower limit of at a subset of is the extended real number (3)✦ and is the lower limit at of the probes (2). A subset of lies in the window of when .✦
Conditions on an Interval
For subsets of a set , the interval is the family of sets with . A sequence of real functions on the subsets of is monotone on when for every and all in . A sequence of real functions on the subsets of rises by at most one per inserted element on when for every and all in with for some element . A sequence of real functions on the subsets of has a lower limit that shifts exactly by finite additions on when (4)✦ A sequence of real functions on the subsets of is frequently negative on the finite extensions of when every set of with finite has for infinitely many .
Two sets and of natural numbers agree below when every lies in exactly when it lies in .✦ A sequence of real functions on the subsets of is cylinder-continuous on when for every and every there is an such that (5)✦
The Claim
Theorem 1. Let be a subset of , and let be sets of the class with and . Then some set of satisfies (6)✦
In the paper, the result reads: there is a set in the family of the paper with .
Theorem 2. Let be a sequence of real functions on the subsets of and sets of natural numbers. Suppose that is cylinder-continuous and monotone on , rises there by at most one per inserted element, and has a lower limit that shifts exactly by finite additions on . If and , then some set satisfies (7)✦
Theorem 3. Let be a sequence of real functions on the subsets of a set and subsets of such that the lower limit of shifts exactly by finite additions on , with and . If (8)✦ or if (9)✦ then some set with has .
Theorem 4. Let be a sequence of real functions on the subsets of and sets of natural numbers. Suppose that is cylinder-continuous and monotone on , rises there by at most one per inserted element, and is frequently negative on the finite extensions of , and that for all large . Then some set with satisfies (10)✦
Theorem 5. Let be a sequence of real functions on the subsets of and sets of natural numbers. Suppose that is cylinder-continuous on , rises there by at most one per inserted element, and is frequently negative on the finite extensions of . Then for every and every some set with and finite satisfies (11)✦
What Is Checked
The claim (6) is stated over the doubled blocks of , the ideal of small sets with the class , and the probes (2) of with their lower limit ; the claims (7) to (11) are stated over an arbitrary sequence of real functions on the subsets of , or of any set in (8) and (9), through its lower limit (3), the exact shift (4), cylinder continuity (5), monotonicity and the bound on single insertions.