Both the set of natural numbers and the set of integers are infinite in size. Amazingly, though, they’re exactly the same size. In this blog post, we’ll explore a technique for showing that these two infinite-sized sets have equal cardinality: creating a bijection between them. We’ll use this technique to show that, counter to all intuition, there are exactly as many natural numbers as there are integers.
Tag: proofs
The Pigeonhole Principle and Hash Tables
This blog post describes what the pigeonhole principle states, demonstrates how to prove its correctness by contrapositive, then applies the pigeonhole principle to the hash table data structure. After reading this post, you should understand how to prove the pigeonhole principle, and recognize situations in computer science where it applies.
Reversing Your Approach to Induction
After reading this post, you should feel comfortable writing proofs by induction in the order of inductive step first, followed by base cases. You should be able to use this method of writing proofs to identify the correct base cases in problems where it is not clear how many or which base cases are necessary.
Begging the Question in Proofs
Begging the question is a subtle mistake. Let’s explore it in more detail in today’s blog post. After reading this post, you should be able to recognize if you are begging the question in one of your proofs, and be able to restructure a proof to correct this logical error.