Hints to exercises
Any set with exactly three natural numbers is in the equivalence class of \(\{1,2,3\}.\)
Use the fact that \(A\) and \(B\) are equivalent precisely when there is a bijection from \(A\) to \(B.\)
This exercise is more interesting if countable means finite or the size of the naturals.
There are only two uncountable sets in the list.
\(f(n) = 4\left(\frac{n-1}{3}\right) + 2\) is a bijection from \(\{3k+1 {\,:\,}k \in {\mathbb N}\}\) to \(\{4k+2 {\,:\,}k \in {\mathbb N}\}.\)
One can show injectivity by showing that the function is strictly increasing. For surjectivity, note that every element in \([c,d]\) can be written as \((1-\lambda) c + \lambda d\) for some \(\lambda \in [0,1].\)
Use the fact that every point on a circle on the \(x\)-\(y\) plane with radius \(r\) centered at \((p,q)\) can be written as \((p+r\cos \theta, q+r\sin \theta)\) for some \(\theta \in [0,2 \pi).\)
If \(a \in (-1,1),\) then the vertical projection onto the upper half of the unit circle is the point \((a, \sqrt{1-a^2})\) whose projection from the point \((0,0)\) is given by the intersection of the lines defined by \(y = 1\) and \(a y - \sqrt{1-a^2} x = 0.\)
\(f(x,y) = \left( \frac{x}{\sqrt{1-x^2-y^2}}, \frac{y}{\sqrt{1-x^2-y^2}}, 1 \right)\) is a bijection from the unit disc in the \(x\)-\(y\) plane to the plane \(z = 1\) in \({\mathbb R}^3.\)
There are different ways to do this. One way is to replace an odd digit with 0 and an even digit with 1. The number thus constructed is different from every number on the list.
Yes.
Since \(S\) is defined as \(\{x \in A {\,:\,}x \notin f(x)\},\) we can go through each \(x\) in \(A\) one by one to see if \(x \notin f(x).\) Now, \(f(1) = \emptyset\) and \(1 \notin \emptyset.\) So \(1 \in S.\) \(f(2) = \{1,3\}\) and \(2 \notin \{1,3\}.\) So \(2 \in S.\) \(f(3) = \{1,2,3\}\) but \(3 \in \{1,2,3\}.\) So \(3 \notin S.\) Thus, \(S = \{1,2\}.\)
Let \(U\) denote the set of all men. Let \(P(x,y)\) denote the proposition that \(x\) shaves \(y.\) Thus, a man \(x\) shaves himself if and only if \(P(x,x)\) is true. Such a barber exists if and only if the following statement holds: \(\exists x \in U, \forall y \in U, P(x,y) \iff \lnot P(y,y).\) How does one obtain a contradiction from this?
Can the set of all sets contain the power set of itself?
Let \(P\) denote the proposition \(y \in S.\) Then \(\lnot P\) is \(y \notin S.\) The contradiction should now be easy to see.
First, move the guest in room \(i\) to room \(2i\) for \(i =1,2,3,\ldots\) all at the same time, thus leaving rooms \(1,3,5,\ldots\) vacant. Then, move new guest \(i\) to room \(2i-1\) for \(i = 1,2,3,\ldots.\)
For each real number \(\alpha,\) let \(f_\alpha\) denote the function that maps \(\alpha\) to \(1\) and every other real number to \(0.\) Then \(f_\alpha = f_\beta\) if and only if \(\alpha = \beta.\) Then \(g : {\mathbb R}\rightarrow F\) given by \(g(\alpha) = f_\alpha\) for every \(\alpha \in Reals\) is an injection.
\({\mathbb R}\) and \(F\) are not equivalent. To see this, try to construct an injection from \({\mathcal P}({\mathbb R})\) to \(F.\)
Dominance is reflexive since the identity function is an injection from a set to itself. Dominance is transitive because if \(f\) is an injection from \(A\) to \(B\) and \(g\) is an injection from \(B\) to \(C,\) then \(g\circ f\) is an injection from \(A\) to \(C.\) Dominance is anti-symmetric because if \(|A| \leq |B|\) and \(|B| \leq |A|,\) then \(|A| = |B|\) by the Cantor-Bernstein-Schröder theorem.
An injection from \({\mathbb Z}\) to \({\mathbb Q}\) is given by the identity function.