4 ms·

Sure, that's the story the government tells everyone. It sounds plausible enough, but is it the whole story? * Apply Downward Lowenheim-Skolem to get a countab

Sure, that's the story the government tells everyone. It sounds plausible enough, but is it the whole story? * Apply Downward Lowenheim-Skolem to get a countable model of set theory * Construct the reals using whichever technique you want. * Since the base set theory is countable, so is the set of constructed reals. The same technique can give you countably many groups, countably many rings, countably many points in the plane, etc. Everything is countable.

openasocket 10y ago
You're referring to https://en.wikipedia.org/wiki/Skolem%27s_paradox https://en.wikipedia.org/wiki/Skolem%27s_paradox ? It's a rather limited edge-case in mathematics, it's misleading to simply assert that "everything is countable."
danharaj 10y ago
Countable in the external logic, but the internal logic still proves that there are uncountably many reals.
wayn3 10y ago
it is very much not possible to construct the real numbers in such a way that they are countable. (the set of real numbers is the object that "happens" when you fill the "holes" in the set of rational numbers). cantors diagonalization argument is proof of that. you can't pull some silly trick to make them countable. there are many properties of R that are countable, but that doesn't make R itself countable.
- btilly 10y ago
  The truth of your statement depends on what philosophy of mathematics you accept. Which itself is not something that can ever be settled by pure reason. Here is a definition of the reals to consider. A real number is a computer program which implements a function f from positive integers N to the rationals such that |f(n) - f(m)| < 1/n + 1/m. This is a reasonable definition of real numbers, and all real numbers that you're likely to hear of are real numbers under this definition. But now consider. There are a finite number of symbols that we build programs out of. Therefore for every N, there are a finite number of possible computer programs of length N. Only some of which represent real numbers under this definition. Therefore there is a countable sequence which contains all real numbers in it! What is the key philosophical difference between this system of mathematics and the usual one? Quite simply this. Classical mathematics asserts the existence of things that cannot be written down or calculated by humans. This system of mathematics denies the existence of things which we cannot write down. Now about a hundred years ago there was a major debate between these two philosophical camps. In the end the classical school won simply because most mathematicians don't care about philosophy, and classical mathematics is easier to work with. But the purportedly inescapable logical conclusions that you're taught about are not actually as inescapable as you've been lead to believe.
  - aaachilless 10y ago
    I don't think I buy your argument, but I'm absolutely not a mathematician, so I could have missed something. Why I don't buy it: It seems you didn't need to redefine the reals as programs to make this argument--the reals are classically defined as Cauchy sequences of rationals and (if the argument were valid) you could make the same claim using these sequences instead of programs. I don't think the actual philosophical question is whether the reals are countable, it's whether the reals "exist". You can't define the reals such that they're countable because if you did, they wouldn't be the same structure.
    - btilly 10y ago
      Here is what you have missed. The difference between the classical version and the constructive version that I wrote down is in what kind of rules you can use to construct a Cauchy sequence. My version is something that can be written down in a Turing machine. The classical version is that rules are anything that can follow a set of axiomatic rules - and includes rules that we cannot, even in principle, think of trying to evaluate. Therefore in the classical version, you can create a rule that depends on being able to evaluate every other rule - including rules similar to itself. That is exactly what Cantor's argument does. In the constructive version you can only create rules using operations that we can guarantee will finish. Which doesn't include verifying the incalculable truth or falsity of arbitrary other rules. Moving on, though, existence is critical. The key philosophical difference that drove the debate was pure existence proofs. Is proof by contradiction a valid method of reasoning with infinite sets? In particular, can you establish the existence of something by proving a contradiction if it does not exist? In what sense does the thing proven to exist actually exist? What if we prove that it exists but have no way to find it? What it we prove that it exists, have no way to find it, and no way to verify that we have found it? These are not hypothetical questions. See the https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... for a class of graph theory problems, all of which have polynomial time algorithms to solve. But we have no way to find those solutions. And in some cases it is impossible for us to verify whether a purported solution is a solution even if we were handed it. So..do you believe in the existence of things in an infinite set that are impossible to find and impossible to verify?
