What is the cardinality of the set of all simple, closed curves in two dimensions, excluding all rotations and reflections?
Since a curve is a continuous map, then the cardinality is essentially the same as that of the set of all real continuous functions, which is 2^aleph-0, the same cardinality of the reals.
To prove this, I won't construct an explicit bijection, because this gets messy pretty quickly. It's sufficient to show that you can construct an injection from A to B and an injection from B to A. The Schroeder-Bernstein theorem guarantees that a bijection exists given these conditions.
It's instructive to recall the proof that the set of continuous functions C has the same cardinality of R. For the injection from R to C, it's clear that for every real number a, there's the constant function f(x)=a, which is continuous. For the injection from C to R, we notice that we can sample any continuous function f(x) at rational values of x, and the values of f at rational numbers completely define the function at the real line (if ou have trouble understanding that, just notice that for every irrational number, you can find a sequence of rationals (xn) that converges to it, and the continuity condition will guarantee that all f(xn) sequences will converge to a value, which should be f evaluated at the irrational point). That gives us an injection between C and sequences of reals, which are in bijection with the set of reals, that finishes the proof.
The case is analogous to closed curves. A curve is just the image of a continuous function. The extra condition that it must be simple and closed only implies that the cardinality is at most 2^aleph-0. However, we see that for every real number a, there's a circumference with radius a, so the cardinality is at least 2^aleph-0. So, again, the set of all closed curves has the same cardinality of R.
Bobo the king wrote:
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?
The answer is in the article you linked to. If you solve Dirichlet's problem with the closed curve as boundary, you get a sequence of real eigenvalues. So, if the set of boundaries is larger than the set of sequences of reals, two boundaries will necessarily correspond to the same sequence of eigenvalues, giving a negative answer to the drum problem.
However, it's not that simple. As I proved before, the two sets have the same cardinality.
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.
Yeah, I realized as I was typing it that you probably knew a good deal of that already. Even so, I thought it might be nice to make sure anyone could understand it.
Scepheo wrote:
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.
You're right. It was fallacious of me.
Tub wrote:
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 ;)
Oops. You caught me. I am a little careless with my math sometimes, especially analysis, which I rarely use...
p4wn3r wrote:
Bobo the king wrote:
What is the cardinality of the set of all simple, closed curves in two dimensions, excluding all rotations and reflections?
Since a curve is a continuous map, then the cardinality is essentially the same as that of the set of all real continuous functions, which is 2^aleph-0, the same cardinality of the reals.
To prove this, I won't construct an explicit bijection, because this gets messy pretty quickly. It's sufficient to show that you can construct an injection from A to B and an injection from B to A. The Schroeder-Bernstein theorem guarantees that a bijection exists given these conditions.
It's instructive to recall the proof that the set of continuous functions C has the same cardinality of R. For the injection from R to C, it's clear that for every real number a, there's the constant function f(x)=a, which is continuous. For the injection from C to R, we notice that we can sample any continuous function f(x) at rational values of x, and the values of f at rational numbers completely define the function at the real line (if ou have trouble understanding that, just notice that for every irrational number, you can find a sequence of rationals (xn) that converges to it, and the continuity condition will guarantee that all f(xn) sequences will converge to a value, which should be f evaluated at the irrational point). That gives us an injection between C and sequences of reals, which are in bijection with the set of reals, that finishes the proof.
The case is analogous to closed curves. A curve is just the image of a continuous function. The extra condition that it must be simple and closed only implies that the cardinality is at most 2^aleph-0. However, we see that for every real number a, there's a circumference with radius a, so the cardinality is at least 2^aleph-0. So, again, the set of all closed curves has the same cardinality of R.
Bobo the king wrote:
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?
The answer is in the article you linked to. If you solve Dirichlet's problem with the closed curve as boundary, you get a sequence of real eigenvalues. So, if the set of boundaries is larger than the set of sequences of reals, two boundaries will necessarily correspond to the same sequence of eigenvalues, giving a negative answer to the drum problem.
However, it's not that simple. As I proved before, the two sets have the same cardinality.
Good answer! Of course I'd hoped for a straightforward proof based on cardinality, but that's a pretty simple solution to the problem. I suppose that one cannot hear the shape of a drum only "coincidentally".
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...
This, incidentally, is a neat way of proving that transcendental numbers exist. (In fact it goes one stage further and shows that not only do they exist, they are actually in the majority.) Although it wasn't the first proof, it's certainly the easiest. To prove the transcendence of any individual number is really quite hard.
So, again, the set of all closed curves has the same cardinality of R.
Hmm.. can you please look over my attempted proof 8 posts above this and tell me where I went wrong? I suspect that my fuzzy block isn't "continuous", but I lack the proper definitions for "continuous" that I'd need to satisfy.
thatguy wrote:
Maybe we should have a separate thread for maths PhD students and postdocs... this is going over my head a bit.
I'm just a computer science student with a bachelor (soon master), neither math nor PhD. While some basic math education beyond high school is certainly required for some topics, it's often enough to spend an hour on wikipedia and google. Can you guess that I never worked with curves before Bobo posted his challenge?
A bit of time may be required, but after all, the thread title is math *challenges*, not math trivialities.
Warp wrote:
Tub wrote:
|2^R| = aleph-2.
Doesn't that assume the generalized continuum hypothesis? (Or am I misunderstanding something about it?)
No, the definition of aleph-numbers is
aleph-(n+1) = 2^aleph-n
The GCH only states that there's no additional cardinality between aleph-n and aleph-(n+1), but that's neither relevant for my statement you quoted, nor for the proof p4wn3r posted.
Hmm.. can you please look over my attempted proof 8 posts above this and tell me where I went wrong? I suspect that my fuzzy block isn't "continuous", but I lack the proper definitions for "continuous" that I'd need to satisfy..
Sure. The reason that it doesn't work is entirely formal, so excuse any excessive formalism below.
Tub wrote:
At this point I'm not sure about the exact definition of a simple, closed curve.
A curve is any continuous function f from an interval of real numbers (open or closed) into a space with a defined topology (in this case R^2 with the euclidean metric).
A simple curve is a curve that doesn't intersect itself, so we require the function f to be injective.
For a closed curve, we require the domain to be a closed interval [a,b] and that f(a)=f(b). And for simple closed closed curves we also require f to be injective in the open interval (a,b).
Tub wrote:
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] }
The result that a simple closed curve defines an interior area in the plane is very difficult to prove, it's known as Jordan's theorem.
But we don't need to dive into the details of the proof. We can look at the statement in the article above:
Let C be a Jordan curve in the plane R2. Then its complement, R2 \ C, consists of exactly two connected components. One of these components is bounded (the interior) and the other is unbounded (the exterior), and the curve C is the boundary of each component.
And what's a boundary? It's easier to understand with an example. 0 is a boundary point of (0,infty), because of two things:
1) you can get infinitesimally close to 0 using only points of (0,infty)
2) you cannot create an interval (0-eps,0+eps) which is completely inside (0,infty)
Analogously, 0 is also a boundary point of the closed interval [0,infty] (BBcode is messing up when I put a parenthesis after infty...), you can check the two conditions above for that set and that the definition of a boundary doesn't depend if the point is inside or outside the set.
Now we can go back to your set I. No matter which subset of (x,0) you remove, the boundary is always the contour of the unit square. So, if you assume that I is a connected component generated by a simple closed curve, you are forced by Jordan's theorem to agree that the curve is the boundary of your set. So, you'd reach the conclusion that all your sets I correspond to the same curve, which is absurd if you also assume that a point can be either in I, in the curve C, or in R2 - I - C. The only way out of this inconsistency is to assume that some sets I cannot be separated from the rest of the plane by a Jordan curve, which invalidates the bijection.
Tub wrote:
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?
Your set is connected, but the condition that for any point there's another arbitrarily close to it is too weak. Take a set which is made of two separate squares. For every point, there's another one infinitesimally close, but there's no path between two points in separate squares, so it's not connected.
And, as shown before, just because a set I is connected, it doesn't mean that it can arise from the partition of a plane by a simple closed curve.
hmm, wikipedia may be on your side there. I was going by the definition Bobo gave in his post
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.
That definition seems more convenient if one didn't assume GCH, since all aleph-numbers remain well-defined and workable without - none of the things we talked about actually require the GCH. It just isn't the "official" definition and we should have talked about |N|, |2^N|, |2^2^N|, ... instead of aleph-numbers.
Now for an unexpected application of topology. In order to define a topology we only need a set S, postulate which subsets of S are open and satisfy the following axioms:
(1) The empty set and S are open.
(2) Any union of open sets is open.
(3) Any finite intersection of open sets is open.
A set is called closed if its complement is open.
Let's use the set of integers Z and say that a set is open if it's the empty set or the union of sets of the form S(a,b) = {an+b | n in Z} with a != 0 (an arithmetic sequence).
An example of an open set would be {..., -5, -4, -2, -1, 1, 2, 4, 5, ...} because it's the union of S(3,1) and S(3,2).
(a) Prove that the topology is well defined. In other words, prove that it satisfies axioms (1)-(3)
(b) Can a finite non-empty set be open?
(c) Are the sets S(a,b) also closed?
(d) Write the union of all S(p,0), with p prime, in a more explicit form. Try to reason whether the resulting set is open or closed. What does that say about the number of primes?
It was new and surprising information for me that the set of algebraic numbers is countable.
In fact, I think this could be extended further.
I don't know if there exists a name for the set of numbers expressible using analytical expressions, so I'll call them "analytical numbers" (in the same vein as "algebraic number" means a number that can be expressed with an algebraic expression.)
Analytical expressions not only include algebraic expressions, but also closed-form expressions as well as infinite series and continued fractions.
"But wait a minute", you would object, "for them to be countable, they would have to consist only of finite expressions; if we allow infinite expressions, they become uncountable."
That's true, except that all those infinite series and continued fractions need to be expressible with a finite notation, or else you could not define them. Thus, although the series may be infinite, it can be expressed with a finite expression (in the same way as eg. the decimal expansion of 1/3 is infinite, yet you can express it with a finite expression.)
So I postulate that the set of analytical numbers is countable.
This set contains many irrational and transcendental numbers (eg. pi = 4*atan(1)).
This got me thinking that this whole idea implies that there are real numbers that cannot be expressed with any kind of finite expression (because if all real numbers were expressible with finite expressions, they would be countable, which we know is not the case.)
So does that mean that the following is impossible to answer? "Give me an example of a real number that's not expressible with a finite expression."
(a) Prove that the topology is well defined. In other words, prove that it satisfies axioms (1)-(3)
For (1), already defined φ and S=S(1,0) are open. For (2), already defined opens sets if they're unions of the form S(a,b). For (3), we want to prove that the intersection of two sets S(a,b) and S(c,d) is still another set, and thus by induction any finite intersection is. To do that, consider these sequences as congruences modulo a or c respectively. We have each element of the set of the form Si=b mod a, Sj=d mod c. We want to know about their intersection, IE when they satisfy both, and thus by the Chinese remainder theorem there exists a unique e<ac such that e mod ac satisfies both; with e= b mod a = d mod c . This describes S(ac, e), and thus is a still a linear progression, IE member of our set; thus any finite intersection is. In the event no intersection exists, then we have the intersection as φ, which was still defined to be open.
p4wn3r wrote:
(b) Can a finite non-empty set be open?
Given how each set s is infinite, their unions are infinite, as are their (non empty) intersections, so no.
p4wn3r wrote:
(c) Are the sets S(a,b) also closed?
They're closed if their compliment S' is open. S'(a,b)=S(a,1) U S(a,2) U ... U S(a,b-1) U S(a,b+1) ... U S(a,(a-1). This is the finite union of all other values of 'b', and thus by axiom (2) this is open; thus the initial sets S are both closed and open. Thus since S is open, we have S' closed, so both S and S' are clopen sets.
p4wn3r wrote:
(d) Write the union of all S(p,0), with p prime, in a more explicit form. Try to reason whether the resulting set is open or closed. What does that say about the number of primes?
This set X=U S(p,0)=Z - {-1, 1} . This set would be all integers expressible in the form nP for some integer n, prime p. This would generate all numbers apart from +-1, as they have no prime factors and thus cannot be expressed in the form nP. The compliment X'={-1,1} is a finite set, thus closed by question (b). This means our set X is open.
By (2) we know that the union of open sets S(a,b) and S(c,d) will be open, and similar to (3) can be shown to generate a cyclic pattern modulo (ac). This means their compliment is also a cyclic pattern modulo (ac), and thus can be written as a union of S(ac, k) for each occurring element k in this pattern. Thus since we have another finite union of sets S, by (2) this is still open. So if this compliment set is open, our initial set S, the union of finite open sets, must be closed. But since by (C) these open sets are also closed, that proves that these finite intersections of closed sets are still closed.
But if X was a finite union of S(p,0)s, it would still be closed, implying X' open, which cannot be true if X' finite. This reaches a contradiction, which can only occur due to applying the axiom with FINITE unions, and thus X must be an infinite union, IE infinite primes exist.
You're very close, yet so far away :)
X' is a finite set, so by (b) it can't be open. Because of this, X can't be closed. But by (c), all S(p,0)'s are closed. So we have a union of closed sets resulting in a set that's not closed. How is this possible?
EDIT: Flip edited his post and finished (d), this post is outdated.
EDIT 2: There's a more straight-forward way to prove that finite unions of closed sets are closed. Just use De Morgan. A union B = (A' inter B')'
So if A and B are closed, their complements are open, and so is their intersection. Then, the complement of A' inter B' should be closed.
So, did you like the topological proof of the infinitude of primes? :)
The compliment X'={-1,1} is a finite set, thus closed by question (b). This means our set X is open.
Careful. The definition allows for a set to be open, closed, both or neither.
By question b, we know that {-1,1} is not open, but we cannot assume it to be closed unless we first prove that the complement is open.
p4wn3r wrote:
So, did you like the topological proof of the infinitude of primes? :)
So does that mean that the following is impossible to answer? "Give me an example of a real number that's not expressible with a finite expression."
Huh, yes, but is it that surprising?
Giving you an example would mean representing the number in a finite way, so it's logically inconsistent to ask someone to represent a number that can't be represented.
Tub wrote:
So does that mean that the following is impossible to answer? "Give me an example of a real number that's not expressible with a finite expression."
That depends on what "give me an example of" and "expressible with a finite expression" mean.
I suppose "give me an example of" means "define", but "expressible with a finite expression"? Does that merely mean computable numbers or possibly a subset of the computable numbers? There are numbers that are not computable and can be defined (as stated on the Wikipedia page).
I just find it fascinating that there exist real numbers that cannot be expressed in any way.
The set of all real numbers that can be expressed with a finite definition is countable (pretty much by definition). Since this doesn't cover all real numbers (because they are uncountable), this means that there are real numbers that cannot be expressed in any way (because you can't literally write an infinite expression to define it).
In fact, the set of real numbers that cannot be expressed in any way is larger than the set of numbers that can.
I think that's fascinating.
I just find it fascinating that there exist real numbers that cannot be expressed in any way.
The set of all real numbers that can be expressed with a finite definition is countable (pretty much by definition). Since this doesn't cover all real numbers (because they are uncountable), this means that there are real numbers that cannot be expressed in any way (because you can't literally write an infinite expression to define it).
In fact, the set of real numbers that cannot be expressed in any way is larger than the set of numbers that can.
I think that's fascinating.
This reasoning is pretty good, but to make it work you have to firm up what you mean by "definition", which will normally require you to define some sort of formal system for defining things; polynomials are an example of such a system, which defines algebraic numbers. Without a formal system like this, you can end up with paradoxes by defining numbers like "the smallest positive real number without a definition".
What you end up with is a statement closer to "In any formal system for creating finite definitions of real numbers, almost all real numbers are undefinable." Which is still fascinating, but leaves open the possibility that any particular real number undefiniable in a particular formal system might have a definition within another formal system.
This is all very closely related to Gödel's incompleteness theorem and Russell's paradox.
Without a formal system like this, you can end up with paradoxes by defining numbers like "the smallest positive real number without a definition".
The example is a bit unfortunate. Unlike the integer case, the subset of positive undefined reals doesn't need to have a minimum. It does have an infimum, but the infimum doesn't need to be a member of the set, and could be a defined number.
It's interesting that we can define a set of numbers which contains elements that cannot be expressed.
I suppose this is starting to delve into the question of how the set real numbers is defined, which apparently isn't actually something that's as trivial or easy to define as one would hastily think.
The definition of the real numbers is not hard at all. There are many equivalent definitions, but the one I like most defines the set of reals as the set where addition, multiplication, and ordering are defined in the usual manner and has the following important property:
Every non-empty set of positive real numbers has an infimum.
This is the continuum analogue of the well-ordering principle. And just like inductive proofs in the integers follow from the well-ordering principle, the notion of limits, convergence, etc. follow from that property of the reals.
We still haven't proved that a set satisfying that property exists, to do so we need constructions, and there are lots of them.
If the issue is just about uncountable sets, the simplest one is the set of subsets of natural numbers. It's still possible to be pedantic and ask how we know that the set of subsets of naturals exists, and the answer is fast. It's an axiom, we simply assume it to be true: https://en.wikipedia.org/wiki/Axiom_of_power_set
Any definition or construction of the reals or any uncountable set must ultimately rely on an axiom that postulates the existence of power sets of infinity or an equivalent formalism, without it the formal system isn't powerful enough to do that.
From here, it largely depends on what you think mathematics should be. If you're a formalist, like most mathematicians are, when someone asks you why do we have real numbers, you'd say "well, math is still consistent if we assume their existence, and we can prove many useful theorems, so why shouldn't we have them?". If you're a constructivist/finitist/intuitionist/whatever (and there are many examples of excellent mathematicians who subscribe to these views), you'd simply think that uncountable sets are bullshit and people should try to redefine analysis in a way that doesn't create a jungle of undefinable entities.
Thanks for the explanation.
I was thinking earlier today the following, and it's probably constructivist thinking:
Let's define a subset of the real numbers which consists of all numbers that are expressible with a finite definition. I understand that this is (most probably) an ill-defined set, but let's just assume that it can be well-defined, just for the sake of argument.
That set is countable (basically by definition).
The rest of the real numbers, thus, cannot be expressed with any finite expression whatsoever. Are these numbers useful in any way, shape or form?
Those numbers cannot be the answer to any problem (because, by definition, any number that's the answer to a problem is defined by a finite statement, ie. the problem itself, and thus belongs to the countable set defined above.) If those numbers cannot be the answer to any problem, and they cannot be expressed in any way, what's their use? Do they even "exist" (by some definition of "exist")?
I suppose this is more a question of philosophy than math...
If you're a constructivist/finitist/intuitionist/whatever (and there are many examples of excellent mathematicians who subscribe to these views), you'd simply think that uncountable sets are bullshit and people should try to redefine analysis in a way that doesn't create a jungle of undefinable entities.
Makes me wonder.. did anyone even come close to that goal? To avoid undefinable entities, one would not only need to restrict analysis to contain only a countable number of numbers, one would also need to restrict analysis to allow only a countable number of statements. That seems.. very limited; possibly useless.
Language theory, for example, works on strictly countable objects: sets of words over a finite alphabet. Still, most properties of languages are undefinable and/or undecidable simply because the amount of properties of languages is larger than the (countable) amount of automatons we can construct to decide them. I cannot imagine a theory of analysis that doesn't inevitably run into the same problem.
Warp wrote:
Let's define a subset of the real numbers which consists of all numbers that are expressible with a finite definition. I understand that this is (most probably) an ill-defined set, but let's just assume that it can be well-defined, just for the sake of argument.
Read rhebus's post again. It's well-defined only for a given "language" or "formal system" that gives meaning to the definition. That's not just an addendum for formal correctness; it's a very important point.
Warp wrote:
The rest of the real numbers, thus, cannot be expressed with any finite expression whatsoever.
Read rhebus's post again. They cannot be expressed with any finite expression in the previously specified formal system. Depending on what you allow as a "formal system", there's always one where the number is definable.
Warp wrote:
Those numbers cannot be the answer to any problem (because, by definition, any number that's the answer to a problem is defined by a finite statement, ie. the problem itself, and thus belongs to the countable set defined above.) If those numbers cannot be the answer to any problem, and they cannot be expressed in any way, what's their use?
No single number in this set can be the answer to a problem formulated in the formal system used. You might find problems where the answer is a subset of these numbers, or the whole set. You might find statements in a different formal system that apply, like "any number with property X (as defined by formal system A) is undefinable in formal system B". I'm sure you've seen proofs that the set of decimal representations of prime numbers cannot be decided by a regular language, and you know why these proofs are useful.
Warp wrote:
Do they even "exist" (by some definition of "exist")?
While we cannot define each of these numbers individually, we can define sets of these numbers. p4wn3r has just defined the set of all reals in a simple, finite way. If you tie "existence" to definability, they still exist.
Depending on what you allow as a "formal system", there's always one where the number is definable.
Well, the formal system itself must be definable with a finite amount of information (or else it's not definable in practice; we cannot read an infinite definition in order to know all of its axioms. A formal system with an infinite definition would not be very useful.)
So if we agree that every formal system definition must be finite, that means that the amount of possible formal systems is countable.
Thus couldn't we define our set as "all the real numbers definable by a finite statement in any possible (finite) formal system"?
In other words: If you can define the number using a finite amount of information, it belongs to our set.
Not all real numbers can be defined like this (because else it would mean that the set of real numbers is countable.) There have to be some numbers that are impossible to define using a finite amount of information.
So the (mostly philosophical) question is: What purpose do these numbers serve, other than being a curiosity? We can define them to conceptually exist, but they will never be the answer to any problem or formulation.
(Some interesting properties can be defined for them, though. For example multiplying two such numbers together may result in a number that's in our countable set. The other way around obviously can't happen.)
