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). \(\mathbb{Z}\) and \(S=\left\\{\ldots, \frac{1}{8}, \frac{1}{4}, \frac{1}{2}, 1,2,4,8,16, \ldots\right\\}\)

Short answer

The function \(f(n) = 2^n\) formulates a bijection between the set of integers \(\mathbb{Z}\) and the set \(S\), proving that these two sets have equal cardinality.

Step-by-step solution

Understand sets

The set \(\mathbb{Z}\) consists of all integers: \(\ldots, -2, -1, 0, 1, 2, \ldots\). The set \(S\) is made up of all positive and negative powers of 2: \(\ldots, 1/8, 1/4, 1/2, 1, 2, 4, 8, \ldots\). We need to find a function that takes an integer and produces a unique power of 2, and vice versa.

Find a possible bijection

A function that could serve as a bijection is \[f(n) = 2^n\] for \(n \in \mathbb{Z}\). This function maps each integer \(n\) to a unique power of 2. Positive integers are mapped to positive powers of 2, negative integers are mapped to the reciprocals of positive powers of 2, and zero is mapped to 1.

Analyze the function

\(f(n) = 2^n\), you will see that it covers all elements in set \(S\). Therefore, the function \(f\) is a bijection between the sets \(\mathbb{Z}\) and \(S\).

Verify the bijection

To verify that \(f\) is a bijection, we need to show that it is both injective (each value in the domain maps to a unique value in the range) and surjective (every value in the range is mapped to by some value in the domain). The function \(f(n) = 2^n\) is injective because for any two different integers \(n\) and \(m\), \(2^n\) and \(2^m\) are different. The function is surjective because for any number in form of \(2^n\) or \(1/2^n\) in \(S\), there exist an integer \(n\) in \(\mathbb{Z}\) such that \(2^n\) is equal to the number.