# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
ralphmerridew
Posted: Wed Oct 15, 2008 1:06 am    Post subject: 1

I think I have a proof of that statement:

Let g:Q->Z+ be a bijection (possible since rationals are known to be countable). Let h:R->[0,1] be a bijection

Consider the set of functions f:Q->[0,1]

i: The set can be injected into the reals.

Associate a function f with the real number sum(i=1 to inf: d_i * 10^-i) where
d_i = the m-th digit of the decimal expansion of f(g(k)) if i = ((2m+1)*2^(k+1)) for positive m and k
d_i = 0 otherwise

ii: The continuous functions k:R->R can be injected into those functions f. (Calculate h(k(x)) at each rational x. Continuity allows at most one k to map to any f.)

iii: Putting those two injections together gives an injection from functions k to R.

iv: And the reals can be injected into the continuous functions trivially.
extro...*
Posted: Tue Oct 14, 2008 11:58 pm    Post subject: 0

Sets with cardinality c

A great many sets studied in mathematics have cardinality equal to c. Some common examples are the following:

* the real numbers R
* any (nondegenerate) closed or open interval in R (such as the unit interval [0,1])
* the irrational numbers
* the transcendental numbers
* Euclidean space Rn
* the complex numbers C
* the power set of the natural numbers (the set of all subsets of the natural numbers)
* the set of sequences of integers (i.e. all functions N → Z, often denoted ZN)
* the set of sequences of real numbers, RN
* the set of all continuous functions from R to R
* the Cantor set
* the Euclidean topology on Rn (i.e. the set of all open sets in Rn)
* the Borel σ-algebra on R (i.e. the set of all Borel sets in R)
extro...*
Posted: Tue Oct 14, 2008 10:55 pm    Post subject: -1

If by curve you mean a continuous function, it sounds like an interesting problem - to prove that the size of the set of all such functions is the same as the size of the set of reals ... or greater?

For non-continuous functions, one need only consider that for every set R of reals, there is some "characteristic" function f such that f(x) = 1 if x is in R, and f(x) = 0 if x is not in R. It's trivial to prove the powerset of an infinite set S is of greater cardinality than S itself, so similarly the set of functions from R to {0,1} is of greater cardinality than the set R. But many of these characteristic functions are non-continuous (with some exceptions).

Any ideas about the continuous case? How to show the set of continuous functions from R to R is larger than R, or the same as R? (it's at least as big as R) ... The problem sounds simple enough.
extro...*
Posted: Mon Oct 13, 2008 7:52 pm    Post subject: -2

MTGAP wrote:
Apparently, it's been proved that there are more curves than there are real numbers. ... So what's the proof?

Define "curve".

If you mean functions from reals to reals, it's pretty straightforward.
MTGAP
Posted: Mon Oct 13, 2008 5:29 pm    Post subject: -3

Apparently, it's been proved that there are more curves than there are real numbers. But I can't find this proof anywhere; no one seems to care about it, and instead they bother with things like proofs that there are more irrationals than rationals.

So what's the proof?
extro...*
Posted: Sun Sep 28, 2008 3:28 am    Post subject: -4

Nsof wrote:
I think your first question depends on the Continuum hypothesis

A bit rusty, but I think:
1) CH (continuum hypothesis) implies aleph null infinities
2) "CH is false" does not imply aleph null infinities, nor does it imply more than aleph null.

With CH, infinities are ordered like the natural numbers, each having one that is greater, with none in between the two. Without CH, infinities may be ordered like the non-negative rational numbers - aleph null, but for any two that are not equal, there are others between them.
Nsof
Posted: Sat Sep 27, 2008 10:53 pm    Post subject: -5

I think your first question depends on the Continuum hypothesis
MTGAP
Posted: Sat Sep 27, 2008 3:54 pm    Post subject: -6

Some more questions:

1. If there are infinite infinities, how many is that? Are there aleph null infinities? Are there aleph (aleph null) infinities?

