Cardinality of straight-line functions vs curved functions

[Dead_Cat]

I hope the thread title is a reasonable summary but let me start by explaining how I got there before I tell you the simple question, as I may have also made errors along the way. Bear in mind I consider my mathematical knowledge to be better than the vast majority of people, but I did fail maths at college level, so this topic is right on the border of my understanding.

I started by considering the fact that you can bisect any rectangle in an infinite number of ways. In other words, there are an infinite number of straight lines that will divide a given rectangle into two equal halves (this will be achieved by any straight line that passes through the centre of the rectangle).

It then occurred to me you could also divide a rectangle into two equal halves with a single curved line, and clearly there are also an infinite number of ways of doing that. My question is, is this a bigger infinity than the first one?

As far as I can tell from a little light Googling of the topic, the cardinality of the first set is equal to that of the reals (a pretty obvious result, as you can represent it graphically by the equation y = ax, where a is in the set of real numbers). Intuitively (which is often wrong in mathematics, particularly with infinite sets) it feels like the number of curved lines (the second set) should be greater, as there are more degrees of freedom. But this link suggests (if I am right that what we are looking at here is the set of continuous functions) that the cardinality of that set is also equal to the cardinality of the reals. Some of the maths on that page isn’t explained clearly enough to me, the layman, so any help would be appreciated - thanks!

This isn’t homework, just curious musings from an amateur with an interest in mathematics.

[Chronos]

OK, how much background do you have in set theory? In particular, are you familiar with the argument that the set of rational numbers has the same cardinality as the set of integers? That is to say, you can put all of the rational numbers on a list, such that there will be a first element of the list, and a second element, and so on, and all rational numbers will be on the list somewhere.

[Chronos]

Actually, let me just start from the beginning, and you can skip over any parts you already know. First step: Show that we can put the rational numbers in a list. Picture an infinite two-dimensional grid of integers (so for instance, (0,0) is on the grid, as is (4,3) , and (7,2) , and (17263,-49564), and so on). We can put those in a list by spiraling out from the center. So we start with (0,0), and then do (1,0) , (0,1) , (-1,0) , (0,-1) , (2,0) , (1,1) , (0,2) , and so on. And we can turn ordered pairs into fractions, too, and so that will give us rational numbers. If we would put a division by zero on our list, just skip over that one and go to the next ordered pair, and likewise if we would put one on that we already have (like 2/4 and 1/2). So our list of rational numbers looks something like 0, 1, -1, 2, 1/2, -2, -1/2, 3, 1/3, -3, -1/3, 4, 3/2, 2/3, 1/4, …, and every rational number will be somewhere on that list.

[DPRK]

I interpreted the question as, why are there not more continuous real functions on the real numbers than there are real numbers. The answer is that any such function is determined by its values at rational numbers, and the rationals are a countable set, as explained.

[Chronos]

OK, next step: Given any list of real numbers between 0 and 1 (which won’t contain all of them, as proven by Cantor, but we can still have a list of some real numbers), we can condense the whole list down to a single real number that corresponds to the whole list. For a list of a finite number of real numbers, this is easy: If we represent the numbers via their decimal expansion (and yes, there are some subtleties here involving 0.999… = 1, but I’ll gloss over that), then we can just alternate the digits of the numbers. Like, for instance, if our numbers are 1/2, e/10, and pi/10, we write them as 0.50000000… , 0.27182818284590… , and 0.314159265358979… (color-coded for convenience) . Then our new number is 0.523071014… . And given that single number, we could “unzip” it into the three numbers on our list.

Now, we can’t quite do this with an infinite list of real numbers, because we’d never finish getting the first digits of all of them, and so never list any of their second digits at all. But we can fix that, in a very similar way to how we listed all of the rationals, in the previous post: We’ll take the first digit of the first one, and then the first digit of the second one and the second digit of the first one, and then the first digit of the third one, the second digit of the second one, and the third digit of the first one, and so on. So if our list started with 1/2, pi/10, e/10, and sqrt(2)/10, then we’d have
0.50000000…
0.27182818284590…
0.314159265358979…
0.1414213…

