Re: less-than-uncool preschool
Reply #151 – July 25, 2016, 06:03:21 AM

It's pretty easy to show that a union of a finite number of countable sets is countable. But let's consider Cartesian products. If A and B are both finite sets, then the Cartesian product A × B is also finite. In particular, if A ∼ {k ∈ ℕ | k ≤ m } and B ∼ {k ∈ ℕ | k ≤ n }, then A × B ∼ {k ∈ ℕ | k ≤ mn }. That's pretty easy to show. If A is finite and B is denumerable, or vice-versa, then A × B is denumerable. That's pretty easy too. What's more interesting is that if A and B are both denumerable, then again A × B is denumerable. Let the elements of A be listed as a _{1} , a _{2} , a _{3} , etc. Let the elements of B be listed as b _{1} , b _{2} , b _{3} , etc. Then consider the following arrangement of ordered pairs: (a _{1} , b _{1} ), (a _{2} , b _{1} ), (a _{3} , b _{1} ), ... (a _{1} , b _{2} ), (a _{2} , b _{2} ), (a _{3} , b _{2} ), ... (a _{1} , b _{3} ), (a _{2} , b _{3} ), (a _{3} , b _{3} ), ... ⋮ ⋮ ⋮ ⋱ We can list these ordered pairs by starting from the upper-left corner, then making a bunch of diagonal stripes from upper right to lower left, with each stripe getting successively further away from the starting corner. Thus, we get the pairs arranged in the following order: (a _{1} , b _{1} ), (a _{2} , b _{1} ), (a _{1} , b _{2} ), (a _{3} , b _{1} ), (a _{2} , b _{2} ), (a _{1} , b _{3} ), (a _{4} , b _{1} ), (a _{3} , b _{2} ), (a _{2} , b _{3} ), (a _{1} , b _{4} ), .... So A × B is denumerable. More generally, a Cartesian product of a finite number of countable sets is countable, as can be shown by induction.