Oh. I overlooked the connection from subsets to infinite bitstrings. Finding a bijection from the latter is still tricky, but obviously easier than going directly from subsets.
Thanks for the detailed writeups!
Describing a bijection between natural and rational numbers is easy: Make a two-dimensional grid of all the rational numbers in such a manner that the numerator increases on one axis and the denominator on the other. Then just index each element in a diagonal fashion.
(Although, thinking about it, creating a grid of rational numbers in that manner will create many repetitions. Their numerator-denominator pairs may be themselves unique, but their value will be the same as other rational numbers in the grid. In this sense a blind indexing will not be a true bijection, as more than one natural number will be mapped to the same rational number. However, I'm assuming that rational numbers that have already appeared in the indexing can be skipped.)
Anyway, I was thinking if there was an equally easy and intuitive way of building a bijection between real and complex numbers.
A bijection between reals and complex numbers is easy. Discard the real part's sign and take the floor of the real and imaginary parts, then discard the sign of the imaginary part's floor and interleave the bits. If the real part is nonzero, append a sign bit for the imaginary part. Then, if both the real and complex parts are nonterminating when written in binary, interleave the fractional bits as well. Otherwise, if one part terminates and the other does not, take the first bit of the part that terminates. If it is 1, invert the remaining bits, otherwise, do not invert them. Then, interleave them with the part that does not terminate. Otherwise, both parts terminate. Then, multiply the real part by 3 and keep the imaginary part as it is. If the resulting integer part is 1, invert the fractional bits, and if it is 2, invert the fractional bits of the imaginary part. Then, interleave the two numbers as usual. Finally, flip the sign if the real part was negative, or if the real part was zero and the imaginary part was negative.
Edit: Oh crap, forgot the signs. Fixed now.
Before we do any bitwise interleaving, we'd need to define a unique bit-representation of a real. There's always the duality of 1.0000... and 0.1111..., which we need to get rid of.
One might be tempted to just disallow all representations that end in an infinite series of 1, thus working on a well defined subset of all infinite bitstrings. But bitwise interleaving is not a bijection between that set and that set squared: try a number ending in .....10101010... It is within the allowed set. But when splitting into two numbers, one will end in ...1111.. and is thus outside the set.
Bitwise interleaving is better suited to programming problems, where bit representations tend to be finite (and thus unique).
I guess the easiest way would be to scroll up 5 posts, where p4wn3r already described a bijection between reals and all infinite substrings. Those are safe to interleave, just pretty far from the binary representations we're used to.
In the above scheme, that is taken care of. All terminating representations are assumed to end with 0's. If after deinterleaving you get a string that ends with 1's, it simply maps to a different part of the unit interval which I have divided into 3 (for 00's, 01's and 10's). On the other hand, mapping from reals to infinite substrings and then interleaving does not work, since the resulting string might then end in 1's. Oh, I see what you're getting at.
Is the set of all possible infinite bit strings larger than ℝ?
(Since an infinite amount of numbers can be represented in two ways as a bit string, is there a bijection between the two sets?)
Is the set of all possible infinite bit strings larger than ℝ?
(Since an infinite amount of numbers can be represented in two ways as a bit string, is there a bijection between the two sets?)
No, you can do a 1:1 mapping like this: for the recurring 1's stick a 1 on the front of the string, and for terminating decimals stick a 0 on the end of the string. Now every string maps to a unique real number.
This technicality generalises completely, so the possibility of equivalence between two different decimals is never a flaw in the proof of a bijection.
I don't understand how that would work. Wouldn't the result simply be the binary representation of another real number?
He's talking about mapping strings that end in 1's and strings that end in 0's to different disjoint intervals, I think. Which I did a few posts up. But you also need to invert the bits in one of the cases, or you'll end up with two of each integer and no half-integers.
For the fractional part, we can map terminating numbers like this, by taking the first bit and XORing it with the rest:
0 -> 00000000…
0.125 -> 01000000…
0.25 -> 10000000…
0.375 -> 11000000…
0.5 -> 11111111…
0.625 -> 10111111…
0.75 -> 01111111…
0.875 -> 00111111…
Whereas nonterminating numbers are written normally:
0.2 -> 00110011…
0.4 -> 01100110…
0.6 -> 10011001…
0.8 -> 11001100…
Lets say you're playing pool on a frictionless surface, and you hit the cue ball from the bottom left hand pocket at a 45° angle. What would be the formula for figuring out how many cushions the cue ball bounces off of before it goes into one of the corner pockets? Remember, the pool table can be any dimension. Whether it be 2x3 or 5435x4356.
Without loss of generality, assume that the ratio is expressed in simplest form. So we have long side length L, short side length S, and gcd(L,S) = 1. Also assume that the long cushions are aligned with the x-axis.
Consider the long cushions first: at each bounce, the ball will go in the pocket if the total distance (scalar distance, not vector displacement) travelled in the x-axis ≡ 0 (mod L). At each bounce on the L-cushion, the x-axis distance travelled increases by S. Since gcd(L,S) = 1, this condition will first be met when the total distance travelled is L×S, after L - 1 bounces on the long cushions (not counting the ball finally being potted as a bounce).
A similar argument shows that there will be S - 1 bounces on the short cushions.
The total is therefore L + S - 2, once L and S have been expressed as the simplest ratio.
If the long cushion is an irrational number times the length of the short cushion, the ball will never be potted. (Of course, we're assuming pointlike balls and perfect pockets here, not to mention perfect cushions.)
All the previous talk of cardinalities got me thinking about something I once asked my real analysis professor many years ago: What is the cardinality of the set of all simple, closed curves in two dimensions, excluding all rotations and reflections? If you cannot prove it easily, can you provide a lower bound on its cardinality? If you can quickly prove that its cardinality is greater than aleph-2, then it also serves as an elegant proof of the popular question, Can One Hear the Shape of a Drum? Do you see why?
Lets say you're playing pool on a frictionless surface, and you hit the cue ball from the bottom left hand pocket at a 45° angle. What would be the formula for figuring out how many cushions the cue ball bounces off of before it goes into one of the corner pockets? Remember, the pool table can be any dimension. Whether it be 2x3 or 5435x4356.
I think that would be impossible to express in closed form, and even with a recursive function it would become amazingly complicated, depending on how accurately you want to model the physics of the scenario.
Normally the table causes the ball to rotate (just moving on the table causes it to start to rotate in that direction, and then when it bounces off a wall, its rotation changes, and all this makes the exiting angle different from the incoming angle; also the speed of the ball comes into play due to all this). Even if you consider the table so frictionless that it doesn't cause the ball to rotate at all, ie. its orientation never changes, and the walls 100% elastic, then there's still the question of the size and shape of the pockets.
I'm at a complete loss what aleph-2 means, and the Wikipedia page doesn't really help, but I'd imagine the set of all two-dimensional curves to be the same size as the set of all infinite collections of real numbers. I have no idea what its aleph number would be, though.
Anyway, a curve is just an infinite collection of real points (right?), so I'd guess the cardinality of the set of all curves would be 2|ℝ|. I don't see the fact that the curves are closed and simple or the exclusion of rotations and reflections factoring into that.
For the fractional part, we can map terminating numbers like this, by taking the first bit and XORing it with the rest:
0 -> 00000000…
0.125 -> 01000000…
0.25 -> 10000000…
0.375 -> 11000000…
0.5 -> 11111111…
0.625 -> 10111111…
0.75 -> 01111111…
0.875 -> 00111111…
Whereas nonterminating numbers are written normally:
0.2 -> 00110011…
0.4 -> 01100110…
0.6 -> 10011001…
0.8 -> 11001100…
This is a bit embarrassing to admit, but I can't understand anything of what you are saying there.
I mean, I understand binary, and I understand how integers and reals can be represented with them (after all, I'm a programmer), but I still have no idea what you are saying there (or how it solves the problem).
What is the cardinality of the set of all simple, closed curves in two dimensions, excluding all rotations and reflections? If you cannot prove it easily, can you provide a lower bound on its cardinality? If you can quickly prove that its cardinality is greater than aleph-2[..]
Going by wikipedia about the aleph numbers.. We'll be assuming AC for this one, right?
With C being the set of 2d-curves and P(x) the power set of x, there's obviously an injection from
C -> P(R x R)
where you just map a curve onto the set of all points (x,y) on the curve (or inside the curve, either one works). Since
| RxR | = |R| = aleph-1
we know that
|C| <= |P(RxR)| = 2^aleph-1 = aleph-2
Since you hinted that it must be greater than aleph-2 I'll accept that as proof by authority and state:
|C| = aleph-2
Or we could find an injection from an aleph-2 set onto the curves, but I'm having trouble with that.
My first idea was to start with
P(R+) -> C
Order the given set, then draw a "circle" around the origin with varying radius. Always starting with the smallest radius at the same angle (i.e. towards positive y direction) would account for rotations, always going clockwise would account for reflections.
But we need to interpolate the missing pieces of the curve, and if we just added one of the interpolated points to the initial set, we have a second set that maps to the same curve. Or rather an uncountably infinite amount of sets mapping to the same curve.
And there's also the problem of infinite subsets of R+ potentially neither being countable, nor having a smallest element, so the whole "ordering" idea goes out the window.
I'm at a complete loss what aleph-2 means, and the Wikipedia page doesn't really help, but I'd imagine the set of all two-dimensional curves to be the same size as the set of all infinite collections of real numbers. I have no idea what its aleph number would be, though.
Anyway, a curve is just an infinite collection of real points (right?), so I'd guess the cardinality of the set of all curves would be 2|ℝ|. I don't see the fact that the curves are closed and simple or the exclusion of rotations and reflections factoring into that.
The aleph numbers are a way of expressing infinite cardinalities. I agree that Wikipedia can be very frustrating when trying to learn a new subject in a technical field, especially math or physics.
If you are not familiar with cardinality, it is essentially the number of elements in a set. Say you have some set:
{5, 7, apple, the entire works of Shakespeare, love}
In the above example, there are five elements and so the cardinality is 5. Just count them up and there it is.
Now let's work with a smaller set (and I'll restrict its elements to numbers for the sake of simplicity):
{0, 5, 7}
The cardinality of this set is 3. This set also has many subsets, including {5}, {0, 5}, and {5, 7}. In fact, we can list all the subsets of this set and place them in a new set. We'll call this set the power set of this set, for reasons that will become clear in a minute. The power set is as follows (I will break up its elements line by line so that it's easier to read):
{{},
{0},
{5},
{7},
{5, 7},
{0, 7},
{0, 5},
{0, 5, 7}}
This is an exhaustive list of all subsets of the set, where the last element I listed is the complete set and the first element is the empty set. The power set has eight elements. You can show with some binary representation that the power set of a set with finite cardinality C is necessarily 2C.
From here, I skip over a few paragraphs (unless you'd like me to fill in some details) and I'll just cut to two important theorems:
1) Two sets share a cardinality if and only if there exists a bijection (a one-to-one and onto function) between them.
2) Given some set, its power set necessarily has a greater cardinality than its own cardinality.
These two facts are pretty much trivial if we stick to finite sets. For example, with the sets {0, 5, 7} and {apple, orange, banana}, we can form the bijection (just one example of six):
0 <--> banana
5 <--> apple
7 <--> orange
For the second theorem, all we have to do is note that the cardinality of any power set is 2C, where C is the cardinality of the original set. If C is a non-negative integer, then 2C is clearly larger than C.
But these theorems are nontrivial (yet still hold) for infinite sets. For example, it is known that there are just as many even integers as there are integers and there are just as many primes as there are rational numbers. All we have to do is form a bijection between these various sets and the proof is complete. Because it is often taken to be the "smallest infinity", aleph-0 is defined to be the cardinality of the set of all integers. Just think of aleph-0 as a fancy way of saying "infinity", except that you're strictly referring to cardinalities and it's a particularly "small" infinity.
However, we can define a larger infinity by taking the power set of the set of all integers. By theorem 2, the cardinality of this set is necessarily strictly greater than aleph-0. We define this new cardinality to be aleph-1. (Incidentally, it is undecidable without a further axiom whether there is another cardinality between aleph-0 and aleph-1. Fortunately, it's irrelevant to the problem at hand.) Aleph-1 is also infinity, but it's a strictly larger infinity than aleph-0. It also happens to be the cardinality of the set of any continuum.
Finally, we are ready to construct aleph-2. To define it, we just take the power set again! That is, we need to take the set of all subsets of the set of all subsets of the integers. This is an even larger cardinality and so is given a new name, aleph-2. You can continue taking power sets to construct aleph-3, aleph-4, and so on.
So the question is whether the set of all simple, closed, two-dimensional curves (or equivalently, the set of all simply connected regions in two dimensions) has cardinality less than, equal to, or greater than aleph-2.
As for your guess that the cardinality of the set of all curves being 2|ℝ|, I wouldn't be so sure. A huge number of those "curves" aren't simple. In fact, if you were to pick a "random" subset of all ℝ, you would almost surely have disjoint set. This hints to me that the cardinality of the set of all simple, closed curves is actually strictly less than 2|ℝ|. I could be wrong, though.
Tub wrote:
Bobo the King wrote:
Since you hinted that it must be greater than aleph-2 I'll accept that as proof by authority and state...
Actually, I'm not sure what the answer is. I only hinted that it is likely to be greater than or equal to aleph-2, but this is just a guess. It's based on two observations:
1) There are a lot of simple, closed curves.
2) There are some pairs of drumheads that produce the same timbre.
I think it's unlikely that the cardinality is less than aleph-2, since this would imply that even though you cannot hear the shape of a drum, there are many more timbres than there are drums. This would be highly "coincidental".
I haven't had a chance to look too closely at the rest of your post. Looks like an interesting start, though.
There's a trivial injection
R+ -> C
where you map each positive real number x to the triangle (0,0), (-1,0), (x,2) - they're unique including rotations and mirroring, even including scaling and translations.
So it's at least aleph-1; intuitively, one would expect it to be strictly larger.
It's also at most aleph-2; intuitively, one would expect it to be strictly less.
I'm hoping it's right in the middle so we can get a paper out of this ^^
Bobo the King wrote:
This hints to me that the cardinality of the set of all simple, closed curves is actually strictly less than 2|ℝ|.
Bobo the King wrote:
I think it's unlikely that the cardinality is less than aleph-2
|2^R| = aleph-2.You can't really assume both at the same time ;)
First of all: thank you for the explanation of aleph numbers. Although you started a lot more basic than needed, the last bit was precisely what I needed.
Second:
Bobo the King wrote:
As for your guess that the cardinality of the set of all curves being 2|ℝ|, I wouldn't be so sure. A huge number of those "curves" aren't simple. In fact, if you were to pick a "random" subset of all ℝ, you would almost surely have disjoint set. This hints to me that the cardinality of the set of all simple, closed curves is actually strictly less than 2|ℝ|. I could be wrong, though.
To me this sounds a lot like: "a huge number of the numbers in ℚ aren't in ℤ, so ℤ must be smaller than ℚ". Although intuitive, incorrect (your disjoint set argument goes too, as a nice bonus). I'll stick with my guesstimation of aleph-2.
ok bobo, this is starting to annoy me. You said you asked your professor, but claim you don't know the answer - so a math professor didn't know, either?
I've been trying to approach it step by step. Starting with the not-so-curvy-curves, also called polygons.
There's a bijection from R to the set of all polygons in 2-space, by the following algorithm:
a) transform the real into an infinite bitstring (like we discussed a few pages ago)
b) read a positive integer from the beginning of the bitstring (there are ways to read an integer of arbitrary size while consuming only a finite amount of bits. I can elaborate if you want me to). Add 3 to the integer to get n = the amount of vertices of the polygon.
c) by bitwise deinterleaving, split the rest of the bitstring into 2*n infinite bitstrings. Transform each of these back into a real and use them as coordinates for the vertices.
So the set of polygons has cardinality aleph-1; the set of simple polygons cannot be larger.
We can simply make it a bit more curvy by allowing each edge to be a bezier curve, by reading an additional 2 points per vertex to be used as control points.
But how "curvy" can we make it without requiring more than a finite amount of reals per edge? What if our curve is fractal in nature, like one connected region of the mandelbrot set, and cannot possibly be approximated by a polygon with a finite amount of edges?
At this point I'm not sure about the exact definition of a simple, closed curve. But let me try one final injection:
P([0,1]) -> C
We take a subset S of [0,1] and construct the interior area of a curve as
I = { (x, 0) | x \in S } \union { (x, y) | x \in [0,1], y \in (0, 1] }
We get a 1x1 block where one of its edges is a bit fuzzy. It is unique wrt rotating, scaling and translations; to make it unique wrt reflections we could just add another feature at either side.
For any point in the set, there's another point arbitrarily close to it. Is that property enough to claim that it's connected, and to claim that its border is a simple, closed curve?
If so, we finally know
aleph-2 <= |C| <= aleph-2
The proofs for both bounds work regardless of the restrictions wrt rotations and reflections; so the set of all curves, and the set of non-congruent curves must both have the same cardinality.
It was new and surprising information for me that the set of algebraic numbers is countable.
However, thinking about it, it actually makes sense. Each algebraic number can be represented with a finite polynomial. This fact, all by itself, pretty much makes them countable by definition.
You learn new things every day...
