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.
In any metric space compactness implies countable compactness and limit point compactness, and each of countable compactness and limit point compactness implies sequential compactness; every implication here is proved without a choice principle
Statement
Let be a metric space (Metric space: iff , symmetry, and the triangle inequality; pseudometric and ultrametric), with compactness as in Open cover, subcover, compact metric space, and compact subset of a metric space and the three variants as in Countably compact, sequentially compact and limit point compact metric spaces. Then:
- If is compact, it is countably compact.
- If is compact, it is limit point compact.
- If is countably compact, it is sequentially compact.
- If is limit point compact, it is sequentially compact.
Every one of the four is a theorem of ZF. Where a subsequence is extracted, the index at each stage is the least admissible one, which The well-ordering principle makes canonical and The recursion theorem then assembles into a function; where finitely many indices have to be recovered from finitely many sets, Every natural-number-indexed list of nonempty sets has a choice function on its family of values supplies them and is itself a theorem of ZF. Nothing below appeals to countable or to dependent choice.
Facts & Assumptions
Given: A metric space , whichever of the four properties is assumed in the claim under proof.
The definitions: is compact when every family of open subsets with union has a finite subfamily with union ; countably compact when every such family that is at most countable does; sequentially compact when every sequence has a subsequence converging in ; limit point compact when every infinite subset has a limit point in , where is a limit point of when for every real (Open cover, subcover, compact metric space, and compact subset of a metric space, Countably compact, sequentially compact and limit point compact metric spaces, Interior, closure, boundary, limit point, isolated point and dense subset of a metric space, Sequences of reals: bounded, eventually, frequently, tails, subsequences).
Open balls are open, an arbitrary union of open sets is open, and a set is closed exactly when its complement is open (Arbitrary unions and finite intersections of open sets are open, open balls are open and closed balls are closed, The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement, Open ball, closed ball and sphere in a metric space).
The closure is closed, contains and is the smallest closed superset of ; and exactly when for every real (The closure of a nonempty is , equals together with its limit points, and is the smallest closed superset, Interior, closure, boundary, limit point, isolated point and dense subset of a metric space).
Recursion: for a set , an element and a function there is a unique with and ; when the recursion rule depends on the stage, it is applied to and the first coordinate of is , by the small induction recorded in Finite sums and finite products, by recursion (The recursion theorem).
Every nonempty subset of has a least element (The well-ordering principle).
A finite list of natural numbers has a greatest member: the reals , with the canonical natural of (The canonical natural of a field), form a nonempty finite set of reals and so have a maximum, which is one of them, say (Every nonempty finite set of reals has a maximum and a minimum, Maximum and minimum of a set); is strictly increasing on the naturals (Canonical naturals are positive and strictly increasing) and the order of is linear ( is a linear order on ), so for every .
A nonempty finite set of reals has a minimum, which is one of its members (Every nonempty finite set of reals has a maximum and a minimum, Maximum and minimum of a set).
Finiteness: a set listed as is finite, a nonempty finite set can be listed, and a subset of bounded above is finite (Open cover, subcover, compact metric space, and compact subset of a metric space, Finite, countably infinite, countable, uncountable, Every subset of an at most countable set is at most countable); an injection carries a set to a set in bijection with its image (Injection, surjection, bijection).
A family indexed by is at most countable, being the image of a surjection from (Finite, countably infinite, countable, uncountable, A nonempty set is at most countable iff it is a surjective image of ).
when for every rational there is with for ; and for every real there is a natural with (Convergence of a sequence in a metric space: iff in , For every in a complete ordered field there is a natural with , Every complete ordered field is Archimedean).
An index map with for every is strictly increasing, and then (A strictly increasing index map satisfies ).
A function with domain a natural number all of whose values are nonempty sets has a choice function, in ZF (Every natural-number-indexed list of nonempty sets has a choice function on its family of values).
A metric is symmetric and satisfies the triangle inequality, and exactly when (Metric space: iff , symmetry, and the triangle inequality; pseudometric and ultrametric).
Proof
Claim 1 is immediate: an at most countable family of open sets with union is in particular a family of open sets with union , so compactness supplies the finite subfamily that countable compactness asks for.
For claim 2, assume compact, let have no limit point in , and put , a family cut out by a property; has union , because each fails to be a limit point of and so admits with , whence and .
Compactness gives and with , unless , in which case is finite.
Define by letting be the least with ; this is well defined and canonical, and it is injective, since puts both and in , a set with at most one element. Hence is in bijection with , a subset of bounded above by , so is finite.
So a subset of with no limit point in is finite; contrapositively every infinite subset of has a limit point in , and is limit point compact: claim 2.
For claim 3, assume countably compact, let be a sequence in and put for .
Each is closed and contains , and whenever , because and is the smallest closed superset of the first set.
Suppose for contradiction that ; then is an at most countable family of open subsets of whose union is .
Countable compactness gives a finite subfamily of with union ; putting , each equals for at least one , so finite choice applied to yields indices with , and a greatest member of that list satisfies for every .
Then , contradicting .
Hence there is with for every .
For every and every the set is nonempty, since means that the ball meets ; so it has a least element, and likewise is nonempty and has a least element .
Applying recursion on to the starting value and the rule produces whose first coordinate at is ; write for its second coordinate.
Then for every , so is strictly increasing, and for every , the case being the choice of .
Given a rational take a natural with ; for one has and so . Hence , the sequence has a convergent subsequence, and is sequentially compact: claim 3.
For claim 4, assume limit point compact, let be a sequence in and let be its range, a nonempty subset of .
Suppose first that is finite, and list it as ; putting for gives .
Some is unbounded in : otherwise each has an upper bound in and hence a least upper bound , canonical by well-ordering, and a greatest member of the list would satisfy for every , so that lies in no , against . Let be the least for which is unbounded.
Recursion applied to the starting value and the rule , each of these sets being nonempty because is unbounded, produces a strictly increasing with for every ; a constant sequence converges to its value, so .
Suppose instead that is infinite; limit point compactness then gives a limit point of .
Suppose for contradiction that some real and some satisfy for every .
Let be the set listed by together with the entries for , where if and otherwise; every listed entry is a positive real, so is a nonempty finite set of positive reals and . Then misses : a point of is with , and when , while when . That contradicts being a limit point of .
Hence for every real and every there is with .
Consequently, for every and every the set is nonempty, as is , and the recursion of steps 13.1 and 14.1 applies verbatim, producing a strictly increasing with ; by the estimate of step 15.1, .
In both cases has a subsequence converging in , so is sequentially compact: claim 4.
Claims 1, 2, 3 and 4 are proved by steps 1.1, 5.1, 15.1 and 25.1 respectively.
Remarks
Why "least" and not "some". At every stage of every recursion above, the next index is the least one meeting the requirement. That is what keeps the four implications inside ZF: a rule that says "take some admissible " would be a selection made infinitely often, and one made in terms of the previous stage, which is dependent choice (The axiom of dependent choice: a relation in which every element is related to something admits an -indexed chain) rather than countable choice. The same device is what A sequentially compact metric space is totally bounded, proved from the axiom of dependent choice cannot use, and that is exactly why that theorem, alone among the implications between the compactness properties on this page, costs dependent choice. It is not the only implication on the page with a choice cost: A complete, totally bounded metric space is compact, proved from countable choice used exactly once spends countable choice, for the different reason that it needs one net for every radius at once. The arrow-by-arrow accounting is What each implication between the compactness properties of a metric space costs: which are theorems of ZF, which use countable choice, and which use dependent choice.
Finite selections are free. Step 9.1 does select, but only over the finite index set , and Every natural-number-indexed list of nonempty sets has a choice function on its family of values proves that such a selection exists in ZF by induction on the size of the index set. Nothing is being smuggled in: what a choice principle buys is infinitely many selections at once.
The two routes to sequential compactness are genuinely different. Claim 3 works with the closures of the tails of the given sequence and needs the countable cover they generate; claim 4 works with the range of the sequence and splits on whether it is finite. Neither argument subsumes the other, and both are needed, because the equivalence proved in For a metric space, compact, countably compact, limit point compact, sequentially compact, and complete together with totally bounded are all equivalent, given countable choice and dependent choice passes through both.
Depends on
- Open cover, subcover, compact metric space, and compact subset of a metric space
- Countably compact, sequentially compact and limit point compact metric spaces
- The closure of a nonempty $A$ is $\{x : d(x,A) = 0\}$, equals $A$ together with its limit points, and is the smallest closed superset
- Interior, closure, boundary, limit point, isolated point and dense subset of a metric space
- The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement
- Arbitrary unions and finite intersections of open sets are open, open balls are open and closed balls are closed
- Open ball, closed ball and sphere in a metric space
- The recursion theorem
- Finite sums and finite products, by recursion
- The well-ordering principle
- Every natural-number-indexed list of nonempty sets has a choice function on its family of values
- Every nonempty finite set of reals has a maximum and a minimum
- Maximum and minimum of a set
- The canonical natural $\iota(n) = n \cdot 1_F$ of a field
- Canonical naturals are positive and strictly increasing
- $\le$ is a linear order on $\mathbb{N}$
- Convergence of a sequence in a metric space: $x_k \to x$ iff $d(x_k, x) \to 0$ in $\mathbb{R}$
- A strictly increasing index map satisfies $n_k \ge k$
- For every $\varepsilon > 0$ in a complete ordered field there is a natural $n \ge 1$ with $1/n < \varepsilon$
- Every complete ordered field is Archimedean
- Sequences of reals: bounded, eventually, frequently, tails, subsequences
- Finite, countably infinite, countable, uncountable
- A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$
- Every subset of an at most countable set is at most countable
- Injection, surjection, bijection
- Metric space: $d(x,y) = 0$ iff $x = y$, symmetry, and the triangle inequality; pseudometric and ultrametric
Used by
- For n ≥ 1 every bounded sequence in ℝⁿ has a convergent subsequence Corollary
- FALSE: in every normed space a closed bounded set is compact False statement
- What each implication between the compactness properties of a metric space costs: which are theorems of ZF, which use countable choice, and which use dependent choice Remark
- For a metric space, compact, countably compact, limit point compact, sequentially compact, and complete together with totally bounded are all equivalent, given countable choice and dependent choice Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 102 results over 23 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Sequentially compact space (Wikipedia) (standard reference, not scraped)
- Limit point compact (Wikipedia) (standard reference, not scraped)
- Countably compact space (Wikipedia) (standard reference, not scraped)