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.
Basic bounds for p and t
Statement
In ZFC, with and as in The pseudointersection and tower numbers,
and moreover every countable family of infinite subsets of with the strong finite intersection property has a pseudointersection, and every countable descending family of infinite subsets of has a pseudointersection (Almost inclusion, pseudointersections and towers for the notions).
The countable case is the diagonal construction: the running finite intersections are infinite, and choosing the least new element of each running intersection produces an infinite set meeting every member cofinitely. That gives and ; a tower is an SFIP family with no pseudointersection, which gives ; and is the normal form of a shortest tower.
Facts & Assumptions
Given: the Axiom of Choice (The Axiom of Choice).
A pseudointersection of is an with for all ; has SFIP when every finite intersection of members is infinite; a tower is a decreasing family of infinite sets with no pseudointersection. (Almost inclusion, pseudointersections and towers)
is the least cardinality of an SFIP family with no pseudointersection, and the minimum is attained; is the least length of a tower, the minimum is attained by a strictly decreasing tower , and is a cardinal with . (The pseudointersection and tower numbers)
Every nonempty subset of has a least element, and recursion on defines the unique sequence with prescribed value at and prescribed successor step. (The well-ordering principle, The recursion theorem, The natural numbers (von Neumann))
Under AC every set has a cardinality, cardinals are comparable, and every family of nonempty sets has a choice function. (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, The Axiom of Choice)
Proof
Let be a sequence of infinite subsets of all of whose finite intersections are infinite, and set ; then each is infinite, and .
: by [F2] there is a strictly decreasing tower ; its member family has cardinality , since is injective. The family has SFIP: for the intersection contains minus the finitely many finite sets . It has no pseudointersection, because it is a tower. Hence some SFIP family without pseudointersection has size , and .
Recursively choose to be the least element of ; this is legitimate because is infinite and only finitely many elements have been removed, so the set is nonempty, and it has a least element by [F3]. Then and the are pairwise distinct, since .
is infinite by step 2.1, and for every : indeed whenever , so is finite. Hence is a pseudointersection of .
Now let be countable and have the strong finite intersection property. If , then is a pseudointersection and the claim follows. Otherwise list as a sequence , repeating one member if is finite; that is possible by [F3] and [F4], and the finite intersections of the are still infinite. Put ; each is infinite by SFIP, and the sequence has all finite intersections infinite, since . By steps 1.1, 2.1 and 3.1 applied to there is with for every .
Every countable descending family of infinite sets has a pseudointersection: reaching from earlier members removes only finitely many points, so satisfies , a finite set, and is infinite because is; the family therefore consists of infinite sets with all finite intersections infinite, and steps 1.1, 2.1 and 3.1 applied to it give with for every .
For each the pseudointersection of step 4.1 is almost contained in , hence has a pseudointersection.
: a tower of length would be a countable descending family of infinite sets, so by step 4.2 it would have a pseudointersection, which a tower cannot have. Since is a cardinal, is excluded, so .
: if has size below , then is finite or countably infinite and, when nonempty, can be listed as a sequence with repetitions if finite; if has SFIP then step 5.1 supplies a pseudointersection. Hence no family of size below has SFIP and lacks a pseudointersection, and since is a cardinal with an attained minimum, .
is clause [F2]. Combining steps 6.1, 1.2, 5.2 and 7.1 gives , and steps 5.1 and 4.2 are the two countable pseudointersection assertions. This is the statement. ∎
Depends on
- The pseudointersection and tower numbers
- Almost inclusion, pseudointersections and towers
- A tower of size at most the continuum exists
- 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
- The successor cardinal $\kappa^{+}$, the alephs $\aleph_\alpha$, the beths $\beth_\alpha$, successor and limit cardinals, and the identifications $\aleph_0 = \omega$ and $\aleph_1 = \omega_1$
- The well-ordering principle
- The recursion theorem
- The natural numbers $\mathbb{N}$ (von Neumann)
Used by
Dependency tree · two levels
53 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
- J. D. Monk, Continuum cardinals, Blass 6.23 and Proposition 34, printed pp.14-15, 19 (standard reference, not scraped)
- M. Malliaris and S. Shelah, Cofinality Spectrum Theorems, Definition 14.3 and the surrounding discussion, PDF pp.54-55 (standard reference, not scraped)