Mathematical Logic...

Error message

Deprecated function: implode(): Passing glue string after array is deprecated. Swap the parameters in drupal_get_feeds() (line 394 of /var/www/pied-piper.ermarian.net/includes/common.inc).

Pages

AuthorTopic: Mathematical Logic...
Or else o'erleap.
Law Bringer
Member # 335
 written Friday, September 9 2005 08:08 Profile Homepage #25
It's been significantly longer since I've studied sets, but here's how I reason through the first two.

1. R contains "more" elements than N. Correspondance isn't exactly an accurate test, but it makes the answer obvious in this case. (An interesting thing to ponder is the set of natural numbers and the set of square numbers. While all square numbers are natural and not all natural numbers are square, the sets are the "same" infinite size because each natural number, n, corresponds to one and only one square number, n^2.)

2. R is the same size as (0,1). The difference is one of scale, not of elements. Again, this isn't formal, but you can hopefully see why they are the same size.

The two above neither prove nor disprove the existence of a set between N and R in size.

—Alorael, who believes that the second step is somewhat arguable. He's willing to propose that in this case such a definition of sizes of infinity is more useful than another definition, although he has no particular grounds for doing so.
Posts: 14579 | Registered: Saturday, December 1 2001 08:00
Khoth
Post Navel Trauma ^_^
Member # 67
 written Friday, September 9 2005 08:44 Profile Homepage #26
Question 4: Where does Q (the set of rational numbers (ie fractions)) fit into all this? Is is bigger or smaller or the same size as N? As R?

[ Friday, September 09, 2005 08:45: Message edited by: Khoth ]

--------------------
Barcoorah: I even did it to a big dorset ram.

desperance.net - Don't follow this link
Posts: 1798 | Registered: Thursday, October 4 2001 07:00
Lt. Sullust
Shaper
Member # 32
 written Friday, September 9 2005 09:02 Profile #27
I suppose that would've been interesting too, but the fact that so many people said false indicates to me that they would say it is similar in size to N...

--------------------
Lt. Sullust
Cogito Ergo Sum
Polaris
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Khoth
Post Navel Trauma ^_^
Member # 67
 written Friday, September 9 2005 09:24 Profile Homepage #28
I wondered, because Alorael's argument as stated would show |N| < |Q|.

--------------------
Barcoorah: I even did it to a big dorset ram.

desperance.net - Don't follow this link
Posts: 1798 | Registered: Thursday, October 4 2001 07:00
Alex
Lifecrafter
Member # 59
 written Friday, September 9 2005 11:03 Profile #29
quote:
Originally written by Lt. Sullust:

Continuum Hypothesis(simplified): There is a set whose size lies between that of the Real Numbers and the Natural Numbers.
I thought the Continuum Hypothesis was that there is NO set whose cardinality is larger than that of the natural numbers and smaller than that of the real numbers (e.g., the rational numbers have the same cardinality as the natural numbers).

I think it's usually accepted as an axiom.
Posts: 950 | Registered: Thursday, October 4 2001 07:00
Or else o'erleap.
Law Bringer
Member # 335
 written Friday, September 9 2005 12:33 Profile Homepage #30
That's a good point, Khoth, but it will take someone with more knowledge of this than I have to prove or disprove it. Let's define |I| as the set of irrational numbers. I'm confident that |N| < |R| and that |N| < |Q|. I'm not sure if |I| < |R| or |I| = |R|, but it's not relevant, because I am reasonably sure that |Q| < |R| and |Q| < |I|. So yes, that would make the set of rational numbers smaller than the set of real numbers. The set of irrational numbers might prove the Continuum Hypothesis by example as well, but I'm not at all confident of it.

—Alorael, who actually leans towards the belief that |I| = |R|, although he can't justify it in any way.
Posts: 14579 | Registered: Saturday, December 1 2001 08:00
Zeviz
Nuke and Pave
Member # 24
 written Friday, September 9 2005 12:57 Profile Homepage #31
Looks like I forgot most of number theory.

However, I still remember how to answer Khoth's question #4. Here is a hint.

Let's look at a quadrant in coordinate plane. The points in it have coordinates (0,0), (0,1), (0,2), (1, 0), (1,1), etc.
We can fill this quadrant with natural numbers if we do it 1 diagonal at a time:

0 1 2 3 4 ... <- x-coordinates
1 1 2 4 7
2 3 5 8
3 6 9
4 10
|
y-coordinates

This method, extended to all 4 quadrants, shows that |N| = number of points in Cartesian coordinate plane.

However, I completely forgot how to prove that some infinities are smaller than others.

