261–270 of 359 posts
Earlier quoted context omitted.
"the claim that the set of natural numbers has the same size as that of the rational numbers" Where can I read more about that? Because, both are infinite, but there still should be more rational numbers, than natural numbers?
You can count rational numbers and everything countable is the size of infinity as natural numbers. Google ”counting rational numbers” and ”different sizes of infinity” to learn more.
Earlier quoted context omitted.
That was another question in the back of my mind -- famously, the four color theorem was proved by computers through exhaustive analysis (checking every possibility). At the time, it was controversial as a "proof" since it didn't really take the usual form of a proof. I've often wondered "Why can't we do something like that, but for all instances of things like the Collatz conjecture?" Of course, it's computationally…
"famously, the four color theorem was proved by computers through exhaustive analysis (checking every possibility)" This is impossible. The plane can be arbitrarily large with an arbitrary number of regions. It can be exhaustively checked for n number of regions up to a certain n. But not for arbitrary n.
Earlier quoted context omitted.
But isn’t this what the busy beaver numbers are? Numbers that we cannot write for arbitrary n but they do exist?
Do they exist? I thought there was an independence theorem for the specific values of almost all busy beaver numbers.
It is true though that various (decidable) proof systems are unable to prove that the Busy Beaver function has any specific value beyond a certain point. However, where that cut-off is varies from proof system to proof system, with stronger proof systems being able to prove more an more values of the Busy Beaver function.
Maybe you find it weird that we can prove (Exists x. P x) without being able to prove P n for any particular numeral n? Welcome to the strange world of classical (i.e. non-constructive) mathematics.
You can map all the real numbers to the interval 0 0.0 => 0 0.1 => 1 0.2 => 2 ... 0.14159 => 95141 The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? Can there be an "infinitely large integer?" or are there just infinitely many of them? I think this question gets to the core of the problem.
so how do you map say pi/4? Which digit do you start with?
Earlier quoted context omitted.
> because it asserts the existence of natural numbers that have no "written form" I don’t see why that should imply it wouldn't be "okay" to add ¬Con(ZFC). It may be highly counterintuitive, but the history of mathematics is full of counterintuitive results that nowadays are accepted as true in mainstream mathematics. Well-known examples are the existence of irrational numbers, the claim that the set of natural numbe…
"the claim that the set of natural numbers has the same size as that of the rational numbers" Where can I read more about that? Because, both are infinite, but there still should be more rational numbers, than natural numbers?
Earlier quoted context omitted.
Sure, that is why I wrote: > In such a sense then, we can trivially "count" the real numbers unless we hold the philosophical view that there are real numbers that are not expressible. This is where it becomes a question of philosophy of mathematics, not mathematics proper. I'm not disagreeing with your interpretation of Cantor's diagonal proof, I'm merely pointing out that this interpretation depends on a very speci…
> It is obvious that all expressions in the English language can be ordered from smallest to largest and lexicographically, which makes these expressions trivially countable. You could say the same about just real numbers, which can also be ordered from smallest to largest. This definitely not 'trivially' implies countability. Edit: I edited my post shortly after posting from "Humor me and count out the first two rea…
> Humor me and count out the first two real numbers in English in lexicographical order.
Probably "one" and "six" (then "ten" and "two", followed by all 4-letter expressions of real numbers), unless you can think of an English expression with a length of three letters or less that would occur before "one" and "six" lexicographically. If you consider "pi" or "e" to be descriptions of real numbers then clearly these would occur before "one" and "six".
But of course you can also pick an arbitrary universal Turing machine or other suitable formalism, pick an encoding as bit strings and order expressions in such a formal language according to their bit strings. Ordering expressions in the English language is only the less formal counterpart.
(If your point is that ordering expressions of real numbers in English is far from unambiguous without first agreeing on a dictionary of valid words and on rules of what can be considered an expression of a real number in more than one word then of course I would agree. But what I'm driving at is not that it's easy to unambiguously count out the real numbers in English, of course it's not, but rather that any kind of natural or formal language expressions, by being recursively enumerable, are "numerous" enough to be a countable set of expressions. To say that the real numbers are uncountable is to accept the view that there are real numbers that are not and can never be expressible in language, which is a view that only makes sense against the backdrop of a very specific philosophical framework. One that is definitely accepted more or less implicitly by most working mathematicians, but not the only possible one. And this philosophical framework cannot itself be justified or grounded by a mathematical argument such as Cantor's diagonal proof.)
---
Reply to the parent after edit:
> You could say the same about just real numbers, which can also be ordered from smallest to largest. This definitely not 'trivially' implies countability.
No, what I meant was that by ordering expressions in the English language or other suitable formal languages first from smallest string to largest string and within these groups lexicographically, you can enumerate all the expressions in such a language, which makes them trivially countable.
Of course this does not give you a 1:1 mapping from expressions in a language to real numbers, but it is meant to illustrate that the real numbers are not uncountable because they are 'too numerous' to be counted by the natural numbers, in the sense that a box is not large enough to hold a collection of things. They are uncountable because we accept the view that there can be real numbers that are not and cannot be expressible in language, which is a platonist view that is open to philosophical critique.
Earlier quoted context omitted.
> It is obvious that all expressions in the English language can be ordered from smallest to largest and lexicographically, which makes these expressions trivially countable. You could say the same about just real numbers, which can also be ordered from smallest to largest. This definitely not 'trivially' implies countability. Edit: I edited my post shortly after posting from "Humor me and count out the first two rea…
EDIT: The parent first said (before being edited, with my original answer after the quote): > Humor me and count out the first two real numbers in English in lexicographical order. Probably "one" and "six" (then "ten" and "two", followed by all 4-letter expressions of real numbers), unless you can think of an English expression with a length of three letters or less that would occur before "one" and "six" lexicograph…
You missed infinitely many numbers between those two. For example "one thousand" and "one dot/comma three".
Once you've worked that all out, can you now tell me which natural number you assigned to "six" in your lexicographical order?
Edit: Ah. Took me a moment to realize you are ordering by number of characters first.
> They are uncountable because we accept the view that there can be real numbers that are not and cannot be expressible in language, which is a platonist view that is open to philosophical critique.
So similar to R \ Q? Or the same?
Earlier quoted context omitted.
EDIT: The parent first said (before being edited, with my original answer after the quote): > Humor me and count out the first two real numbers in English in lexicographical order. Probably "one" and "six" (then "ten" and "two", followed by all 4-letter expressions of real numbers), unless you can think of an English expression with a length of three letters or less that would occur before "one" and "six" lexicograph…
> Probably "one" and "six" You missed infinitely many numbers between those two. For example "one thousand" and "one dot/comma three". Once you've worked that all out, can you now tell me which natural number you assigned to "six" in your lexicographical order? Edit: Ah. Took me a moment to realize you are ordering by number of characters first. > They are uncountable because we accept the view that there can be real…
Edit: This is also why the computable numbers are countable, but not computably enumerable (because figuring out which expressions correspond to real numbers is equivalent to the halting problem).
Earlier quoted context omitted.
Individually, or independently, axioms have no truth value. But when you put together a system of multiple axioms, they can contradict eachother. I see no problem with the question of whether the continuum hypothesis is true, given ZFC as a precondition. All we are asking is if the axiom contradicts ZFC. Axiom independence is very similar to operator commutation in quantum mechanics.
The Continuum Hypothesis and its negation are both proven to be consistent with ZFC (this is what the article is talking about RE forcing and Godel's proof of the consistency of CH). There is no contradiction to assume one or the other alongside ZFC. The article is really talking about Platonic truth when it talks about something being true or false. > Individually, or independently, axioms have no truth value. Indee…
Earlier quoted context omitted.
> Probably "one" and "six" You missed infinitely many numbers between those two. For example "one thousand" and "one dot/comma three". Once you've worked that all out, can you now tell me which natural number you assigned to "six" in your lexicographical order? Edit: Ah. Took me a moment to realize you are ordering by number of characters first. > They are uncountable because we accept the view that there can be real…
Oh, I see what the issue is. I wrote "smallest to largest and lexicographically", meaning first from smallest to largest (as measured by the length of the string) and then within each group lexicographically, which is the usual way of giving an enumeration of such expressions as far as I know. Of course you cannot enumerate these expressions if you expect a solely lexicographical ordering. In any case, English was ju…
Though I'm not convinced that numbers that are not expressible don't exist. I could for instance say "the length of this line", which may very well have a length that is not expressible in a language that uses a finite set of symbols (hah, that's why your expressions are countable, of course!).
Consider a language however that instead of numbers simply uses sounds of the appropriate length, or draws lines of proportional length (assuming of course you could do this precisely).
With that language you could express every real number, and you could express numbers that turing machines* or English can't.
*Unless programmed in that language.