11–20 of 32 posts
This is the first time I've seen this way to show that Q does not have a higher cardinality than N, is it a common method? I don't remember exactly how I learned about it in high school, infinity cardinalities have rarely come up since then, but it was some other method or at least another form of presentation, i.e. symbols and prose.
> But what would be an example of an uncomputable number? That’s a good question. Most obviously, we could be talking about numbers that encode the solution to the halting problem. It would lead to a paradox to have a computer program that allows us to decide, in the general case, whether a given computer program halts. So, if a procedure to approximate a particular real requires solving the halting problem, we can’t…
Busy beavers are a classic example. They're mostly-hypothetical numbers that tell you "if any Turing machine of size s runs for longer than this, it doesn't halt." There's a link to that in the sentence you quoted.
> Of course, we don’t teach about computable numbers in school. Instead, the most common “upgrade” from ℚ are reals: While "computable" numbers are a recent concept, already for a few centuries, since the early 18th century, mathematics has taught about another set of numbers intermediate between rational numbers and "real" numbers: the algebraic numbers, which are a subset of the computable numbers. Like the "real"…
I don’t think this is true at all. For example: the solution to a generic PDE that has no closed form solution at some point of import is likely transcendental, not algebraic, but definitely computable. (Think, say, Navier-Stokes being used for weather predictions in some specific place.)
> But what would be an example of an uncomputable number? That’s a good question. Most obviously, we could be talking about numbers that encode the solution to the halting problem. It would lead to a paradox to have a computer program that allows us to decide, in the general case, whether a given computer program halts. So, if a procedure to approximate a particular real requires solving the halting problem, we can’t…
I was making myself toy, tapered kaleidoscopes using one piece cardboard plans. One needed to ensure that the dihedral angles between the mirrors be precise.
This is not easy to do with the usual middle-school geometry-box rulers and protractors. Graduations not fine enough, precise enough, extending long straight lines using a small ruler not straight enough ...
However the dimensions being all algebraic numbers one could use entirely straight edge and compass constructions. Had much better luck this way, with a pointy enough pencil.
A proper drafting board and a T-square or a drafter would have made things easier for parallel and perpendicular translations. But one can do those with compass too.
> Of course, we don’t teach about computable numbers in school. Instead, the most common “upgrade” from ℚ are reals: While "computable" numbers are a recent concept, already for a few centuries, since the early 18th century, mathematics has taught about another set of numbers intermediate between rational numbers and "real" numbers: the algebraic numbers, which are a subset of the computable numbers. Like the "real"…
> few of the computable numbers that are not algebraic are interesting, the main exceptions being the numbers that are algebraic expressions containing "2*Pi" and/or "ln 2". I don’t think this is true at all. For example: the solution to a generic PDE that has no closed form solution at some point of import is likely transcendental, not algebraic, but definitely computable. (Think, say, Navier-Stokes being used for w…
They are not comparable with numbers like 2*Pi or various irrational nth roots that can appear in a lot of relationships and formulae in symbolic computations.
That is what I meant by "interesting", i.e. the necessity of using symbols of such numbers, obviously for use in symbolic computations, since in numeric computations you would never use the actual numbers, but only some approximations of them.
What I have said is equivalent to saying that there are only a few transcendental numbers for which you need symbols.
The number of symbols that are really needed is much less than the number of symbols that happened to be used during the history. For instance a single symbol related to Pi is needed, and it would have been much better if it was a symbol for 2*Pi, not for Pi. When using decimal numbers, one may want to use the value of the decimal logarithm of "e", or of its inverse, but there exists no need whatsoever to use decimal numbers anywhere, this is just a historical accident. Etc., there are various other examples of superfluous constants, which are not needed in any practical application, unlike "2*Pi" and "ln 2", which are ubiquitous (because they appear in the derivation formulae for the trigonometric and exponential functions).
This is the first time I've seen this way to show that Q does not have a higher cardinality than N, is it a common method? I don't remember exactly how I learned about it in high school, infinity cardinalities have rarely come up since then, but it was some other method or at least another form of presentation, i.e. symbols and prose.
Yup, it's common. (I'm fairly sure this or something very similar was the first way I ever saw it done.)
I've read about an actual bijection between naturals and rationals, but I don't remember how it was done.
¹ Possibly in the more general form of showing the bijection between ℕ and ℤ².
> But what would be an example of an uncomputable number? That’s a good question. Most obviously, we could be talking about numbers that encode the solution to the halting problem. It would lead to a paradox to have a computer program that allows us to decide, in the general case, whether a given computer program halts. So, if a procedure to approximate a particular real requires solving the halting problem, we can’t…
Earlier quoted context omitted.
Yup, it's common. (I'm fairly sure this or something very similar was the first way I ever saw it done.)
Indeed, it's always presented that way.¹ It's very unsatisfying because it doesn't establish a 1:1 correspondence; it depends on the idea that if set A has the same cardinality as a superset of set B, then set B's cardinality cannot exceed set A's. Add the assumption that the natural numbers have the lowest possible infinite cardinality and the proof is technically complete. I've read about an actual bijection betwee…
There are many ways to define an order on the rational numbers, which would establish a bijection to 0, 1, 2 ...
For instance, after reducing the numerator and denominator, so that you have unique rational numbers, you could define that they are ordered based on the sum of the number of digits of the numerator and of the denominator. This ensures that for each N that is the sum of digits, there are only a finite number of rational numbers. Inside this finite set, you can choose various rules, e.g. that positive numbers precede negative numbers, that a number with fewer digits in the denominator precedes another, etc. Then among the numbers with e.g. K digits in the numerator and L digits in the denominator, you could choose a lexicographic ordering, when the numerator is written before the denominator.
It does not matter which ordering rules you choose, the point is that you can always find such an order, which will arrange all rational numbers in a sequence, which describes thus a bijection with the natural numbers.
For algebraic numbers, you can establish such an order for the polynomials whose solutions they are, again finding a bijection. The easy solution is the same, to first establish an order between subsets of numbers that contain only a finite number of elements, and then define an order inside the subsets (e.g. with unique polynomials, where the coefficients do not have common factors, you can order them based on the sum of the number of digits of all coefficients).
The same technique works with any power of the set of rational numbers, or of the set of algebraic numbers.
For computable numbers, which are determined by programs written with an alphabet having a finite number of characters, you can define an order for the programs, e.g. first based on the length of the program, and then, among the finite number of programs having the same length, with lexicographic order.
With real numbers such methods do not work, because any attempt to arrange the real numbers into a sequence of subsets results in subsets that do not have a finite number of elements, like above, but which have an infinite number of elements.