--------------------
Be careful with a word, as you would with a sword,
For it too has the power to kill.
However well placed word, unlike a well placed sword,
Can also have the power to heal.
Posts: 2649 | Registered: Wednesday, October 3 2001 07:00
Khoth
Post Navel Trauma ^_^
Member # 67
 written Friday, September 9 2005 13:32 Profile Homepage #32
You make a list of all the real numbers, then show that actually you failed. The standard proof is to muck about with decimal expansions, but there are other ways.

--------------------
Barcoorah: I even did it to a big dorset ram.

desperance.net - Don't follow this link
Posts: 1798 | Registered: Thursday, October 4 2001 07:00
Thuryl
...b10010b...
Member # 869
 written Friday, September 9 2005 15:47 Profile Homepage #33
mathworld.wolfram.com says that the set of rational numbers does in fact have the same cardinality as the natural numbers. (Incidentally, so does the set of algebraic numbers.)

--------------------
My BoE Page
Bandwagons are fun!
Roots
Hunted!
Posts: 9973 | Registered: Saturday, March 30 2002 08:00
Khoth
Post Navel Trauma ^_^
Member # 67
 written Friday, September 9 2005 21:36 Profile Homepage #34
And so does the set of real numbers which can be defined.

--------------------
Barcoorah: I even did it to a big dorset ram.

desperance.net - Don't follow this link
Posts: 1798 | Registered: Thursday, October 4 2001 07:00
Micawber
Agent
Member # 2759
 written Friday, September 9 2005 22:36 Profile Homepage #35
The continuum hypothesis is accepted as an axiom by some, but not by others. I voted "false" on question 3, because in my view CH (and even more so the Generalised Continuum Hypothesis: GCH) unnecessarily restricts the size of the universe. Some results that I like (and many beautiful counter-examples) occur if you postulate Proper Forcing Axiom (PFA) or MA+¬CH.

Forcing, by the way, is a fascinating methodology of taking a universe (=everything) and making it bigger (ie adding some new things that weren't included in everything). I recommend a book called "Set Theory" by Kenneth Kunen. However, that book is quite challenging.

--------------------
Everything I know about the Avernum Trilogy: [ A1 | A2 | A3 ]
Posts: 1104 | Registered: Monday, March 10 2003 08:00
Lt. Sullust
Shaper
Member # 32
 written Saturday, September 10 2005 09:48 Profile #36
quote:
Originally written by Alex:

quote:
Originally written by Lt. Sullust:

Continuum Hypothesis(simplified): There is a set whose size lies between that of the Real Numbers and the Natural Numbers.
I thought the Continuum Hypothesis was that there is NO set whose cardinality is larger than that of the natural numbers and smaller than that of the real numbers (e.g., the rational numbers have the same cardinality as the natural numbers).

I think it's usually accepted as an axiom.
I felt that phrasing the question in that way might give away the first answer too easily...

--------------------
Lt. Sullust
Cogito Ergo Sum
Polaris
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
carmen122
BANNED
Member # 6248
 written Saturday, September 10 2005 13:59 Profile Homepage #37
wow what math nerds, HHAHAHAHAHAHAHHAHAHAHHAHAHAHAh

--------------------
Reeeeeeeeeeeeeeeeeeeir
Posts: 7 | Registered: Friday, August 26 2005 07:00
Student of Trinity
Electric Sheep One
Member # 3431
 written Sunday, September 11 2005 23:39 Profile #38
At the risk of bringing people down, it should be pointed out that there are lots of kinds of size, and what has been discussed in this thread is the relatively arcane version called 'cardinality'. Just as valid, and of a lot more practical use, is metrical size, according to which [0,1] is indeed much smaller than R. This is not set theory anymore, but geometry; but so what?

--------------------
It is not enough to discover how things seem to seem. We must discover how things really seem.
Posts: 3335 | Registered: Thursday, September 4 2003 07:00
Or else o'erleap.
Law Bringer
Member # 335
 written Monday, September 12 2005 07:47 Profile Homepage #39
But geometry has nothing to do with the question under discussion! Don't sap ivory towers!

—Alorael, who will consider the distance from a point to another point 1 unit away to be infinite if he pleases, all right? The distance from a point to another point twice as far away will be twice as infinitely far away, which is actually the same distance. Then some horrible thing with many tentacles will probably come through an acute angle and start Galactic Coring everyone.
Posts: 14579 | Registered: Saturday, December 1 2001 08:00
Khoth
Post Navel Trauma ^_^
Member # 67
 written Monday, September 12 2005 08:29 Profile Homepage #40
I reckon it's reveal the answers time.

|N| < |R|:
This proof isn't my favourite, but it doesn't have as many subscripts so it's easier to put on a forum.
It's obviously not true that |N| > |R|, because N is a subset of R.
Suppose |N| = |R|. If this was the case, we could make a big list of all the real numbers, like so:
1: 23.553456765...
2:  4.0000000...
3:  3.14159....
.
.
.
Now we take the diagonal after the decimal point (shown in bold), which makes the number 0.501....
Then we change every 5 to a 6, and every non-5 to a 5, getting 0.655....
This number can't be the first in our list, because the first digit is different. It can't be the second, because the second digit is different, and so on.
So it can't be on our list. But our list was supposed to be of all the real numbers. Contradiction, so the original assumption (that |N| = |R|) must be wrong.

|(0,1)| = |R|
Consider the function f(x) = tan(90x) (in degrees)
This function takes everything in (0,1) to something in R, and everything in R is covered by this. So there is a one-to-one mapping, so the sets are the same size.

-----
Continuum hypothesis: It is consistent for it to be true, and consistent for it to be false. So there is a model of set theory which has a set of size between N and R, which is good enough for me. :-)