2. If there are infinite infinities, that means there are numbers between irrationals, right? Or does it mean that all the infinities above aleph one are not representable with numbers? If so, are they representable at all?
ralphmerridew
Posted: Thu Aug 21, 2008 6:19 pm    Post subject: -7

Chuck: That is possible. Forming a bijection beween the power set of the integers and the integers is not possible.
alphatango
Posted: Thu Aug 21, 2008 5:31 pm    Post subject: -8

You can indeed do such a thing -- see this everything2 article, for example. In particular, it deals with the problem under your scheme where two different subsets map to the same thing; 0.0111... and 0.1000..., for example, would represent the sets {2, 3, 4, ...} and {1}, respectively, but the two binary numbers are equal.
Chuck
Posted: Thu Aug 21, 2008 3:44 pm    Post subject: -9

It seems like you should be able to represent all of the subsets of the integers as all of the binary real numbers from zero to one. Each binary number would represent one subset. If an integer is in the subset then the binary digit in that position in the corresponding real number would be one, otherwise it would be zero. That way each real number from zero to one corresponds to a different subset of the integers since each such point has a different binary expansion. None would be left out. No subsets of the integers would be left out since each would convert to a different binary number. They'd be the same order of infinity.
MTGAP
Posted: Sun Aug 17, 2008 8:41 pm    Post subject: -10

ralphmerridew wrote:
MTGAP: The proposition that aleph-one is the power set of aleph-null (the "Continuum Hypothesis") is undecidable within standard set theory.

Wonderful.
ralphmerridew
Posted: Sun Aug 17, 2008 10:35 am    Post subject: -11

MTGAP: The proposition that aleph-one is the power set of aleph-null (the "Continuum Hypothesis") is undecidable within standard set theory.
Bicho the Inhaler
Posted: Sun Aug 17, 2008 4:33 am    Post subject: -12

I think at this point you should just get a good discrete mathematics textbook. Your questions seem a bit ill-posed, but reading about cardinal numbers would go a long way toward addressing whatever you have in mind. (I'd recommend the book I had in high school, but I don't remember the exact title or the author. )
MTGAP
Posted: Sun Aug 17, 2008 4:14 am    Post subject: -13

Is it true that if you have 2^infinity objects, you cannot line them up, no matter how long the line is? And that you need an infinite number of dimensions to place all the objects?

I read somewhere that 2^infinity is equal to aleph one, and all alephs above one. Is that true? It doesn't seem right to me.
Chuck
Posted: Tue Aug 05, 2008 8:49 pm    Post subject: -14

Of course you can do something that's impossible if you don't actually have to do it to consider it to be done.
ralphmerridew
Posted: Tue Aug 05, 2008 8:29 pm    Post subject: -15

Chuck, from a practical POV, it is impossible to generate a random real number, but I already pointed out that we are talking theoretically.
GH
Posted: Tue Aug 05, 2008 8:08 pm    Post subject: -16

Infinity: not adequate for real-life situations.
Chuck
Posted: Tue Aug 05, 2008 7:10 pm    Post subject: -17

But you still haven't generated a real random number because you can never know to an infinity of decimal places exactly where the coin is. We don't even know for sure that there are an infinity of places to put it. Space might be grainy on a low lever.
GH
Posted: Tue Aug 05, 2008 7:09 pm    Post subject: -18

I don't think that's a fair interpretation of "zero probability."

"Zero probability" really just reflects that as the number of equally-likely possible results increases, the probability of any given result decreases. If the number of possible results increases without bound, the probability of any given result approaches zero.

Did you look at that Wikipedia page about what the terms "surely" and "almost surely" mean? I found it interesting, particularly because it included examples of flipping a coin and throwing an ideal dart at a unit square!
Jack_Ian
Posted: Tue Aug 05, 2008 7:05 pm    Post subject: -19

