0

I understand how to prove it... but without any kind of rigorous mathematical proof, how could it be explained to a layman who understands countable sets that $\mathbb{Q}$ is in fact countable? I have seen from other posts on this site vague ideas, but none are as fulfilling as I would have hoped.

e.g. My closest idea was that if a rational number can be expressed as $\frac{p_i}{q_i}$, then do:

  1. Set $q_j=j$. For $i\in \mathbb{N}$, then do $\frac{\sum p_i}{q_j}$.

  2. Set $q_j=j+1$ do $\frac{\sum p_i}{q_{j+1}}$

etc .... although i'm not sure this quite works?

I think the above can be shown with examples to a layman quite easily, are there any other (simpler) ideas?

Andrés E. Caicedo
  • 79,201
Btzzzz
  • 1,113
  • In particular, the second highest answer has a beautiful proof by picture that is quite understandable. –  Apr 05 '18 at 01:19
  • @user296602 For sure, the picture is very interesting, but I would also like to look at other ideas too as my example shown in the question pretty much explains this image... most answers on this site talk about injectivity and basic set-theory, whereas not many for the intuition behind such an indispensable property. – Btzzzz Apr 05 '18 at 01:28

2 Answers2

1

My intuition is each rational can be represented by a pair of integers. $q = \frac ab$ so $q$ ~ $(a,b)$.

It doesn't matter that these pairs of if integers are not unique ($q$ ~ $(a,b)$ an $q$~ $(ka,kb)$, because that only serves to make the set of rationals smaller.

It makes sense that pairs of integers are countable because we can "weave" among them. We can list all the $(a,b)$ so that $a+ b = 0$; $(0,0)$. It doesn't matter that there is no $q = \frac 00$; that only means we have even fewer rationals to consider. The we can list all the $(a,b)$ so that $a+b= 1$; $(1,0),(0,1)$ and then so that $a+b = 2$ $(2,0),(1,1),(0,2)$ and so on. Listing all the $(a,b) = k$ is $(k,0), (k-1, 1), (k-2,2).... (0,k)$ and this way we can list them all.

Done.....

Except I didn't take into account that $q$ could be negative.

Well that doesn't matter. Will just list one positive, and then one negative, and so on and go through them all.

fleablood
  • 124,253
0

I think that someone without a significant grounding in mathematics will not accept that there are different cardinalities of infinity, and that just because you can put a set in bijection with the natural numbers it must have the same cardinality. It was certainly a controvercial idea went Cantor suggested it in the tail end of the 19th century.

If you can get passed the definition of countable sets, I don't think that what you offer is simpler for the layman to accept than the classic explanation.

Doug M
  • 57,877