Question

Show that the two given sets have equal cardinality by describing a bijection from one to the other. Describe your bijection with a formula (not as a table). \(\\{0,1\\} \times \mathbb{N}\) and \(\mathbb{N}\)

Short answer

The function \(f: \{0, 1\} \times \mathbb{N} \rightarrow \mathbb{N}\) defined by \(f(x, n) = 2n + x\) is a bijection, thus showing that \(\{0,1\} \times \mathbb{N}\) and \(\mathbb{N}\) have the same cardinality.

Step-by-step solution

Define Function

A bijection can be described by a function which maps from the one set to the other and vice versa without any left-over elements. The function \(f: \{0, 1\} \times \mathbb{N} \rightarrow \mathbb{N}\) is defined as: \(f(x, n) = 2n + x\)

Prove Function Is Injective

An injective (or one-to-one) function maps distinct elements of the domain to distinct elements of the codomain. For all \(x_1, x_2 ∈ \{0,1\}\) and \(n_1, n_2 ∈ \mathbb{N}\), if \(f(x_1, n_1) = f(x_2, n_2)\), then \(x_1 = x_2\) and \(n_1 = n_2\). Thus, the function is injective.

Prove Function Is Surjective

A surjective (or onto) function maps from the domain to every element in the codomain. For any \(n ∈ \mathbb{N}\), there exists some \(x\) and \(y\) in \(\{0, 1\} \times \mathbb{N}\) such that \(f(x, y) = n\). Thus, the function is surjective.

Conclusion

Since the function \(f\) is both injective and surjective, it is a bijection. So, \(\{0,1\} \times \mathbb{N}\) and \(\mathbb{N}\) have the same cardinality.