Chapter 8

Prove that positive numbers of the form \(3 k+1\) are equinumerous with positive numbers of the form \(4 k+2\).

Can a diagonalization proof showing that the interval (0,1) is uncount- able be made workable in base-3 (ternary) notation?

Let \(F\) be the collection of all real-valued functions defined on the real line. Find an injection from \(\mathbb{R}\) to \(F\). Do you think it is possible to find an injection going the other way? In other words, do you think that \(F\) and \(\mathbb{R}\) are equivalent? Explain.

Prove that \(f(x)=c+\frac{(x-a)(d-c)}{(b-a)}\) provides a bijection from the interval \([a, b]\) to the interval \([c, d]\)

Prove that set equivalence is an equivalence relation.

In the proof of Cantor's theorem we construct a set \(S\) that cannot be in the image of a presumed bijection from \(A\) to \(\mathcal{P}(A)\). Suppose \(A=\\{1,2,3\\}\) and \(\mathrm{f}\) determines the following correspondences: \(1 \longleftrightarrow \emptyset\) \(2 \longleftrightarrow\\{1,3\\}\) and \(3 \longleftrightarrow\\{1,2,3\\}\). What is \(S ?\)

Prove that any two circles are equinumerous (as sets of points).

An argument very similar to the one embodied in the proof of Can- tor's theorem is found in the Barber's paradox. This paradox was originally introduced in the popular press in order to give laypeople an understanding of Cantor's theorem and Russell's paradox. It sounds somewhat sexist to modern ears. (For example, it is presumed without comment that the Barber is male.) In a small town there is a Barber who shaves those men (and only those men) who do not shave themselves. Who shaves the Barber? Explain the similarity to the proof of Cantor's theorem.

Determine a formula for the bijection from (-1,1) to the line \(y=1\) determined by vertical projection onto the upper half of the unit circle, followed by projection from the point (0,0) .

Verify that the final deduction in the proof of Cantor's theorem, " \((y \in\) \(S \Longrightarrow y \notin S) \wedge(y \notin S \Longrightarrow y \in S), "\) is truly a contradiction.