13 ms·

Mathematician here. If you mean to say that you cannot constructively prove "the real numbers are not countable", then you're wrong. As a rule of thumb, you can

by mbid 10y ago

Mathematician here. If you mean to say that you cannot constructively prove "the real numbers are not countable", then you're wrong. As a rule of thumb, you can usually prove negative statements constructively as you would prove them classically. A constructivist would probably state the result more positive (and stronger, constructively): To every countable set M of real numbers, there is a real number not contained in M.

btilly 10y ago
Yeah, I'm a trained mathematician as well. A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument.
- Smaug123 10y ago
  Are you happy with the stronger "there is no surjection from any set to its power set"?
- mbid 10y ago
  I don't understand this. For a constructivist, "¬A" means "from A, falsity is derivable". You can derive falsity from the statement "there is a countable enumeration of the real numbers". A diagonal function given such an enumeration is constructively definable, and it is also constructively true that it is not equal to any of the enumerated ones (because 0 != 1 is true constructively). Thus, the diagonal is not enumerated all real numbers, but it also is by assumption, thus falsity. What does make real numbers weird when working constructively is that you cannot conclude |x| > 0 from x != 0. This means that 1 / x need not exist even if x != 0, so the real numbers do not form a field in the classical sense. If you don't trust me, maybe you'll trust wikipedia: https://en.wikipedia.org/wiki/Constructivism_(mathematics)#Cardinality https://en.wikipedia.org/wiki/Constructivism_(mathematics)#C....
  - mietek 10y ago
    > The interpretation of Cantor's result will depend upon one's view of mathematics. To constructivists, the argument shows no more than that there is no bijection between the natural numbers and T. https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#Interpretation https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#I...
    - Confusion 10y ago
      A surjection seems silly: doesn't that imply that some reals would be indistinguishable? Or can you indeed not prove that more than the natural number of reals are distinguishable in constructive mathematics?
      - mbid 10y ago
        Honestly, the result hinted at in the wikipedia article caught me by surprise as well: There are some flavors of constructive mathematics (notably CZF), that are still consistent if you also add the statement "There is a subset A of the natural numbers such that there is a surjection from A onto the real numbers". Note that this does not imply that you can prove this in CZF, it only means that you cannot disprove it. See http://www1.maths.leeds.ac.uk/~rathjen/acend.pdf http://www1.maths.leeds.ac.uk/~rathjen/acend.pdf prop. 8.2 if you're interested. Wikipedia says that the Cantor argument shows "no more" than that there is no bijection between the natural numbers and the real numbers. As far as I can tell, it also proves that there is no surjection from the natural numbers onto the reals in every system of constructive mathematics I know of, so I think this is slightly misleading. What do you mean by "distinguishable"? In constructivism, a set A such that x = y or x != y for all x, y in A is sometimes called decidable. And yes, it is indeed not true that the real numbers are decidable. This would imply that there is an algorithm that decides whether two infinite sequences of ones and zeroes will differ at some point or agree indefinitely, which is pretty much equivalent to solving the halting problem. On the other hand, the natural numbers, integers, rational numbers and every finite algebraic extension of the rational numbers (for example Q[i], "rational imaginary numbers") is decidable.
- TezlaKoil 10y ago
  > I'm a trained mathematician as well. Mayhap. >A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument. But in any case you misunderstand Cantor's argument and constructive mathematics. mbid is correct; Cantor's diagonalization argument constructively proves the uncountability of the real numbers, see e.g. Bishop-Bridges' CONSTRUCTIVE ANALYSIS, Theorem 2.19, page 29.
gertef 10y ago
"the real numbers are not countable" is a different statement from "the real numbers are constructible"
deleted 10y ago
[deleted]
hzhou321 10y ago
I am not a mathematician (physicist). I think the concept of infinity is a con that mathematicians have pulled on us (as there isn't an easy reality to map on to). I can understand arbitrarily big set; however, I never managed to make the jump from arbitrarily finite to infinity. Mathematicians made that jump and glossed over, then continue to show the difference between countable infinity and infinity beyond. Since I never could make that jump, it all sounds nonsense to me. I have a similar (and I believe to be equivalent) problems with infinitesimal as well. How does arbitrarily small but non-zero become infinitesimal? Since I have problem with infinitesimal, I find the differentiation of real numbers and rational numbers equally non-sensical. So mathematician, take a pause, could you explain what is countable infinity? Since you never can finish counting (all the natural numbers), how does it make the set countable? What do we mean exactly by countable here? Wikipedia refers to the idea of one-to-one correspondence. But since you can never exhaust the correspondence, what do we mean by one-to-one? Give me any unique real, I'll give you a unique natural number, and we can go on forever, so how does that not count as one-to-one correspondence? Unlike mathematicians, physicists are fine with unresolved :) PS: I guess countable can be defined as there is a definite way of ordering the set, which is true for natural numbers but questionable for real numbers. I still don't see how the ordering connects to the size of infinity and one to one correspondence. Even for the set of real numbers, I can have an algorithm continuously generate random numbers (discarding re-occurring ones so it will be a unique sequence) and prove there is an order of the set (non-exhaustively defined, same as the set of natural number). The ordering may not be describable though. But non-describable ordering is still an ordering, right? Just as a real number that cannot be exhaustively described is still a number. I don't have to describe it, I can hand-wave it just as the way mathematicians hand-waved the infinity.
- cvoss 10y ago
  I find it helpful to think of countability in terms of the following game: You have a set of items in mind. You propose a (non-terminating) scheme for listing all the items in the set. An adversary attempts to name any item X, hoping your scheme misses it. However, you then show your scheme does, in fact, get to X after a _finite_ amount of time. The set is said to be countable if you prove that your adversary cannot win this game. Yes, the counting process is non-terminating. But every item gets counted after only finite time.