There are an infinite number of locations where I can place a coin in a room. Even if I remove the coin and replace it, it will not be in exactly the same position.
Before I place the coin anywhere, every one of the infinite locations has 0 chance of being selected. This is true even though I am more likely to place the coin on the floor than on the ceiling, since that would be impossible.
Once I place the coin in the room, I have made one of these zero probability events occur.
Even if I decided to cover a particular spot on the floor, the inaccuracy of my movements would mean that the infinite number of possibilities within 1 mm of the final resting place were equally likely to have been chosen by me and so all had probability zero.
Unless, of course, space is granular in nature, in which case there are only a finite number of locations in the room.
Chuck
Posted: Tue Aug 05, 2008 4:18 pm    Post subject: -20

It's not impossible, it just won't be selected at random. Isn't that what zero probability means? You can certainly intentionally select 7 from the set of all integers, but not at random.
ralphmerridew
Posted: Tue Aug 05, 2008 4:14 pm    Post subject: -21

GH, that wouldn't work because it's impossible to make a fair selection from the integers (or any countably infinite set).

And Chuck, why do you keep assuming that "event has probability 0" is equivalent to "event is impossible"?
Chuck
Posted: Tue Aug 05, 2008 4:13 pm    Post subject: -22

How do you choose a particular integer at random from the entire set with equal probability for each? It would seem that it can't be done. What is the probability that it will have more than 1000 digits? A finite number of them have 1000 digits or fewer and an infinity have more so it looks like you'd have a 100% chance of choosing a number with more then 1000 digits. But the same argument applies to any number of digits.
GH
Posted: Tue Aug 05, 2008 4:05 pm    Post subject: -23

Hm. So your issue is not with the fact that any given element has the same probability is any other element, but that we don't have a realistic notation for the particular element that we've chosen?

What if the original problem were rephrased so that we're choosing random integers until we choose 0?
Chuck
Posted: Tue Aug 05, 2008 3:57 pm    Post subject: -24

My problem is, if you have an infinity of things from which to choose, how can you choose one at random with equal probability for each? I see no way that it can be done.
GH
Posted: Tue Aug 05, 2008 3:52 pm    Post subject: -25

Chuck wrote:
If something has a probability of zero of happening at random then it won't happen.

That's both true and false.

If you had a finite number of possible results, and one result had a probability of 0, then it could never happen. But when you have an infinite number of possible results, the probability of any one happening is calculated as a limit, which leads to assign zero probability for things that can happen.

Here's what I find annoying about that. If I randomly choose any integer, the probability of choosing 11 is 0. The probability of choosing 37.5 is also 0. Clearly, though, they're different kinds of 0. Argh!

Chuck
Posted: Tue Aug 05, 2008 3:25 pm    Post subject: -26

But can you choose a point in such a way that each has equal probability?
Jack_Ian
Posted: Tue Aug 05, 2008 3:20 pm    Post subject: -27

Every point has an equal probability of being chosen, namely 0, but if you randomly choose a point then you have made something with a probability of 0 actually occur.
Chuck
Posted: Tue Aug 05, 2008 2:46 pm    Post subject: -28

It's not impossible. You can intentionally choose a point on the boundary. If something has a probability of zero of happening at random then it won't happen.
ralphmerridew
Posted: Tue Aug 05, 2008 2:38 pm    Post subject: -29

Where am I disputing that the probability is zero? I'm claiming that "probability 0" != "impossible". (The second implies the first, but they are not equivalent.)
Chuck
Posted: Tue Aug 05, 2008 1:30 pm    Post subject: -30

Let's see, then, if you randomly select a point in a figure, the probability of landing on the boundary is zero. But that's not very satisfying because the boundary is there so it seems that it ought to be possible to land on it, but saying there's zero chance of landing on it makes it sound like it can't happen. So instead of saying that the probability is zero we'll call it measure zero instead. That makes it sound like it's not really zero. We'll also just overlook the fact that we can't actually select a random point with uniform probability at all.
ralphmerridew
Posted: Tue Aug 05, 2008 9:36 am    Post subject: -31