And our new number would be 0.5203701110…

And there’s a detail here that I was only looking at real numbers between 0 and 1, but that’s not too big a deal, because we can convert all real numbers to a number in that range using an inverse tangent function or something. So we can also combine a list of full-range real numbers into a single real number.

[Chronos]

Next step: Convert a function whose domain is all rational numbers (but whose range can be real numbers) into a single real number. We’ll start by looking at our list of rationals, and apply our function to it to get a list of reals. So since our list of rationals looks like 0, 1, -1, 2, 1/2, -2, -1/2, 3, 1/3, -3, -1/3, 4, 3/2, 2/3, 1/4, … , our list of reals looks like f(0), f(1), f(-1) f(2), f(1/2), f(-2), f(-1/2), f(3), f(1/3), f(-3), f(-1/3), f(4), f(3/2), f(2/3), f(1/4), … . And we’ve already shown how to condense that down to a single real number.

Final step: A continuous function with a domain of all real numbers. Well, if we know the value of that function on all rational numbers, then we know it everywhere, because the definition of “continuous” is that the limit of the function approaching any point exists, and is equal to the value of the function there. And any real number can be approached as a limit of rational numbers, so once we know the value at all the rational numbers, we must, in order for the function to be continuous, know its value at all real numbers, too. So given any continuous function, we can turn it into a single real number, that contains all the same information.

[Francis_Vaughan]

If you assume the generalised continuum hypothesis GCH it might not be too bad. We need the axiom of choice as well. Neither seem unreasonable IMHO.

CH says the cardinality of the reals is Aleph[sub]1[/sub]. The only question is then going to be, is the number of bisections Aleph[sub]1[/sub] or Aleph[sub]2[/sub] or greater?
GCH says there are no numbers in between Aleph[sub]1[/sub] or Aleph[sub]2[/sub] , and that that Aleph[sub]2[/sub] is the cardinality of the powrerset of a set with cardinality Aleph[sub]1[/sub]. (ie 2[sup]Aleph[sub]1[/sub][/sup])

