Math 2.0

Mathematical logic and foundations Theorem

Countable union of countable sets is countable

Builds on Countable setUnion of a family of setsProduct of countable sets is countableAxiom of choice

Statement

Assume the axiom of choice. Let II be a countable set and let (Ai)i∈I(A_i)_{i \in I} be a family of sets such that each AiA_i is countable. Then the union ⋃i∈IAi\bigcup_{i \in I} A_i is countable.

Remarks

Proof: choose for each ii a surjection from ℕ\mathbb{N} onto AiA_i, when AiA_i is nonempty. Together they give a surjection from a subset of ℕ×ℕ\mathbb{N} \times \mathbb{N} onto the union, and ℕ×ℕ\mathbb{N} \times \mathbb{N} is countable. The proof uses the axiom of countable choice to choose the surjections. Without any choice, the statement cannot be proved in ZF. When the enumerations of the AiA_i are given, no choice is needed.

Reading path

To understand this page from the ground up, read these 27 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 choicestatementCountable set, definition, no evidence levelCountable setdefinitionBijective function, definition, no evidence levelBijective functiondefinitionCantor pairing function, example, no evidence levelCantor pairing functi…exampleProduct of countable sets is countable, statement, no evidence levelProduct of countable …statementCountable union of countable sets is countable, statement, no evidence levelCountable union of co…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. Countable set definition
  24. Bijective function definition
  25. Cantor pairing function example
  26. Product of countable sets is countable statement
  27. Countable union of countable sets is countable statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Countable_set, Formal overview
About this page
Tag0Z8FM54P86
URIm2://0Z8FM54P86
Kindstatement, theorem
WritingW0 stub
MSC03E10
StatusThis copy of the site has no build data. Run m2 status 0Z8FM54P86.
UsesCountable set, Union of a family of sets, Product of countable sets is countable, 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.