Countable (roughly) means that you can count from one element to any other in a finite amount of time, it doesn't mean you can count the whole set in a finite amount of time.
1. Produce a number
2. Add it to the set of numbers I’m counting
3. Sort the numbers
Usually when you produce a number, you produce it in order (eg. 1, 2, 3, 4). But you could also count like: 4, 1, 3, 2 and then sort the set.
As long as you have an algorithm/function to keep producing numbers for “each iteration”, you can always keep counting one at a time.
The case you say: “count from one element to any other” is equivalent to a finite operation, it has a very clear beginning and end. But an infinite set doesn’t, unless you stop counting.
I think you're mixing up math and natural language. A "countable set" in math, by definition, means what I said it means, (or more precisely means it is 1-to-1 with the natural numbers). You can argue that the word itself is misleading/unclear, but that's a semantic argument and you should make clear that that's your stance.
It seems to me that this definition of "countable" is obscure, and furthermore fails to show why the word "countable" is used. Is it wrong to say that a countable set is a set in which it is reasonable to ask which element is the "next" element? That's a natural-language definition, right?
You can do that with natural numbers (just add 1) and with rationals (so I understand, but I can't give a procedure). Both sets have the same cardinality: aleph-null. You can't do that with the reals; that set is not countable, and furthermore has grater cardinality than aleph-null.
It can also be shown that (a) there is no set with cardinality greater than aleph-null and smaller than the cardinality of the reals; and (b) no set with cardinality greater than aleph-null is countable.
I can't do these proofs, but I've read them (in their non-symbolic, natural-language forms), and I was convinced.
> You can... (define "next number") ...with rationals (so I understand, but I can't give a procedure).
1/1
1/2, 2/1
1/3, 2/2, 3/1
1/4, 2/3, 3/2, 4/1
1/5, 2/4, 3/3, 4/2, 5/1
...
The first rational number is 0. Next is 1/1, that is 1.
Next number to a positive rational number is its negative version, for example 1/1 is followed by -1/1.
Next number to a negative positive number can be found by taking its absolute value (i.e. the previous number), locating it in the pyramid, and choosing the next number... skipping those fractions which can be simplified. For example -1/1 is followed by 1/2.
So it goes like this: 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3... now we skip 2/2 because that can be simplified to 1/1, and proceed with... 3/1, -3/1, 1/4, -1/4...
> Is it wrong to say that a countable set is a set in which it is reasonable to ask which element is the "next" element? That's a natural-language definition, right?
You can do that with real numbers as well.
F(x)=randomreal()
At any step you want a next element, you just produce a random real element.
You can’t pre-determine how that random element will relate to the previously generated elements, but you can still produce real numbers, one at a time, and count them as you go. And if you do it for infinity, then you will never finish, but at every single step you will have assigned a natural number to a real number.
The definitions used for the proof are fiction that you can ever fully finish counting something.
The illusion that will fall for is that we think that all natural numbers are somehow pre-computed.
If we are going to be generating infinite elements one by one, then you can count/number/order all of them, one at a time, no problem.
If you recall, your original comment said “ If you say one infinity is larger/smaller than another, you’d be saying that the complete map for one is larger/smaller than for the other one.
But if they are both infinite, you will never stop counting, so you just can’t know.”.
So, if I can map all of the positive integers onto the reals and provably have reals that cannot be generated, that should suffice, no?
Take the reals from 0 to 1. For each positive integer X, flip the digits and put it behind the decimal. So, 437 gets mapped to 0.734, 1000 gets mapped to .0001, etc.
None of the transcendental numbers between 0 and 1 will get mapped onto.
This is because all positive integers are a finite series of digits, whereas all transcendental numbers provably do not terminate. It is not possible to flip a finite sequence of digits and get a non terminating sequence of digits.
So, now you have a generator function that can go through the positive integers one by one and never generate any members of an entire class of real numbers.
FYI I find this quite useful in clarifying my own thinking so feel free to tell me why that isn’t convincing to you.
But you are imagining “all the numbers between 0 and 1”, those numbers don’t/won’t exist until you generate them.
You cannot perform the action of mapping.
You can give me a formula to start mapping. But I would never finish. So you are imagining the result.
There is no result, the mapping is a process, not a finite result that you can compare to another finite result.
As long as you keep counting (producing naturals one after another), I can keep producing random real numbers and sorting them. There’s no point at which either one of us cannot generate one additional number.
And if we keep going to infinity, then the random generator will have generated all possible real numbers.
Does pi/4 not exist? If I draw a circle of diameter 1 and erase all but one quadrant, I now have constructed a segment of length pi/4. This happens to be a transcendental number between 0 and 1.
Stop using your random number generator. It is making you miss the point. It has no special value. For some reason you are assigning it a special value the same way people might assign numerical greater than order a special value.
If you use the flipped positive integer generator instead, it is quite obvious that you will never generate pi/4 no matter how long you run that generator, yet that generator will run through all possible positive integers.
> Does pi/4 not exist? If I draw a circle of diameter 1 and erase all but one quadrant, I now have constructed a segment of length pi/4. This happens to be a transcendental number between 0 and 1.
Pi/4 the symbol exists. Pi/4 the calculated number output doesn’t exist. You can’t finish calculating it.
And if you calculated a finite approximation, then all you’d be doing is just connect one symbol (Pi/4) to another symbol (output of your calculation).
You keep thinking hat assigning symbols/labels to infinity somehow gives you an instant result of an infinite process/computation.
You don’t need to finish calculating pi/4 to know that it is a non-computable number, whereas all positive integers are computable, which is why the length of that segment will never show up in the generator.
My assertion is simply that the infinity of the positive integers is different from the infinity of the reals in the sense that the infinity of the positive integers can be computed to arbitrarily large measure given enough time.
Whereas for the reals, we’ll forever be stuck on pi/4 and never get to e. That given arbitrary time, we can only compute a non-measurable number of reals.
Which makes the infinity of the positive integers more “real” than the infinity of the reals, because we can use measurable things in algorithms, whereas non-measurable things require a leap of imaginative voodoo that I imagine you would rather not take.
If you prefer to take the infinity of the positive integers as literally the same as the infinity of the reals, then you’d have to believe that all finite sets of reals have positive measure within the reals. Sure, both infinities can be considered “unknowable” in that we cannot generate the entire thing so cannot generate/know all their properties, but we can generate the measure property. So they should both satisfy it.
Also, intuitively I think we should be able to prove the halting problem wrong, if all finite sets of reals are positively measurable, but don’t quote me on that! But I feel like taking such a property would imply that the spectral gap problem is computable, which then bunks the halting problem, and the concept of non-computable numbers altogether.
> My assertion is simply that the infinity of the positive integers is different from the infinity of the reals in the sense that the infinity of the positive integers can be computed to arbitrarily large measure given enough time.
Again the same issue. You are trying to make infinity finite by reducing it to “arbitrarily large measure”.
> Whereas for the reals, we’ll forever be stuck on pi/4 and never get to e. That given arbitrary time, we can only compute a non-measurable number of reals.
If you generate random reals at each step, you can generate a sequence as long as you want, without ever “getting stuck”.
I’m not trying to make infinity finite. I am just giving the infinity of the positive integers a computationally verifiable property.
> If you generate random reals at each step, you can generate a sequence as long as you want, without ever “getting stuck”.
You don’t understand your own argument. At no point did you ever generate an irrational number, nor can you. You can only generate approximations of them, all of which are rational. You are trying to make infinity finite by reducing it to “generate a random real”.
As it so happens, the infinity of the rationals is the same as the infinity of the positive integers, and demonstrably so. But the reals are not only the rationals. Or, you could say the reals do not exist. Only rational numbers do.
> At no point did you ever generate an irrational number, nor can you. You can only generate approximations of them, all of which are rational.
If you can’t generate an irrational number, then you can never have a set that contains it.
Again, you want to use a finite label “irrational”, to denote the idea of an infinite process (generating some irrational number one digit at a time without stopping).
You cannot count an infinite process. It doesn’t matter if it’s a rational number, the reals or the naturals.
The thing you are failing to understand is that your statement of “generate a random real” at each step is meaningless because each such step cannot be guaranteed to terminate.
Which means the generator function you have been espousing this entire time is in fact just as much symbolic fiction as the symbol of pi.
Consider the while loop,
while (1 === 1) {
print “Step {step++}”
}
Though clearly an infinite process, each step within the loop clearly terminates and has a loop index. That is, we will see “Step 100” printed, “Step 9999999”, etc given enough time. In a sense, countable, for a particular definition of countable.
On the other hand,
while (1 === 1) {
print “Step {step++}“
random_real()
}
This, your favored generator, is not guaranteed to ever print “Step 2”, because at step 1, it might try to print pi, which is a fiction that will never terminate and become real. Thus not countable.
I never guaranteed you that the process will finish. In fact I agree it will not, since it is infinite.
However, each subprocess within the process is finite and has a definite end. That is why the process is countable, albeit indefinite.
> No difference if you are trying to count the naturals, the reals or the digits of pi.
There is a difference. You can count the naturals. Each subprocess is finite: 1, 5, 2, 6, 3, 7, ....
You can count the digits of pi: 3, 1, 4, 1, 5, 9, ....
You cannot count the reals. randomreal() is not guaranteed to be finite a finite subprocess. I cannot guarantee you that any given invocation of randomreal() will terminate. In fact, it is trivial to construct a subprocess sequence where it fails to terminate:
randomreal(1) = 1
randomreal(2) = 3.14159.....
We will never reach randomreal(3).
In that sense, your issue is that your view is self-contradictory. For it to be consistent, you need to stop talking about the reals, because there is no such thing as the reals. Or, accept the notion of there being an infinite number of alephs.
You cannot both reference the reals and simultaneously claim there are not an infinite number of alephs without contradicting yourself. This is not a minor detail.
Which you path you choose, as far as I'm aware, is currently unknowable and a matter of personal philosophy rather than objectivity.
The definition of a countable set is that it has the same cardinality as the natural numbers set, “aleph-null”.
This is an ill defined concept for two reasons:
1) a set is supposed to be a “collection of items”, but the natural numbers is not a collection of numbers, it’s a method to generate an infinite number of numbers… which technically you could never count
2) it’s trying to use a symbol (aleph-null), to make infinity appear finite - the cardinality of an infinite set (like the natural numbers), cannot be a finite symbol.
So essentially there’s two contradictions in the definition of the cardinality of the set of natural numbers.
But that definition is taken as true, and then used as the basis for justifying other concepts, like comparing sizes of unknown infinities.
1) Who said a set is supposed to be a "collection of items" or any other kind of set in the CS definition? A set is a mathematical object which can be said to contain, or not contain, an element. The natural numbers fall into this definition of a set.
2) There's no such thing as a "finite symbol." What does that even mean? A symbol is a symbol, it symbolizes something. The symbols themselves are finite; they're just letters. But if that something that it symbolizes is an infinite quantity, why stop it?
You are living too close to reality and numbers and words. Even if sets were rigidly defined as finite objects, why not define some new thing, call it an "infinite collection," and let all the theorems like countability and aleph-null come out of that? It lets us do useful math, after all, so why let the words we use stop us? Clearly set theorists worldwide find nothing* wrong with the current definition.
> Clearly set theorists worldwide find nothing* wrong with the current definition.
Are you saying that popularity defines reality? If enough people agree on something that’s the truth and we shouldn’t question thing anymore?
About the two points:
1) the definition of what a set is vague, so math has determines that set is an atomic concept that through formality should conform to our expectations of what a set is. So instead of dormally defining what a set is, they formally define a description for a certain set (https://math.stackexchange.com/questions/1452425/what-is-the...)
2) not sure what you mean. All symbols are finite. Think of a symbol as a tag for something else. In the case of infinity, what’s happening here is that the label for infinity is being equated with actual infinity, and then used to determine other stuff.
Yes, I want this to mean something real. Because if we are just going to make stuff up, let’s just use a different language instead of co-opting concepts from natural language.
Cantors proof doesn’t prove that reals are uncountable, they prove that he couldn’t come up with a system to count them, if he had already counted the naturals and paired them up. But you cannot do that, it just doesn’t make sense.
Similarly, saying that the cardinality of the naturals is the label aleph-null, might be useful to perform operations. But whatever you conclude, will be based on the wrong assumption that you can finish counting infinity.