Chuck, modern probability theory is not strictly frequentist. It's part of measure theory.

The perimeter of an shape has area 0, but the boundary still exists.
Chuck
Posted: Tue Aug 05, 2008 7:14 am    Post subject: -32

It's easy to make an extremely low but still positive probability event happen. Some sequence of numbers will come up if I toss a die a thousand times. I've never heard of a zero probability event actually occurring.
Bicho the Inhaler
Posted: Tue Aug 05, 2008 6:25 am    Post subject: -33

The "it has probability zero, so it can't happen" argument is tempting, but it's totally fallacious, and I'll try to explain why. It's because the concept of probability is useless when applied to an event after it occurs: the event either happened or it didn't happen. To assign a probability to an event, you have to do it before the event occurs.

To illustrate this, here's an easier thought experiment: suppose I flip an unbiased coin 200 times. The result:

HTTHHTHTTHHHTHTTHTHTTHTHHTTHTTTHHTHTHTHHTTHTHTTHHHHHTHTHHTTHHTTHHHHTTHTHTTTHHHTTHTHTTTHTHTHHHTHHHTHT
HTHHHHTTTHHHHHTHTTTTTTTHHHTTTHHHTHHTTHTHTTTTTHTHHHHHTTHTTHHHHTHTTTHHHHHHTTHHHTTTTHTHTHTHHTHHHHTHHHTT

Now what was the probability of obtaining that result? 1/2^200, right? That's astronomically small. Nevertheless, it's completely unexceptional, regardless of the fact that the probability of that event was supposedly so incredibly close to zero. The problem is that we can't say it has probability 1/2^200 after it has already happened. There was a time, namely before I started flipping coins, when we could have written down that sequence of heads and tails and said the probability of obtaining that sequence was 1/2^200, but we missed that opportunity, and so we missed our chance to observe an event of probability so small that you'd be more likely to win 5 lotteries in the same day.

The same is true with these so-called "events of probability zero." There is no qualitative difference. If I choose a random real number uniformly between 0 and 1 and show it to you, you have lost your right to claim that you've seen a event of probability zero, since it happened before you decided to give it a probability. However, there was a time, namely before I showed you the number, when you could have said "the probability of you showing me this number is zero," and you would have been correct, no matter what number you had in mind. And there's no contradiction here: if you first select a number (by any means) and then select another uniformly random number between 0 and 1, there is no chance at all that the two will match. So it really does have probability zero.

Edit: Before anybody says that probabilities can sometimes be assigned after events occur (for example, I can still consider odds on a baseball game I taped from TV if I didn't see it and nobody told me what happened), the "occurrence" I'm talking about is really the knowledge of the result. Probability is a tool for reasoning with limited information, and when you gain complete information, there's no more talk of probability. (In general, when you gain any information about an event, its probability changes, and its old probability is useless.)
Chuck
Posted: Tue Aug 05, 2008 2:29 am    Post subject: -34

It means it won't happen by chance.
ralphmerridew
Posted: Tue Aug 05, 2008 2:23 am    Post subject: -35

"Having probability 0" does not mean the same as "can't happen".
Chuck
Posted: Tue Aug 05, 2008 2:21 am    Post subject: -36

In theory the probability of hitting any given point is zero but the dart has to hit somewhere. So in theory something that can't happen is certain to happen.
ralphmerridew
Posted: Mon Aug 04, 2008 11:34 pm    Post subject: -37

When I started with an "ideal dart", I thought it was clear that I was treating this as a theoretical problem.
Chuck
Posted: Mon Aug 04, 2008 11:26 pm    Post subject: -38

ralphmerridew wrote:
Imagine throwing an ideal dart at a target which is a square with side 1 until it lands on or in the target. Take the x-coordinate of the point for your result.

You'd need to be able to measure the distance along the x coordinate with infinite precision. The dart would be sticking in some point on the board but how do you turn that into your random number?