[Math] Prove that if $A \subseteq B$ and B is countable, then $A$ is either countable or finite.

proof-verificationreal-analysis

I am currently taking a Real Analysis course and am just coming off an F on my first exam, so I am feeling extremely apprehensive about my already poor ability to write proofs. I am sure a question like this has been asked at some point in the past, but I wanted to try and figure things out myself to try and build my confidence back up again, so I am just looking for feedback on a proof that I have come up with for this proposition.

Proof: Suppose $A \subseteq B$ and $B$ is countable. $A \subseteq B \Rightarrow A \leq B$, and if $B$ is countable then $\mathbb{N} \cong B$, so there exists $f:\mathbb{N} \rightarrow B$, where $f$ is one-to-one and onto. If $A=B$ then $A$ is countable since $B$ is countable. If $A<B$ then $A$ is a proper subset of $B$ which implies that a subset of $\mathbb{N}$ must also map to $A$, so $A$ is countable. Therefore, if $A \subseteq B$ and $B$ is countable, then $A$ is countable. $ \square$

I have this feeling that I didn't actually prove anything here, but that could also be my lack of confidence at the moment. I am also unsure if I need to address the "or finite" part of the proof. I feel that $A$ being countable or finite is dependent upon the nature of $B$. If $B$ was countably infinite then $A$ would be countable, and if $B$ was finite then $A$ would be finite as well. Again, I am not sure if this matters since we weren't told anything about $B$ in regards to whether or not it is countably infinite or finite… and if it does matter, I am not sure how I would organize it into my proof.

Best Answer

$A$ is countable iff there is a function $f : A \to \omega$ such that $f$ is one-to-one(not necessarily onto) if $A$ is finite.

Let $ Id_A : A \to A$ is one-to-one and one can make the image bigger without effecting one-to-one propriety $Id_A : A \to B$ and $ g: B \to \omega$ such that $g$ is one-to-one, then simply take $ f = g(Id_A) : A \to \omega$ and its not hard to prove that $f$ is one_to_one.

Assume $x,y \in A$ and $f(x) =f(y) $ and we need to prove that $ x =y$

$f(x) = g(Id_A(x)) = g(x) = g(y) = g(Id_A(y)) = f(y)$, which means that $ g(x) =g(y)$ which means that $x=y$ because we know that $g$ is one_to_one.

Related Question