Problem 18, then prove that \(\mathbb{N}\) and \(\mathbb{Z}\) have the same cardinality. (the relevant function is \(f(n)=((-1)^n(2n-1)+1)/4\))
Problems 11, 12: consider the functions \(\theta(a,b)=(-1)^ab\) and \(\theta(a,b)=a-2ab+b\) from from \(\{0,1\}\times\mathbb{N}\) to \(\mathbb{Z}\). Are they injective? surjective? bijective?
Prove that if \(g\circ f\) is injective, then \(f\) is injective. Prove that if \(g\circ f\) is surjective, then \(g\) is surjective. Give counterexamples showing that \(g\circ f\) can be injective but \(g\) not injective, and \(g\circ f\) is surjective by \(f\) is not surjective.
Give an example of a countable subset of the irrational numbers, or prove that no such subset exists.
How many surjective maps are there from a 3 element set to a 2 element set? From a 4 element set to a 3 element set?
Go through the argument that \(\mathbb{N}\times\mathbb{N}\) is countable (Figure 14.2)
Go through Cantor’s diagonalization argument proving that (for example) infinite sequences form an uncountable set. See pp. 271-272 and also Gilbert and Vanstone Theorem 6.67.
Let \(A\) be the set of sequences of natural numbers \(a_1,a_2,a_3,\ldots\) that are eventually constant at zero – in other words, a sequence \(a_1,a_2,\ldots\) is in \(A\) if there exists an \(N\) such that \(a_i=0\) for all \(i\ge N\). Is \(A\) countable?
Prove that the intervals \((0,1)\) and \((a,b)\) in \(\mathbb{R}\) have the same cardinality for any \(a,b\) with \(b>a\).
Give 3 examples of functions that are surjective but not injective, and 3 examples of functions that are injective but not surjective
Two tricky problems from Gilbert and Vanstone.
Prove that a function \(f:X\to Y\) is injective if and only if, given two maps \(g:T\to X\) and \(h:T\to X\), \[ f\circ g:T\to X = f\circ h:T\to X \implies g=h. \]
If \(f:A\to B\) and \(g:B\to C\) are bijective maps, prove that the inverse map to \(f\circ g\) is \(g^{-1}\circ f^{-1}\).