So, how many curved lines can we create to bisect the rectangle. If we restrict ourselves to true functions I supect we could show that there are still only Aleph 1 such functions. (Handwaving that you could use a Taylor series to define all such possible functions, and these have a countable number of terms, so the number of such functions is Aleph[sub]0[/sub] * Aleph[sub]1[/sub] = Aleph[sub]1[/sub].

But of you allow for arbitrary squiggly lines (that don’t cross themselves) I’m not so sure. If we express this on the complex plan we probably get a subset of complex functions, so I suspect it is still Aleph[sub]1[/sub]. So the answer to the OP is No. It is the same number of possible bisections.

But it is late here in Oz, and it has been a hard week. Maybe a real mathematician can come along soon.

[DPRK]

I see no need to assume any continuum hypothesis or axiom of choice ??

[Francis_Vaughan]

@DPRK

I see no need to assume any continuum hypothesis or axiom of choice ??

You need AC for CH. You need GCH to stop there being numbers between Aleph[sub]1[/sub] and Aleph[sub]2[/sub]. That was all.

Hardly rigorous I’m afraid. Just throwing the thought out there are a quick idea.

ETA, the point was to try and show that the generation of all possible parametrisations of the bisection curves fell short of Aleph[sub]2[/sub]. I’m afraid I simply failed to say that was the point. If it does fall short, it remains Aleph[sub]1[/sub].

I’m too tired to do this properly.

[Chronos]

If you don’t restrict yourself to continuous functions, then it’s easy to show that the number of functions on the reals is greater than the number of reals. Even functions on the reals with a two-element range gets you to the power set of the reals.

If you are staying with continuous curves, though, then arbitrary curves (even self-intersecting or space-filling ones) are no problem. We can express any such curve parametrically, as a pair of true functions.

EDIT: Oh, and I’ve never been able to understand why anyone considers the Axiom of Choice intuitive. To me, it’s not just unintuitive, but counterintuitive.

Mathematician: And now, I pick one member of each of these sets, which I can obviously do.
Me: OK, what’d you pick?
Mathematician: Well, I can’t tell you, but it’s obvious that I can pick them.
Me: If you can’t tell me what you picked, then what does it mean to say that you picked them? It sounds to me like you haven’t picked them yet.
Mathematician: But I could…
Me: OK, then, do it.

And then, of course, you have the fact that it leads to absurdities like Banach-Tarski, which are certainly counterintuitive.

[Dead_Cat]

@Chronos

OK, how much background do you have in set theory? In particular, are you familiar with the argument that the set of rational numbers has the same cardinality as the set of integers? That is to say, you can put all of the rational numbers on a list, such that there will be a first element of the list, and a second element, and so on, and all rational numbers will be on the list somewhere.

A little knowledge. Yes, I am familiar with that result and understand it.

@Chronos

Actually, let me just start from the beginning, and you can skip over any parts you already know. First step: Show that we can put the rational numbers in a list. Picture an infinite two-dimensional grid of integers (so for instance, (0,0) is on the grid, as is (4,3) , and (7,2) , and (17263,-49564), and so on). We can put those in a list by spiraling out from the center. So we start with (0,0), and then do (1,0) , (0,1) , (-1,0) , (0,-1) , (2,0) , (1,1) , (0,2) , and so on. And we can turn ordered pairs into fractions, too, and so that will give us rational numbers. If we would put a division by zero on our list, just skip over that one and go to the next ordered pair, and likewise if we would put one on that we already have (like 2/4 and 1/2). So our list of rational numbers looks something like 0, 1, -1, 2, 1/2, -2, -1/2, 3, 1/3, -3, -1/3, 4, 3/2, 2/3, 1/4, …, and every rational number will be somewhere on that list.

That’s a nice way of illustrating it, hadn’t seen it put that way before - thanks.

@DPRK

I interpreted the question as, why are there not more continuous real functions on the real numbers than there are real numbers. The answer is that any such function is determined by its values at rational numbers, and the rationals are a countable set, as explained.

Yes, that is what my question boils down to (provided it is equivalent to the formulation I started with, i.e. the bit about bisecting rectangles - in fact, it doesn’t have to be a rectangle, any regular polygon will do). I guess it is the second part I was struggling a bit with, I believe the answers in the link I provided expand on this a bit, is it true to say that the reason for this is because of the definition of a continuous function? And if we expand the set to include non-continuous functions, we do indeed get a set of greater cardinality?

@Chronos

OK, next step: Given any list of real numbers between 0 and 1 (which won’t contain all of them, as proven by Cantor, but we can still have a list of some real numbers), we can condense the whole list down to a single real number that corresponds to the whole list. For a list of a finite number of real numbers, this is easy: If we represent the numbers via their decimal expansion (and yes, there are some subtleties here involving 0.999… = 1, but I’ll gloss over that), then we can just alternate the digits of the numbers. Like, for instance, if our numbers are 1/2, e/10, and pi/10, we write them as 0.50000000… , 0.27182818284590… , and 0.314159265358979… (color-coded for convenience) . Then our new number is 0.523071014… . And given that single number, we could “unzip” it into the three numbers on our list.

Now, we can’t quite do this with an infinite list of real numbers, because we’d never finish getting the first digits of all of them, and so never list any of their second digits at all. But we can fix that, in a very similar way to how we listed all of the rationals, in the previous post: We’ll take the first digit of the first one, and then the first digit of the second one and the second digit of the first one, and then the first digit of the third one, the second digit of the second one, and the third digit of the first one, and so on. So if our list started with 1/2, pi/10, e/10, and sqrt(2)/10, then we’d have
0.50000000…
0.27182818284590…
0.314159265358979…
0.1414213…

And our new number would be 0.5203701110…

And there’s a detail here that I was only looking at real numbers between 0 and 1, but that’s not too big a deal, because we can convert all real numbers to a number in that range using an inverse tangent function or something. So we can also combine a list of full-range real numbers into a single real number.

OK.

@Chronos

Next step: Convert a function whose domain is all rational numbers (but whose range can be real numbers) into a single real number. We’ll start by looking at our list of rationals, and apply our function to it to get a list of reals. So since our list of rationals looks like 0, 1, -1, 2, 1/2, -2, -1/2, 3, 1/3, -3, -1/3, 4, 3/2, 2/3, 1/4, … , our list of reals looks like f(0), f(1), f(-1) f(2), f(1/2), f(-2), f(-1/2), f(3), f(1/3), f(-3), f(-1/3), f(4), f(3/2), f(2/3), f(1/4), … . And we’ve already shown how to condense that down to a single real number.

Final step: A continuous function with a domain of all real numbers. Well, if we know the value of that function on all rational numbers, then we know it everywhere, because the definition of “continuous” is that the limit of the function approaching any point exists, and is equal to the value of the function there. And any real number can be approached as a limit of rational numbers, so once we know the value at all the rational numbers, we must, in order for the function to be continuous, know its value at all real numbers, too. So given any continuous function, we can turn it into a single real number, that contains all the same information.

Bolding mine - I think this is the key point, and speaks to my reply above to DPRK’s post - thank you very much for taking the time to explain it all so clearly.

[Thudlow_Boink]

@Dead_Cat

In other words, there are an infinite number of straight lines that will divide a given rectangle into two equal halves (this will be achieved by any straight line that passes through the centre of the rectangle).

It then occurred to me you could also divide a rectangle into two equal halves with a single curved line, and clearly there are also an infinite number of ways of doing that. My question is, is this a bigger infinity than the first one?

As far as I can tell from a little light Googling of the topic, the cardinality of the first set is equal to that of the reals (a pretty obvious result, as you can represent it graphically by the equation y = ax, where a is in the set of real numbers).

The question that arose in my mind when reading this was how to characterize the “single curved lines” that could bisect a rectangle. Would it be necessary and/or sufficient that such a curve be the rotated graph of a continuous odd function, suitably bounded so that it does not leave and then reenter the rectangle?

[Francis_Vaughan]

@Chronos

EDIT: Oh, and I’ve never been able to understand why anyone considers the Axiom of Choice intuitive. To me, it’s not just unintuitive, but counterintuitive.

So is just about all of this.

I always had a problem of AC in that any number you pick defines a finite subset of R - that of all numbers less than the number you pick. But there remain an infinite number of numbers greater. So you can only ever pick a number that is somehow restricted to being essentially zero wrt the magnitude of the numbers you didn’t pick. This always seemed just plain wrong in some mind bending way.

But a counter to the idea of AC not being so sensible is to ask if you can name a member of R that I fundamentally can’t pick. You can’t do so.

None of this is in the slightest bit rigorous. Better for a quiet evening over a few beers.

[DPRK]

[QUOTE=Francis Vaughan]

You need AC for CH. You need GCH to stop there being numbers between Aleph1 and Aleph2. That was all.

[/QUOTE]

The CH states 2[sup]ℵ₀[/sup] = ℵ₁ , but there is no reason to work with ℵ₁ or ℵ₂ in this problem so (G)CH is not relevant.

@Dead_Cat

Yes, that is what my question boils down to (provided it is equivalent to the formulation I started with, i.e. the bit about bisecting rectangles - in fact, it doesn’t have to be a rectangle, any regular polygon will do). I guess it is the second part I was struggling a bit with, I believe the answers in the link I provided expand on this a bit, is it true to say that the reason for this is because of the definition of a continuous function? And if we expand the set to include non-continuous functions, we do indeed get a set of greater cardinality?

We did not have to investigate the bisection problem geometrically since it is straightforward (by continuity) to bisect any area using a straight line at any chosen angle, so the cardinality is at least the continuum, and by counting all continuous curves we saw that the cardinality is at most the continuum.

There are more arbitrary functions than there are continuous functions, but you want the plane curves used for bisection to be continuous, no? How would you even define bisection if you do not separate your region into two pieces?

[DPRK]

@Thudlow_Boink

The question that arose in my mind when reading this was how to characterize the “single curved lines” that could bisect a rectangle. Would it be necessary and/or sufficient that such a curve be the rotated graph of a continuous odd function, suitably bounded so that it does not leave and then reenter the rectangle?

I don’t think there is any symmetry condition. For instance, you could bisect the rectangle with an L-shaped curve, or a
Brownian bridge, or many other funny shapes.

[Chronos]

You could bisect a plane region using non-continuous functions. A graph of any true function still divides the plane into a region above it and a region below it, and it’s not too difficult, given any function, to odd-ify it so that the regions above and below are congruent.

[DPRK]

This is by no means authoritative, but in my mind a curve will be defined by the image of an injective continuous function R → R[sup]2[/sup]. If it were not continuous, you could have a gap. Come to think of it, even this condition by no means guarantees the rectangle is split in two. Better to make it a Jordan arc with both endpoints on the perimeter of the rectangle; something like that should do it.

You appear to be thinking of graphs of functions R → R, but there is no reason to restrict to that class (unless I misunderstood the problem).

[Chopsticks]

@DPRK

This is by no means authoritative, but in my mind a curve will be defined by the image of an injective continuous function R → R[sup]2[/sup]. If it were not continuous, you could have a gap. Come to think of it, even this condition by no means guarantees the rectangle is split in two. Better to make it a Jordan arc with both endpoints on the perimeter of the rectangle; something like that should do it.

You appear to be thinking of graphs of functions R → R, but there is no reason to restrict to that class (unless I misunderstood the problem).

Now you’re going past my level of understanding (who is Jordan?), but what about

For the rectangle, make it square from (0,0) to (1,1)
draw a line from (0,1/4) to (0,3/4), to (1,3/4) to (1,1/4)
The inside of this line is a rectangle of area 1/2, and the outside is two nonconnected pieces with total area 1/2.

Would that be a valid solution? Or, a circle of area 1/2 inside the square?

[OldGuy]

@DPRK

I interpreted the question as, why are there not more continuous real functions on the real numbers than there are real numbers. The answer is that any such function is determined by its values at rational numbers, and the rationals are a countable set, as explained.

A question.

Is this actually true of all continuous functions or do they have to be sufficiently smooth. In particular, the path of a Brownian motion is continuous with probability 1. Is the cardinality of the number of Brownian paths on say (0,1) only the cardinality of the reals? The Mandelbrot set is connected so its outline should be a a continuous curve. Is the cardinality of Mandelbrotian-type curves (if that means anything) only the cardinality of the reals?

[DPRK]

@Chopsticks

Now you’re going past my level of understanding (who is Jordan?),

Camille Jordan.

but what about

For the rectangle, make it square from (0,0) to (1,1)
draw a line from (0,1/4) to (0,3/4), to (1,3/4) to (1,1/4)
The inside of this line is a rectangle of area 1/2, and the outside is two nonconnected pieces with total area 1/2.

Would that be a valid solution? Or, a circle of area 1/2 inside the square?

I am not the OP who proposed the problem, and cannot say what he or she originally had in mind. Let’s think, though: if we restrict to considering (Jordan) paths that start at some point on the perimeter, go wherever they want inside the rectangle but without touching the boundary, and finally end up again on the perimeter, then from the Jordan curve theorem it will follow that such curves split the rectangle into exactly two connected pieces. Your first example would not work in this case, but a circle that fits inside the rectangle and touches it at a single point would. If you relax the conditions further so that the bisecting curve can touch the perimeter, maybe wander outside, or maybe even consider Jordan curves that do not even intersect the rectangle, then you have still chopped the rectangle into two “pieces”, except the pieces may no longer be connected (or even have a finite number of connected components), and may even be empty. Not sure if the OP had that in mind, but none of those nuances make any difference to the count of possible paths (all classes have the cardinality of the continuum).