Verify any claim · lenz.io
Claim analyzed
Science“Every infinite set contains a countably infinite subset.”
Submitted by Keen Crane bc3e
The conclusion
Open in workbench →As stated, the theorem is too broad. In ordinary ZFC-based mathematics, every infinite set does contain a countably infinite subset, but without some form of the Axiom of Choice this is not generally true. In ZF, there can be infinite Dedekind-finite sets with no countably infinite subset, so the omitted assumption materially changes the claim.
Caveats
- The claim omits a load-bearing hypothesis: it is valid in ZFC, but not in bare ZF set theory.
- Without choice, an infinite set need not contain a countably infinite subset; Dedekind-finite counterexamples can exist.
- Many textbook or homework-style sources state the result without making their background axioms explicit.
Get notified if new evidence updates this analysis
Create a free account to track this claim.
Sources
Sources used in the analysis
A set which has a countably infinite subset is called Dedekind-infinite. Clearly every Dedekind-infinite set is infinite. Short answer: No. The statement that every infinite set is Dedekind-infinite is not provable in ZF (assuming ZF is consistent, of course). You don't need full AC, though. In fact, the equivalence isn't even as strong as countable choice.
The statement is independent of Zermelo-Fraenkel set theory (ZF) but true if you assume the axiom of choice. Consequently, deriving a proof of this claim within Zermelo-Fraenkel set theory with the axiom of choice (ZFC) can be quite complex, as it necessitates the use of the axiom of choice at some point.
We say a set is “Dedekind-finite” if there is no bijection between it and a proper subset. A set is “Dedekind-infinite” if it is not Dedekind-finite. If we assume the Axiom of Choice, being Dedekind-finite is equivalent to being in 1-1 correspondence with a natural number. However, without the Axiom of Choice, there may exist infinite Dedekind-finite sets; Dedekind-finite sets that contain more than n elements for all n ∈ ℕ. Lemma 1.1. Let X be a set. The following are equivalent definitions for “X is Dedekind-finite”: (1) There is no 1-1 correspondence between X and a proper subset of X. (2) X has no countably infinite subset.
If the axiom of choice holds, then a set is infinite if and only if it includes a countably infinite subset.
A set which has a countably infinite subset is called Dedekind Infinite. It is not provable within Zermelo-Fraenkel set theory (ZF) that every infinite set is Dedekind Infinite— that there is a bijection between it and a proper subset of itself. (This is not necessarily the same as "infinite" without choice.)
It should be noted that the weaker axiom of countable choice is sufficient to prove the stated theorem. Hence, T is a countably infinite subset of S.
Every infinite set contains a countably infinite subset. Every subset of a countable set is countable. Proof. Given an infinite set A, it suffices to construct an infinite sequence of distinct elements of A, for then the set {a1, a2, a3, ...} is a countably infinite subset of A.
A countably infinite set is a set that has the same size as the natural numbers or the integers. A countable set is a set that's either finite or countably infinite. Subsets of countable sets are countable.
A proof that shows that an infinite set has a countable subset. Is it as simple as taking arbitrary values of the finite set and listing them in their own ... A lemma: If a set is infinite, then it has an n-element subset for every natural number n.
A set is said to be Dedekind infinite iff it is equinumerous with a proper subset of itself. (Contrast this with the definition that a set is infinite if it is not equinumerous with any natural number.) ... Corollary: If A is Dedekind infinite, then it is infinite. ... The Dedekind-Pierce Theorem: A set is infinite iff it is Dedekind infinite. Proof: The only-if part was proven above. Now suppose A is infinite. Then ω ⪯ A, that is, there is an injection f : ω → A.
Definition. A set is said to be countably infinite if it is equinumerous with ℕ. A set is said to be countable if it is finite or countably infinite. ... In the nineteenth century, the mathematician Richard Dedekind used this curious property to define what it means to be finite. We can show that his definition is equivalent to ours, but the proof requires the axiom of choice. Definition. A set is A Dedekind infinite if A is equinumerous with a proper subset of itself, and Dedekind finite otherwise. Theorem. A set is Dedekind infinite if and only it is infinite.
A set is countable provided that it is finite or countably infinite. An infinite set that is not countably infinite is called an uncountable set. ... If A is a countably infinite set and B is a finite set, then A ∪ B is a countably infinite set.
The proof of the theorem uses the fact that every subset of N has a least element. For an infinite subset A of N, define psi(1) as the least element of A, then repeatedly choose the least element of the remaining set; this yields a bijection from N to A.
Definition 3.1. A set A is said to be countably infinite if |A| = |N|, and simply countable if |A| ≤ |N|. In words, a set is countable if it has the same cardinality as some subset of the natural numbers. ... if it is not finite, it must be countably infinite.
A posted solution says that every infinite set must have at least a countable subset, because you can always pick an infinite sequence of distinct elements from it. This is a community answer rather than a primary source.
Every infinite set contains a countable subset. Answer: Every infinite set contains a countable subset, which can be constructed by picking elements one by one and creating a bijection with the set of natural numbers.
By the lemma that every infinite set or that every non finite set so we're using we're trying to distinguish between non finite and infinite here and I mean non-finite so by the lemma every non finite set has some subset from ℕ to S which is an injection. The image of this map is the countably infinite subset that's guaranteed by the non finiteness of the set and that's the thing where we use the axiom of choice to produce that. ... Let me just recap again what we did is that we showed that for every non finite set we can produce a countably infinite subset and then using that we did this Hilbert Hotel trick to shift this countably infinite subset over and this produces a bijection to a proper subset.
We say a set is “Dedekind-finite” if there is no bijection between it and a proper subset. A set is “Dedekind-infinite” if it is not Dedekind-finite. If we assume the Axiom of Choice, being Dedekind-finite is equivalent to being in 1-1 correspondence with a natural number. However, without the Axiom of Choice, there may exist infinite Dedekind-finite sets; Dedekind-finite sets that contain more than n elements for all n in ℕ. In particular, a Dedekind-finite set has no countably infinite subset.
Every infinite set has an infinite countable subset | countable and uncountable sets | Adnan Alig.
What do you think of the claim?
Your challenge will appear immediately.
Challenge submitted!
For developers
This same pipeline is available via API.
Verify your AI's output programmatically.
/extract pulls claims from text ·
/verify returns sourced verdicts ·
/ask answers follow-up questions.
Continue your research
Verify a related claim next.
Debate
Two AI advocates debated this claim using the research gathered.
Argument for
Under standard mathematical frameworks that assume the Axiom of Choice, every infinite set is proven to contain a countably infinite subset, as established in Wikipedia (Source 4) and the Dedekind-Pierce Theorem detailed by Ohio State University (Source 10). This fundamental equivalence is further supported by Mathematics LibreTexts (Source 7) and Vaia (Source 16), which demonstrate that we can always construct a countably infinite subset from any infinite set by sequentially selecting distinct elements.
The Proponent's argument relies exclusively on Source 4 Wikipedia, Source 10 Ohio State University, Source 7 Mathematics LibreTexts, and Source 16 Vaia, each of which assumes the axiom of choice, while disregarding the ZF-independence result and existence of infinite Dedekind-finite sets documented in Source 1 MathOverflow, Source 3 LSA, and Source 5 Math StackExchange. The Proponent therefore commits an appeal to selective authority that leaves the universal claim unproven in the absence of choice.
Argument against
The claim is false because the statement that every infinite set contains a countably infinite subset is not provable in ZF alone and requires the axiom of choice, as shown by the existence of infinite Dedekind-finite sets with no countably infinite subset (Source 1 MathOverflow; Source 3 LSA; Source 5 Math StackExchange). Sources 2, 4, and 18 confirm this independence from ZF, directly contradicting the universal assertion in the claim.
The Opponent's argument relies on a strawman fallacy by restricting the mathematical universe to Zermelo-Fraenkel set theory (ZF) alone, ignoring that the standard framework of modern mathematics is ZFC, which includes the Axiom of Choice. Under this standard ZFC framework, the claim is universally true, as confirmed by Wikipedia (Source 4) and the Dedekind-Pierce Theorem (Source 10), which establish that every infinite set indeed contains a countably infinite subset.
Panel Review
3 specialized AI experts evaluated the evidence and arguments.
Reviewer 1 — The Logic Examiner
The claim that every infinite set contains a countably infinite subset is independent of Zermelo-Fraenkel (ZF) set theory and cannot be proven without assuming some form of the Axiom of Choice, as shown in Sources 1, 2, 3, and 5. Because the claim is presented as a universal mathematical truth but fails in standard ZF set theory where infinite Dedekind-finite sets can exist, it is logically classified as Mixed.
Reviewer 2 — The Source Auditor
High-authority, independent sources in the pool (1 MathOverflow; 3 University of Michigan REU paper) state that “every infinite set contains a countably infinite subset” is not provable in ZF and fails in some models of ZF because infinite Dedekind-finite sets exist, i.e., infinite sets with no countably infinite subset; Wikipedia (4) and several teaching notes (10, 11, 7) only support the claim under additional choice principles (AC or at least countable choice), not unconditionally. Because the atomic claim is stated without any assumption like AC/ZFC, the most reliable evidence indicates it is not universally true in standard foundational terms (ZF without choice), so the claim as written is false.
Reviewer 3 — The Precision Analyst
The claim's unqualified universal assertion that every infinite set contains a countably infinite subset does not match the evidence, which shows the statement holds in ZFC but is independent of ZF and fails for infinite Dedekind-finite sets (Sources 1, 3, 4, 5, 18). The wording therefore overstates the result by omitting the required axiom of choice, so only a qualified version is supported.