chriswarbo 10y ago
Your theory will have countable models, but via Goedel (and assuming we're ignoring inconsistent theories) it will be incomplete, capturing only a subset of the reals' properties. Any particular theory, capturing some aspect of the reals, can be given a countable model. Those "constructed reals" are countable, but they miss out almost all of the reals. Think about it this way: a theory is like an interface, a theory of the reals provides an API to access the reals. The API is necessarily limited; not least because there are only countably many ways we can combine the operations. Now consider a mock implementation of that interface: rather than passing around reals, we invent some (countable) dummy objects to use instead. Since the API is limited, we can always come up with a mock implementation which cannot be distinguished from the real implementation using that API/theory. That doesn't mean that the reals are countable. It does mean that uncountability is an implementation convenience; regardless of what result we're after, we could get it using countable objects, but we might have to spend a lot of effort "out smarting" the algorithms we're using (i.e. coming up with our "mock" set).

openasocket 10y ago

You're referring to https://en.wikipedia.org/wiki/Skolem%27s_paradox https://en.wikipedia.org/wiki/Skolem%27s_paradox ? It's a rather limited edge-case in mathematics, it's misleading to simply assert that "everything is countable."

danharaj 10y ago

Countable in the external logic, but the internal logic still proves that there are uncountably many reals.

wayn3 10y ago

it is very much not possible to construct the real numbers in such a way that they are countable. (the set of real numbers is the object that "happens" when you fill the "holes" in the set of rational numbers). cantors diagonalization argument is proof of that. you can't pull some silly trick to make them countable. there are many properties of R that are countable, but that doesn't make R itself countable.

btilly 10y ago
The truth of your statement depends on what philosophy of mathematics you accept. Which itself is not something that can ever be settled by pure reason. Here is a definition of the reals to consider. A real number is a computer program which implements a function f from positive integers N to the rationals such that |f(n) - f(m)| < 1/n + 1/m. This is a reasonable definition of real numbers, and all real numbers that you're likely to hear of are real numbers under this definition. But now consider. There are a finite number of symbols that we build programs out of. Therefore for every N, there are a finite number of possible computer programs of length N. Only some of which represent real numbers under this definition. Therefore there is a countable sequence which contains all real numbers in it! What is the key philosophical difference between this system of mathematics and the usual one? Quite simply this. Classical mathematics asserts the existence of things that cannot be written down or calculated by humans. This system of mathematics denies the existence of things which we cannot write down. Now about a hundred years ago there was a major debate between these two philosophical camps. In the end the classical school won simply because most mathematicians don't care about philosophy, and classical mathematics is easier to work with. But the purportedly inescapable logical conclusions that you're taught about are not actually as inescapable as you've been lead to believe.
- aaachilless 10y ago
  I don't think I buy your argument, but I'm absolutely not a mathematician, so I could have missed something. Why I don't buy it: It seems you didn't need to redefine the reals as programs to make this argument--the reals are classically defined as Cauchy sequences of rationals and (if the argument were valid) you could make the same claim using these sequences instead of programs. I don't think the actual philosophical question is whether the reals are countable, it's whether the reals "exist". You can't define the reals such that they're countable because if you did, they wouldn't be the same structure.
  - btilly 10y ago
    Here is what you have missed. The difference between the classical version and the constructive version that I wrote down is in what kind of rules you can use to construct a Cauchy sequence. My version is something that can be written down in a Turing machine. The classical version is that rules are anything that can follow a set of axiomatic rules - and includes rules that we cannot, even in principle, think of trying to evaluate. Therefore in the classical version, you can create a rule that depends on being able to evaluate every other rule - including rules similar to itself. That is exactly what Cantor's argument does. In the constructive version you can only create rules using operations that we can guarantee will finish. Which doesn't include verifying the incalculable truth or falsity of arbitrary other rules. Moving on, though, existence is critical. The key philosophical difference that drove the debate was pure existence proofs. Is proof by contradiction a valid method of reasoning with infinite sets? In particular, can you establish the existence of something by proving a contradiction if it does not exist? In what sense does the thing proven to exist actually exist? What if we prove that it exists but have no way to find it? What it we prove that it exists, have no way to find it, and no way to verify that we have found it? These are not hypothetical questions. See the https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... for a class of graph theory problems, all of which have polynomial time algorithms to solve. But we have no way to find those solutions. And in some cases it is impossible for us to verify whether a purported solution is a solution even if we were handed it. So..do you believe in the existence of things in an infinite set that are impossible to find and impossible to verify?

chriswarbo 10y ago

Your theory will have countable models, but via Goedel (and assuming we're ignoring inconsistent theories) it will be incomplete, capturing only a subset of the reals' properties. Any particular theory, capturing some aspect of the reals, can be given a countable model. Those "constructed reals" are countable, but they miss out almost all of the reals. Think about it this way: a theory is like an interface, a theory of the reals provides an API to access the reals. The API is necessarily limited; not least because there are only countably many ways we can combine the operations. Now consider a mock implementation of that interface: rather than passing around reals, we invent some (countable) dummy objects to use instead. Since the API is limited, we can always come up with a mock implementation which cannot be distinguished from the real implementation using that API/theory. That doesn't mean that the reals are countable. It does mean that uncountability is an implementation convenience; regardless of what result we're after, we could get it using countable objects, but we might have to spend a lot of effort "out smarting" the algorithms we're using (i.e. coming up with our "mock" set).