Exercise · ZW-COUNTABLE-SET-010 · ★★★ Advanced
Which of these functions is a bijection from \(\mathbb{N}\times\mathbb{N}\) onto \(\mathbb{N}\)?
Choose one option.
Show answer
- A. \(f(m,n)=\frac{(m+n)(m+n+1)}{2}+n\)
Explanation
Cantor's function \(\frac{(m+n)(m+n+1)}{2}+n\) runs through the diagonals \(m+n=k\) in order and is a bijection. The product \(m\cdot n\) and the sum \(m+n\) repeat values, and \(2^m3^n\) never reaches \(5\).
Review the concept: Countable set
A set is countable if it is finite or equipotent to \(\mathbb{N}\), that is, if its elements can be listed in a sequence.
\[A \text{ numerable} \iff A \text{ finito} \lor A\sim\mathbb{N}\]
More practice problems: countable set
- ZW-COUNTABLE-SET-001 What does it mean for a set A to be countable?
- ZW-COUNTABLE-SET-002 Which of these sets is countable?
- ZW-COUNTABLE-SET-003 What is a set equipotent to ℕ called?
- ZW-COUNTABLE-SET-004 What is an enumeration of a countably infinite set A?
- ZW-COUNTABLE-SET-005 Is a finite set countable?
- ZW-COUNTABLE-SET-006 Which of these functions is a bijection from ℕ onto ℤ?
- ZW-COUNTABLE-SET-007 Is ℕ×ℕ countable?
- ZW-COUNTABLE-SET-008 Is ℚ countable?