Countability of $\{S\subseteq \Bbb Q:\;\text{S is finite}\}$

Question

I was given the following problem on a test and provided the proof below. My professor says there is an error in my logic (which I'll identify later) but I respectfully disagree and am looking for a second opinion.

I'm asked to consider the following set $A$ and prove that $|A|=|\Bbb Q|$.

$$A=\{S\subseteq \Bbb Q:\;\text{S is finite}\}$$

To show that $|A|\ge|\Bbb Q|$, I said consider the following subset $B$ of $A$:

$$B=\{S\subseteq \Bbb Q: |S|=1\}$$

The set $B$ consists of elements which are sets of cardinality $1$. This means $\forall\;x\in \Bbb Q$, $\{x\}\in B$. Since $B\subseteq A$, $|A|\ge|\Bbb Q|$. She gave credit for this part, but the next was where we disagreed.

To show $|A|\not>|\Bbb Q|$, I offered the following:

Consider a finite subset of $\Bbb Q$ with cardinality $\le n$. This subset is comparable to an ordered pair in $\Bbb Q^n$. E.g. if $n=4$, we have the following:

$$\{a,b,c,d\}\text{ is comparable to } (a,b,c,d) \text{ in }\Bbb Q^4$$

For subsets of cardinality $p$ less than four, I said one could simply repeat the last entry $n-p$ times since sets require unique elements but ordered pairs do not.

$$\{a,b\}\text{ is comparable to }(a,b,b,b)\text{ in }\Bbb Q^4$$

In each case , the ordered pair in $\Bbb Q^n$ is unique, implying injectivity.

Thus, my solution simply found an injection from $A$ to $\Bbb Q^n$ and utilised the fact that the Cartesian product of countable sets is countable to show that $|A|\le|\Bbb Q|\implies|A|=|\Bbb Q|$.

However, my professor claimed that this does not necessarily hold for sufficiently large $n$. She compared my work to the false proof that the sum of naturals is finite because each time you add the next natural to the previous sum, you're adding a finite number to a finite sum.

I disagree because no matter how large $n$, this is still comparable to $\Bbb Q^n$.

I normally would never have the confidence to disagree with her as she's an extremely good professor, but I feel like my approach is valid and want to see if anyone else does.

Answer 1

I'm not sure if this is a complete answer, but I would like to point out two main issues that I see in your proof (which rests on some good ideas, though!).

First, as mentioned in the comments, the mapping you describe, is not a function, since two equal sets like $\{1,2,3\}$ and $\{3,2,1\}$ are mapped to two different tuples, namely $(1,2,3)$ and $(3,2,1)$, respectively. Thus, as you suggested, you have to identify equal sets somehow. For example, by ordering the elements. The mathematical concept behind that is called "equivalence relation". To avoid this, you can simply go the other way round and define a surjective function by mapping a tuple to the set of its elements.

The second problem is the $n$. I think what you wanted to do is something like this: Fix $n\in\mathbb N$ and define $A_n:=\{S\subset\mathbb Q\ |\ |S|=n\}$ (you can also use $|S|\leq n$, the result is the same). Then, with one of the abovementioned methods, you show that $|A_n|\leq|\mathbb Q|$. Although this is true for any $n$, you now have to say what each individual $A_n$ has to do with $A$. You cannot say something like $A_n=A$, because $n$ is an arbitrary large natural whatever. You can pick arbitrary large $n$, but once such an $n$ is picked, it is and stays a finite (possibly very large but still finite) natural number until the end of days. To finish we could do something like this: Since $A=\bigcup_{n\in\mathbb N}A_n$ is a countable union of countable sets we conclude $|A|\leq|\mathbb Q|$.

I hope that this helps a little, and I think that last point is what your professor meant when she complained about the "large" $n$. If you have any questions, pls don't hesitate to ask.

Answer 2

I think you can argue as follows: enumerate the rationals in some way $\left \{ r_1,r_2,\cdots \right \}$ and list the primes in order $\left \{ p_1,p_2,\cdots \right \}=\left \{ 2,3,\cdots \right \}.$ Now, $A=\bigcup _nA_n$ where $A_n=\{S\subseteq \Bbb Q: |S|=n\}.$

Write $r_i=\frac{s_i}{t_i}:s_i,t_i\in \mathbb N$ in lowest terms. Notice that if $r_i\neq r_j$ then either $s_i\neq s_j$ or $t_i\neq t_j.$ Then, $\left ( \frac{s_{i_1}}{t_{i_1}},\cdots, \frac{t_{i_n}}{t_{i_n}} \right )\mapsto p_{i_1}^{s_{i_1} t_{i_1}}\times\cdots \times p_{i_n}^{s_{i_n} t_{i_n}}$ injects $A_n$ into $\mathbb N$ and it follows that $A$ is countable.

Answer 3

"Thus, my solution simply found an injection from A to $Q^n$ "

No, it didn't.

How do you map $S$ so that $|S| = n+1$ into $\mathbb Q^{n}$?

You've only mapped all $S$ so that $|S| = 1$ to $\mathbb Q^1$ and all $S$ so that $|S| \le n$ into $\mathbb Q^n$ but you sure as heck haven't shown that you can map all $S$ so that $|S|$ is finite into some $\mathbb Q^n$.

What if $|S|$ is much much larger than your $n$?

You've proven that $A_n = \{S \subset \mathbb Q| |S| \le n\}$ is countable for all $n \in \mathbb N$.

But $A =\{S \subset \mathbb Q| S \text{ is finite}\}\ne S_n$ for any $n$.

This is exactly the same as proving that $A_n = \{k \in \mathbb N| k \le n\}$ is finite so $A = \{k \in \mathbb N \}$ is finite.

You need to argue that $A = \cup_{n\in \mathbb N} A_n$ and that the countable union of countable sets is countable.