Trickster
Level: Smitemaster

Rank Points: 662
Registered: 07-03-2007
IP: Logged

Someone Else wrote:
Your other points, however, are flawed with the version of the proof you used. If my numbers ended in ...9999~, then it could possibly be equal to the diagonalized number. A stronger version of the proof would be that the number is replaced by a digit x such that 1<=x<=8, to avoid that identity.

Your intuition here is correct! This is something that must be accounted for in a formal proof. The modified version of Cantor's original proof I gave handles this, but diagonalization does not. Your idea works to solve part of the issue, but not in base 2 (this turns out to be important because base 2 is in a sense a useful metric of things in information theory).

Before solving your problem, there is another wrinkle of the same sort: we need to show that when we tried to map N to R, we weren't foiled solely because of the existence of potential duplicate numbers in R (due to the multiple representations in Arabic numbers).

To solve this, we can show with diagonalization that there is no possible bijection from N to [0,1) in R. Some of the [0,1) in R have two forms, so we consider anything ending in .99999... to actually refer to a number in [1,2): the number you get from adding 1 to the duplicate form. Thus we still have a proof that there is no possible bijection from N to a subset of R (the subset [0,1) + (all [1,2) rationals where the denominator only has prime factors of 2 and 5). Specifically, we show that there are R in this set left unpaired, so there is no surjection from N to this subset of R. By properties of the composition of surjections, there is no surjection from N into any set that is a superset of this; so there is no surjection (and thus no bijection) from N to R in general.

Now on to the second part: choosing a pattern which does not equal another number in the list, when each number might have two forms, in base 2. We want, if we ever see ...00000... or ...11111..., to choose something other than ...11111... or ...00000... . The simple method for doing this is to consider every pair of digits rather than every digit, and choose something that differs from this pair: either 01, or 10. This has the same effect as what you suggested.

Someone Else wrote:
But I admit defeat in this debate. You have argued well and persuasively, my good sir.

In mathematics this is not really a "debated" topic (apart from constructivism and intuitionism, which are both separate issues). The challenge you have is pausing long enough to learn the definitions under the topic, rather than jumping to intuition-based conclusions.

Math in general, and logic in particular, are prone to false paradoxes if the language you use is either not well-defined or not well-founded. English (as with all natural languages) is horrible for this: the binding of quantifiers is wholly ambiguous, words take on different meanings spontaneously, and we consistently type-raise without realizing it. So it's not the most effective language for conveying meaning unambiguously.

As I promised, I'm going to post something on this topic later today. I'll start a new thread for it, though.

____________________________
Trickster

Official Hold Progress
Favorite Unofficial Holds (I need to play more!)
My Holds

Dischorran
Level: Smitemaster

Rank Points: 3425
Registered: 09-10-2005
IP: Logged

...does the thread title refer to the topic or the average post length?

____________________________

Someone Else
Level: Smitemaster

Rank Points: 2398
Registered: 06-14-2005
IP: Logged

Trickster wrote:
In mathematics this is not really a "debated" topic (apart from constructivism and intuitionism, which are both separate issues). The challenge you have is pausing long enough to learn the definitions under the topic, rather than jumping to intuition-based conclusions.

Oh, I did take time to learn the definitions (I have read a fair bit on set theory). But I guess I do tend to trust to my intuition a fair bit (which is what my first post in this thread was). But after that, you and TripleM gave proofs, so I naturally went and looked them up (and obviously, read what I found on them wrong). I'm still uncertain as to why the correspondence I made doesn't work, so I'm going to ask around a bit more. I just don't like being wrong without finding out why.

Trickster
Level: Smitemaster

Rank Points: 662
Registered: 07-03-2007
IP: Logged

Multiple replies to this thread follow (as I came in late, initially).

This reply is enormous, but it covers many different topics, so it might be worth skimming if you find this interesting. Just skip over the stuff you hate.

12th Archivist wrote:
I can even take it a step in the opposite direction, too. Zero to infinity in degree one could be a single value of a larger set, this particular set having an infinite number of these single values.

It's important to realize here that "infinity" is not a number. Infinity is only a concept that means "this goes on forever without bound". (The different "sizes of infinity" are actual numbers as defined through set theory, but the non-numeric concept of "infinity" still arises there all the time, and it is important to understand the difference.)

I think what you're trying to get at is not representable in the reals, because there is no "smallest" real value, no "least", no "greatest", etc. These are, in fact, some of the main properties which define the reals. You might want to take a look at the surreal numbers, which attack this issue in a formal way:

http://en.wikipedia.org/wiki/Surreal_number

skell wrote:
No two infinities are the same infinities, we had quite a lot of fun reducing expression with infinities on polytechnics to make them from: inf / inf ^2 to 0.5 (just a non-working example).

To be specific, you're not using infinities. You're working with limits that approach infinity, which is what analytical calculus handles. This is not the same thing.

True infinity cancellation, called "normalization", does occur in some branches of physics. It is still (for a minority of mathematicians and scientists) mildly controversial in its application.

Someone Else wrote:
12357 <-> 0.75321
234900 <-> 0.009432
...
Take the real number n.a(1)a(2)a(3)...a(m)... (n is any number of digits, a(m) is one digit for each a(m)). It corresponds to the counting number P(n+1)^(...a(m)...a(3)a(2)a(1)), where P(n) is the nth prime.

The reason these strategies fail is that they can only count real numbers which terminate. Real numbers that continue infinitely would not produce a natural number (no natural number has an infinite number of digits).

da rogu3 wrote:
As for lowest possible number - for whole numbers, it's zero; for integers and real numbers, it's -infinity.

No. -∞ is not a number. There is no lowest possible number: that's what infinity means. More accurately, the integers and reals are unbounded below. The infimum of each, meaning the greatest number that is less than or equal to the integers or reals, does not exist. At least, it is not a real number; you could say it is "-∞" without too much confusion, which basically means it does not exist in the domain of ℝ.

In some forms of numerical analysis, there is occasionally a number line used, called the extended number line, that includes ∞ and -∞ as distinct points. But these are still not numbers in the usual sense. These two objects can be treated as true numbers in the construction of a wheel (a group where everything can be divided, even zero), but this is rarely done, and additional "numbers" like 0/0 must also be created to satisfy the necessary properties.

Most of this math is new, owing to the fact that it has been less than 150 years since people realized what mathematics actually is: the study of the results of arbitrary choices of logical rules. Prior to this everyone was trying to fit math directly to reality, and failing to discover some extremely interesting ideas (many with direct applications to science).

For more on wheels, see http://en.wikipedia.org/wiki/Wheel_theory

The spitemaster wrote:
What I find interesting is infinite sets of numbers. For example, prime numbers. If positive integers is countably infinite what does that mean for prime numbers which are a degree of magnitude less that those numbers?

As da rogu3 indicated, these are the same "size". As it turns out, they're even the same "length" (ordinal). If we strip out all numerical information, the only difference between "naturals" and "primes" is the labels we choose to use for the numbers, which are arbitrary. Both sets are indistinguishable in terms of the way they are ordered.

This is even true for something that is truly "smaller" in a sense. Consider the set of all squares of naturals versus the set of all naturals (we'll eliminate 0 for reasons I will explain later). By the time we reach 1, 100% all numbers are squares. At 4, 50% of numbers are squares. At 9, 33% of numbers are squares. At 100, 10% of numbers are squares. At 10,000, 1% of numbers are squares. This proportion shrinks without bound, so we would say that the squares in their usual order of appearance are "0% dense" on the naturals.

This was in fact the very argument Newton made for why attempting to reason about infinity was absurd (and Newton, like everyone in his time, would not have treated 0 as a natural number). Of course, Newton didn't realize the difference between the "number" of something and the way it is ordered or paired, but he didn't need to. The contributions needed during his time were the ones he produced, and were far more important than pure theoretical math.

As an aside, in Newton's day they were forced to use infinitesimals for calculus (they had not yet discovered the epsilon-delta definition for limits), but mathematicians wisely avoided coming to conclusions about them as numbers. Today we have a formal understanding of infinitesimals, and ironically we no longer need them for basic mathematics. Math is filled with these sorts of ironies: applications which used to be controversial, after 100 years of work we learned to formalize them, and now we discover we never really needed them for what they were originally used: infinitesimals, quaternions, the Axiom of Choice, proofs requiring uncountably infinite sets, and the list goes on.

____________________________
Trickster

Official Hold Progress
Favorite Unofficial Holds (I need to play more!)
My Holds

Trickster
Level: Smitemaster

Rank Points: 662
Registered: 07-03-2007
IP: Logged

Someone Else wrote:
That is quite a bit more elegant than diagonalization, IMO. Clearly, I am wrong. I think that if I saw it formally, I'd be able to understand it easier...

That's what wikipedia is for. EDIT: Wikipedia doesn't have a formal version of it. I'll keep looking.

The proof I made differs from Cantor's original proof, in that it has the power of 100 years of hindsight to make his proof more succinct. It is essentially the same, however. An informal version of Cantor's original proof is here:

http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof

The version of the proof I gave was taken from "Set Theory", the Third Millenium Edition, by Thomas Jech. I reproduce the formal proof listed by Jech below. The proof is verbatim to the text; my only change is replacing some occurrences of the subscript n with the "prime" symbol ', since I can't do reasonable-looking double-subscripts with the font sizes available.

Theorem 4.1 (Cantor). The set of all real numbers is uncountable.

Proof. Let us assume that the set ℝ of all reals is countable, and let c0, c1,..., cn,..., n ∈ ℕ, be an enumeration of ℝ. We shall find a real number different from each cn.

Let a0 = c0 and b0 = ck' where k' is the least k such that a0 < ck. For each n, let an+1 = ci' where i' is the least i such that an < ci < bn, and bn+1 = ck' where k' is the least k such that an+1 < ck < bn. If we let a = sup{an : n ∈ ℕ}, then a ≠ ck for all k. (QED)

____________________________
Trickster

Official Hold Progress
Favorite Unofficial Holds (I need to play more!)
My Holds

Someone Else
Level: Smitemaster

Rank Points: 2398
Registered: 06-14-2005
IP: Logged

Thanks! I sent an email to one of my profs already, though, so I'll see what he says too.

---

[Last edited by Someone Else at 06-26-2011 08:50 PM]