by mbid 10y ago

btilly 10y ago

Yeah, I'm a trained mathematician as well. A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument.

Smaug123 10y ago
Are you happy with the stronger "there is no surjection from any set to its power set"?
mbid 10y ago
I don't understand this. For a constructivist, "¬A" means "from A, falsity is derivable". You can derive falsity from the statement "there is a countable enumeration of the real numbers". A diagonal function given such an enumeration is constructively definable, and it is also constructively true that it is not equal to any of the enumerated ones (because 0 != 1 is true constructively). Thus, the diagonal is not enumerated all real numbers, but it also is by assumption, thus falsity. What does make real numbers weird when working constructively is that you cannot conclude |x| > 0 from x != 0. This means that 1 / x need not exist even if x != 0, so the real numbers do not form a field in the classical sense. If you don't trust me, maybe you'll trust wikipedia: https://en.wikipedia.org/wiki/Constructivism_(mathematics)#Cardinality https://en.wikipedia.org/wiki/Constructivism_(mathematics)#C....
- mietek 10y ago
  > The interpretation of Cantor's result will depend upon one's view of mathematics. To constructivists, the argument shows no more than that there is no bijection between the natural numbers and T. https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#Interpretation https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#I...
  - Confusion 10y ago
    A surjection seems silly: doesn't that imply that some reals would be indistinguishable? Or can you indeed not prove that more than the natural number of reals are distinguishable in constructive mathematics?
    - mbid 10y ago
      Honestly, the result hinted at in the wikipedia article caught me by surprise as well: There are some flavors of constructive mathematics (notably CZF), that are still consistent if you also add the statement "There is a subset A of the natural numbers such that there is a surjection from A onto the real numbers". Note that this does not imply that you can prove this in CZF, it only means that you cannot disprove it. See http://www1.maths.leeds.ac.uk/~rathjen/acend.pdf http://www1.maths.leeds.ac.uk/~rathjen/acend.pdf prop. 8.2 if you're interested. Wikipedia says that the Cantor argument shows "no more" than that there is no bijection between the natural numbers and the real numbers. As far as I can tell, it also proves that there is no surjection from the natural numbers onto the reals in every system of constructive mathematics I know of, so I think this is slightly misleading. What do you mean by "distinguishable"? In constructivism, a set A such that x = y or x != y for all x, y in A is sometimes called decidable. And yes, it is indeed not true that the real numbers are decidable. This would imply that there is an algorithm that decides whether two infinite sequences of ones and zeroes will differ at some point or agree indefinitely, which is pretty much equivalent to solving the halting problem. On the other hand, the natural numbers, integers, rational numbers and every finite algebraic extension of the rational numbers (for example Q[i], "rational imaginary numbers") is decidable.
TezlaKoil 10y ago
> I'm a trained mathematician as well. Mayhap. >A constructivist would state the result in a variety of ways. But none of them would involve a potentially self-referential construction based on the absolute truth of an infinite number of statements. Which really does rule out Cantor's argument. But in any case you misunderstand Cantor's argument and constructive mathematics. mbid is correct; Cantor's diagonalization argument constructively proves the uncountability of the real numbers, see e.g. Bishop-Bridges' CONSTRUCTIVE ANALYSIS, Theorem 2.19, page 29.

gertef 10y ago

"the real numbers are not countable" is a different statement from "the real numbers are constructible"

deleted 10y ago

[deleted]

hzhou321 10y ago

I am not a mathematician (physicist). I think the concept of infinity is a con that mathematicians have pulled on us (as there isn't an easy reality to map on to). I can understand arbitrarily big set; however, I never managed to make the jump from arbitrarily finite to infinity. Mathematicians made that jump and glossed over, then continue to show the difference between countable infinity and infinity beyond. Since I never could make that jump, it all sounds nonsense to me. I have a similar (and I believe to be equivalent) problems with infinitesimal as well. How does arbitrarily small but non-zero become infinitesimal? Since I have problem with infinitesimal, I find the differentiation of real numbers and rational numbers equally non-sensical. So mathematician, take a pause, could you explain what is countable infinity? Since you never can finish counting (all the natural numbers), how does it make the set countable? What do we mean exactly by countable here? Wikipedia refers to the idea of one-to-one correspondence. But since you can never exhaust the correspondence, what do we mean by one-to-one? Give me any unique real, I'll give you a unique natural number, and we can go on forever, so how does that not count as one-to-one correspondence? Unlike mathematicians, physicists are fine with unresolved :) PS: I guess countable can be defined as there is a definite way of ordering the set, which is true for natural numbers but questionable for real numbers. I still don't see how the ordering connects to the size of infinity and one to one correspondence. Even for the set of real numbers, I can have an algorithm continuously generate random numbers (discarding re-occurring ones so it will be a unique sequence) and prove there is an order of the set (non-exhaustively defined, same as the set of natural number). The ordering may not be describable though. But non-describable ordering is still an ordering, right? Just as a real number that cannot be exhaustively described is still a number. I don't have to describe it, I can hand-wave it just as the way mathematicians hand-waved the infinity.

cvoss 10y ago
I find it helpful to think of countability in terms of the following game: You have a set of items in mind. You propose a (non-terminating) scheme for listing all the items in the set. An adversary attempts to name any item X, hoping your scheme misses it. However, you then show your scheme does, in fact, get to X after a _finite_ amount of time. The set is said to be countable if you prove that your adversary cannot win this game. Yes, the counting process is non-terminating. But every item gets counted after only finite time.