(June 15, 2020 at 8:03 pm)polymath257 Wrote:(June 15, 2020 at 3:21 pm)Fireball Wrote: Bolding mine. Can you run that past me, but at a slow walk? I never would have thought that this would be the case. I suspect that if I go look it up in a text the discussion will be way over my head.
Ok, let's go through a few of the basics first. We identify cardinality by looking at one-to-one correspondences between sets. We say that a set is countably infinite if it can be put into one-to-one correspondence with the set of natural numbers, N={0,1,2,..}. We say a set is countable if it is either finite or countably infinite.
There are three basic facts about countable sets that are important:
1. Any subset of a countable set is countable.
2. If you have a countable collection of sets, and each set is itself countable, then the union is countable.
3. Any set that is one-to-one correspondence with a countable set is itself countable.
Almost all countability arguments are based on using these three facts repeatedly. If you need me to prove them, I can, but for this, I'll take them as known.
We proceed by several steps:
Step I: the set of integers (positive, negative, and zero) is countable.In fact, the positive integers with zero is the same as the natural numbers and the negative integers can be put into a one-to-one correspondence with the naturals. So the collection of integers is the union of two countable sets, so by 2 above, it is countable.
Step II: The collection of linear functions with integer coefficients is countable. Such a function is of the form mx+n where m and n are integers. For each value of m, there are countably many values of n (corresponding with the integers). And the collection of all linear functions is the union as m varies, so is the union of countably many countable sets. Again, by 2, this is countable.
Step III: The collection of quadratic functions with integer coefficients is countable. Such a function is of the form kx^2 +mx+n where k, m, and n are integers. Now, for each value of k, there are only countably many values of m and n (linear functions!) and the collection of all quadratic functions is then the countable union (one set for each value of k) of countable sets (the linear piece). So, again by 2, the whole is a countable set.
Step IV: For each n, the collection of polynomials with integer coefficients of degree n is countable. This is done by induction on n. We have n=1 and n=2 by steps II and III. But the same argument as in step II shows that if the collection of polynomials of degree n is countable, so is the collection of degree n+1. Just take the union over the first coefficient of the possible following terms. So the induction works.
Step V: The collection of ALL polynomials with integer coefficients is countable. This is just the union over the the sets in step IV, one for each degree n. This is a countable union, and once again the result is countable.
Step VI: For each polynomial with integer coefficients, there are only finitely many roots. If the polynomial has degree n, then there are at most n roots. This is a fact from algebra. if you need me to prove it, let me know.
Step VII: the collection of all possible roots of all polynomials with integer coefficients (the collection of algebraic numbers) is countable: this is the union over the countably many polynomials of the finite (hence countable) set of roots for each.
The last step is *exactly* the set of numbers that are NOT transcendental.
Now, I assume you know that the set of all real numbers is NOT countable (once again, i can prove it if you want).
But this means that the collection of transcendental number is also NOT countable (if it was countable, its union with the algebraic numbers would be countable--but this is the whole set of real numbers).
If you have questions about any part of this, feel free to ask.
OK, thanks, I appreciate that you did my homework for me. I don't generally ask people to do that, but you've explained succinctly what I wanted to know. I'll trade you for an answer to a question you might have on auto repair, because I have a lot of experience with that. Not good with fuel injection, or many electronic ignition systems, because I graduated from uni and went to work as an engineer when those were becoming more commonplace.
I'll read this a couple more times so that the ideas are cemented into my head. It usually takes about three times before the bell goes, "ding!", but I get the gist of it. You've a clear expository style!
If you get to thinking you’re a person of some influence, try ordering somebody else’s dog around.