Math 2.0

Mathematical logic and foundations Theorem

Every infinite set has a countably infinite subset

Builds on Infinite setCountably infinite setInjective functionAxiom of choice

Statement

Assume the axiom of choice. Let AA be an infinite set. Then there is an injective function f ⁣:ℕ→Af \colon \mathbb{N} \to A, so AA has a countably infinite subset f(ℕ)f(\mathbb{N}).

Remarks

The proof chooses a0∈Aa_0 \in A, then a1∈A∖{a0}a_1 \in A \setminus \{a_0\}, and so on. Each set A∖{a0,…,an}A \setminus \{a_0, \dots, a_n\} is nonempty because AA is infinite. The axiom of countable choice is enough, but some choice is needed: in ZF alone, the statement cannot be proved. It follows that ℵ0\aleph_0 is the least infinite cardinal.

Reading path

To understand this page from the ground up, read these 28 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionProposition, concept, no evidence levelPropositionconceptSet, definition, no evidence levelSetdefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionFamily of sets, definition, no evidence levelFamily of setsdefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionUnion, definition, no evidence levelUniondefinitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionUnion of a family of sets, definition, no evidence levelUnion of a family of …definitionUniqueness quantifier, definition, no evidence levelUniqueness quantifierdefinitionBinary relation, definition, no evidence levelBinary relationdefinitionFunction, definition, no evidence levelFunctiondefinitionCodomain, definition, no evidence levelCodomaindefinitionInjective function, definition, no evidence levelInjective functiondefinitionChoice function, definition, no evidence levelChoice functiondefinitionSurjective function, definition, no evidence levelSurjective functiondefinitionAxiom of choice, statement, no evidence levelAxiom of choicestatementBijective function, definition, no evidence levelBijective functiondefinitionCountably infinite set, definition, no evidence levelCountably infinite setdefinitionEquinumerous sets, definition, no evidence levelEquinumerous setsdefinitionFinite set, definition, no evidence levelFinite setdefinitionInfinite set, definition, no evidence levelInfinite setdefinitionEvery infinite set has a countably infinite subset, statement, no evidence levelEvery infinite set ha…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Proposition concept
  3. Set definition
  4. Disjunction definition
  5. Implication definition
  6. Predicate definition
  7. Family of sets definition
  8. Ordered pair definition
  9. Union definition
  10. Existential quantifier definition
  11. Universal quantifier definition
  12. Cartesian product definition
  13. Subset definition
  14. Union of a family of sets definition
  15. Uniqueness quantifier definition
  16. Binary relation definition
  17. Function definition
  18. Codomain definition
  19. Injective function definition
  20. Choice function definition
  21. Surjective function definition
  22. Axiom of choice statement
  23. Bijective function definition
  24. Countably infinite set definition
  25. Equinumerous sets definition
  26. Finite set definition
  27. Infinite set definition
  28. Every infinite set has a countably infinite subset statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Infinite_set, Properties
About this page
Tag0RWQ5VZ6VQ
URIm2://0RWQ5VZ6VQ
Kindstatement, theorem
WritingW0 stub
MSC03E10
StatusThis copy of the site has no build data. Run m2 status 0RWQ5VZ6VQ.
UsesInfinite set, Countably infinite set, Injective function, Axiom of choice

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.