Edit: Formatting

[ Monday, September 12, 2005 08:31: Message edited by: Khoth ]

--------------------
Barcoorah: I even did it to a big dorset ram.

desperance.net - Don't follow this link
Posts: 1798 | Registered: Thursday, October 4 2001 07:00
Jumpin Salmon
? Man, ? Amazing
Member # 5755
 written Monday, September 12 2005 13:55 Profile #41
I hurt now.

*owww*
Posts: 4114 | Registered: Monday, April 25 2005 07:00
Sturg
Master
Member # 4614
 written Monday, September 12 2005 16:03 Profile Homepage #42
Eh, I'll just leave it that if |N| = inifinity, then |R| = infinity squared. :P

--------------------
-ben4808

For those who love to spam:
CSM Forums
RIFQ
Posts: 3360 | Registered: Friday, June 25 2004 07:00
Micawber
Agent
Member # 2759
 written Tuesday, September 13 2005 09:52 Profile Homepage #43
quote:
Originally written by Benny Boy:

Eh, I'll just leave it that if |N| = inifinity, then |R| = infinity squared. :P
No no, |N|^2=|N|.

|R|=2^|N|

Seriously :P

Edit: Fixed an idiotic mistake. Goodness, my set theory is rusty...

[ Tuesday, September 13, 2005 09:57: Message edited by: Micawber ]

--------------------
Everything I know about the Avernum Trilogy: [ A1 | A2 | A3 ]
Posts: 1104 | Registered: Monday, March 10 2003 08:00
Lt. Sullust
Shaper
Member # 32
 written Tuesday, September 13 2005 10:27 Profile #44
I'm not completely convinced by that little statement of yours that |R| = |P(N)

--------------------
Lt. Sullust
Cogito Ergo Sum
Polaris
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Micawber
Agent
Member # 2759
 written Tuesday, September 13 2005 10:50 Profile Homepage #45
It is, nonetheless, provable in ZFC. I leave the details as exercise for the reader.

Edit: Always wanted to say that

[ Tuesday, September 13, 2005 11:20: Message edited by: Micawber ]

--------------------
Everything I know about the Avernum Trilogy: [ A1 | A2 | A3 ]
Posts: 1104 | Registered: Monday, March 10 2003 08:00
Arancaytar
Law Bringer
Member # 2984
 written Tuesday, September 13 2005 13:49 Profile Homepage #46
quote:
I leave the details as exercise for the reader.
That is the single most annoying statement I've come across in any text. The "details" frequently involve hours or days of brain straining. :rolleyes:

--------------------
The Encyclopaedia Ermariana <-- Now a Wiki!
"Polaris leers down from the black vault, winking hideously like an insane watching eye which strives to convey some strange message, yet recalls nothing save that it once had a message to convey." --- HP Lovecraft.
"I single Aran out due to his nasty temperament, and his superior intellect." --- SupaNik
Posts: 8752 | Registered: Wednesday, May 14 2003 07:00
Lt. Sullust
Shaper
Member # 32
 written Tuesday, September 13 2005 14:04 Profile #47
Alrighty, I've done some digging...

S = the set of all sequences of 0's and 1's

|P(N)| = |S|
|R| = |S|

Thus we have |P(N)| = |R|.

--------------------
Lt. Sullust
Cogito Ergo Sum
Polaris
Posts: 2462 | Registered: Wednesday, October 3 2001 07:00
Micawber
Agent
Member # 2759
 written Tuesday, September 13 2005 21:51 Profile Homepage #48
Yup, that's the way Cantor proved it, in 1895.

The power set of N is, of course, identifiable with the set of all mappings N -> {0,1}. And every real number has a binary expansion.

Aran, I totally agree. But it's so much fun when you're the one setting the challenge. I really must write a textbook some time.

--------------------
Everything I know about the Avernum Trilogy: [ A1 | A2 | A3 ]
Posts: 1104 | Registered: Monday, March 10 2003 08:00

Pages