Math 2.0

Mathematical logic and foundations Proof

Proof that the integers are countable

Builds on Countably infinite setBijective functionInjective functionSurjective functionDivision algorithm

Proof

We check that the given map is injective and surjective.

  1. Each n∈ℕn \in \N is either 2k2k or 2k+12k + 1 for exactly one k∈ℕk \in \N, by the division algorithm with divisor 22. So f(2k)=kf(2k) = k and f(2k+1)=−(k+1)f(2k+1) = -(k+1) define a function f ⁣:ℕ→ℤf \colon \N \to \Z.
  2. For even n=2kn = 2k, f(n)=k≥0f(n) = k \ge 0. For odd n=2k+1n = 2k + 1, f(n)=−(k+1)≤−1f(n) = -(k + 1) \le -1.
  3. The map ff is injective. Let f(n)=f(n′)f(n) = f(n'). By step 2, nn and n′n' are both even or both odd.
  4. If n=2kn = 2k and n′=2k′n' = 2k', then k=k′k = k', so n=n′n = n'. If n=2k+1n = 2k + 1 and n′=2k′+1n' = 2k' + 1, then −(k+1)=−(k′+1)-(k+1) = -(k'+1), so k=k′k = k' and n=n′n = n'.
  5. The map ff is surjective. Let m∈ℤm \in \Z. If m≥0m \ge 0, then f(2m)=mf(2m) = m.
  6. If m<0m < 0, put k=−m−1k = -m - 1. Then k∈ℕk \in \N, and f(2k+1)=−(k+1)=mf(2k + 1) = -(k + 1) = m.
  7. So ff is a bijection from ℕ\N to ℤ\Z, and ℤ\Z is countably infinite.

Idea

List the integers as 0,−1,1,−2,2,…0, -1, 1, -2, 2, \dots. The even positions hold the nonnegative integers and the odd positions hold the negative ones. Each integer appears exactly once in this list.

Reading path

To understand this page from the ground up, read these 37 pages in order. The foundations come first. The path takes the proofs Proof of the commutativity of addition by induction, Proof of strong induction from ordinary induction, Proof of the well-ordering principle from strong induction, Proof of the division algorithm.

Show the path as a graph
Definition by recursion, concept, no evidence levelDefinition by recursi…conceptDivisibility, definition, no evidence levelDivisibilitydefinitionElement, definition, no evidence levelElementdefinitionMathematical induction, concept, no evidence levelMathematical inductionconceptNatural numbers, object, no evidence levelNatural numbersobjectPeano axioms, concept, no evidence levelPeano axiomsconceptProposition, concept, no evidence levelPropositionconceptSet, definition, no evidence levelSetdefinitionSuccessor function, definition, no evidence levelSuccessor functiondefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionAddition of natural numbers, definition, no evidence levelAddition of natural n…definitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionThe successor function is injective, statement, no evidence levelThe successor functio…statementUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionZero is not a successor, statement, no evidence levelZero is not a success…statementCartesian product, definition, no evidence levelCartesian productdefinitionProof of the commutativity of addition by induction, proof, no evidence levelProof of the commutat…proofSubset, definition, no evidence levelSubsetdefinitionOrder on the natural numbers, definition, no evidence levelOrder on the natural …definitionUniqueness quantifier, definition, no evidence levelUniqueness quantifierdefinitionBinary relation, definition, no evidence levelBinary relationdefinitionCommutativity of addition, statement, no evidence levelCommutativity of addi…statementProof of strong induction from ordinary induction, proof, no evidence levelProof of strong induc…proofFunction, definition, no evidence levelFunctiondefinitionStrong induction, statement, no evidence levelStrong inductionstatementCodomain, definition, no evidence levelCodomaindefinitionInjective function, definition, no evidence levelInjective functiondefinitionProof of the well-ordering principle from strong induction, proof, no evidence levelProof of the well-ord…proofSurjective function, definition, no evidence levelSurjective functiondefinitionWell-ordering principle, statement, no evidence levelWell-ordering princip…statementBijective function, definition, no evidence levelBijective functiondefinitionProof of the division algorithm, proof, no evidence levelProof of the division…proofCountably infinite set, definition, no evidence levelCountably infinite setdefinitionDivision algorithm, statement, no evidence levelDivision algorithmstatementProof that the integers are countable, proof, no evidence levelProof that the intege…proof
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. Definition by recursion concept
  2. Divisibility definition
  3. Element definition
  4. Mathematical induction concept
  5. Natural numbers object
  6. Peano axioms concept
  7. Proposition concept
  8. Set definition
  9. Successor function definition
  10. Implication definition
  11. Predicate definition
  12. Ordered pair definition
  13. Addition of natural numbers definition
  14. Existential quantifier definition
  15. The successor function is injective statement
  16. Universal quantifier definition
  17. Zero is not a successor statement
  18. Cartesian product definition
  19. Proof of the commutativity of addition by induction proof
  20. Subset definition
  21. Order on the natural numbers definition
  22. Uniqueness quantifier definition
  23. Binary relation definition
  24. Commutativity of addition statement
  25. Proof of strong induction from ordinary induction proof
  26. Function definition
  27. Strong induction statement
  28. Codomain definition
  29. Injective function definition
  30. Proof of the well-ordering principle from strong induction proof
  31. Surjective function definition
  32. Well-ordering principle statement
  33. Bijective function definition
  34. Proof of the division algorithm proof
  35. Countably infinite set definition
  36. Division algorithm statement
  37. Proof that the integers are countable proof

Where this leads

9 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Countable_set, Introduction
About this page
TagBVDCFVVCJ8
URIm2://BVDCFVVCJ8
Kindproof
WritingW0 stub
MSC03E10
ProvesThe integers are countable
UsesCountably infinite set, Bijective function, Injective function, Surjective function, Division algorithm
Changed4 November 2026

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.