Countable or uncountable

Question

(1) $C$ is the set of all circles $C(z,r)$ with $z\in\mathbb{Q}\times\mathbb{Q}$ and $r\in\mathbb{Q}^+$. What is the cardinality of $C$?

(2) Let $S$ be the set of all sequences $X=\{X_n\}_{n=1}^\infty$ such that $X_n\in\{0,1,2\}$ for all $n$. Show that $S$ is uncountable.

(3) A function $f:\mathbb R \to \mathbb R$ has a proper local maximum at $a$ if there exists an interval $(b,c)$ such that $b<a<c$ and $f(x)<f(a)$ for all $b<x<c$, $x\neq a$. Denoting by $M$ the set of all proper local maxima, show that $M$ is countable.

No clue for these, any hint?

Answer 1

For (1), the number of possible centres of circles is countable and the number of possible radii is countable. What does that mean for the set $C$?

For (2), are you familiar with Cantor's diagonal argument? It's very similar to what you're trying to show.

For (3), edit: just see the other answer.

Answer 2

HINTS:

1. You have one circle for each triple $\langle p,q,r\rangle\in\Bbb Q\times\Bbb Q\times\Bbb Q^+$. You know that $\Bbb Q$ is countable. What do you know about the cardinality of $S\times S$ when $S$ is countable?

2. Look at the subset $Y$ of $X$ consisting of just the sequences whose terms are all $0$ or $1$. If $y=\langle y_n:n\in\Bbb N\rangle$ is such a sequence, let $A_y=\{n\in\Bbb N:y_n=1\}$. Show that the map $y\mapsto A_y$ is a bijection from $Y$ to $\wp(\Bbb N)$. Is $\wp(\Bbb N)$ countable, or uncountable?

3. You know that for each $a\in M$ there are $b_a<a$ and $c_a>a$ such that $f(x)<f(a)$ whenever $b_a<x<a$ or $a<x<c_a$. You can always choose $b_a$ and $c_a$ to be rational numbers. (Why?) Assume that we’ve done so. There are only countably many pairs $\langle p,q\rangle$ of rational numbers with $p<q$. (Why?) Thus, $\{\langle b_a,c_a\rangle:a\in M\}$ is countable. If $M$ is uncountable, that means that there must be some pair $\langle p,q\rangle$ of rational numbers such that $b_a=p$ and $c_a=q$ for uncountably many points $a\in M$. Let $a_1$ and $a_2$ be distinct points of $(p,q)\cap M$. Explain why we must have both $f(a_1)<f(a_2)$ and $f(a_2)<f(a_1)$. Of course this is impossible, so when you’ve done all that, you’ll have shown that $M$ cannot be uncountable and must therefore be countable.