Talk:Cantor-Dedekind Hypothesis

Umm...this is a little silly, but is there any axiom that implies that every line is nonempty? Also, is the axiom of choice required? If all lines contain at least two points, then it is not required to choose two points on the line. Also, the statement "The existence of the choice function allows that this process can be done for any point on L" should be a little more formal - I don't know what this function is, or how we're manipulating the choice function to create this mapping. Andrew Salmon 03:02, 2 March 2012 (EST)

I'm kind of skeptical of this because the constructible numbers (and even algebraic numbers) are countable. Do you know a book or anything that mentions the statement here as a theorem (or says euclidean lines have to be uncountable)? I don't know nearly enough (even elementary) geometry, and I could easily be misunderstanding something, but at the moment I don't see why euclidean geometry guarantees enough points are on a line to get such a bijection. -- Qedetc 01:25, 10 June 2011 (CDT)

We have that $\pi$ is a transcendental real number and so an element of an uncountable set. $\pi$ is on the real number line, although admittedly Euclid did not prove that $\pi$ was transcendental. I don't know the details of how the proof of this works (I've seen it but haven't analysed it properly) but "surely" it's a truism that the points on a line are uncountable. Besides, who says that the points on an infinite straight line have to be constructible? There is nothing in Euclid's Elements that says every point on a line has to be "constructible", all you need to do is be able to draw the straight line and it is at that level "assumed" that the points on it "exist". But only certain points on it are proved to be identified by a specific "location" on that line. That's my understanding of this and how I reach a philosophical acceptance of its truth. --prime mover 01:54, 10 June 2011 (CDT)

Sorry in advance for the huge wall of text below:

Even if we need countably many transcendentals, that isn't necessarily enough to force an uncountable amount of elements. For example, if you adjoin $\pi^{1/n}$ for every $n\in\mathbb N$ to the field of algebraic numbers, you still get a countable field.

We don't, we need uncountably many transcendentals, and it can be proved that there's an uncountable number. --prime mover 13:01, 10 June 2011 (CDT)

What do you mean by "need" here? I feel like you're mixing up the real line with the lines in euclidean geometry in advance. We know $\mathbb{R}$ is uncountable and has uncountably many transcendentals over $\mathbb{Q}$. The relevance that has is that this page is claiming that there is a bijection between $\mathbb{R}$ as defined in some analysis or algebra text, and the lines that appear in euclidean geometry. But, the lines in euclidean geometry are primitives; they have no definition. Their properties are only known through the axioms which mention them. So if there's going to be a proof that the collection of points on a line in euclidean geometry are in bijection with the elements of $\mathbb{R}$, there's got to to be something in the euclidean axioms that's going guarantee you can get at that many points. -- Qedetc 14:33, 10 June 2011 (CDT)

I'd have to suspect that uncountably many elements are forced to exist by euclidean geometry to clear this up for me. The problem for me is that I don't see why something would be forced to exist if it wasn't constructible. I'm not sure it's obvious that any notion of line has to have uncountably many points. The set of points $\{(0,0) + t(1,1): t\in\mathbb{Q}\}$ in $\mathbb{Q}^2 \subseteq \mathbb{R}^2$ certainly looks like kind of line-ish if you try to graph it. Intuition on this matter isn't really relevant though. The theorem here is purporting to establish that it is in fact uncountable.

By insisting on any mathematical result to be "constructible", I see you're allied with the "intuitionist" school (Kronecker, Brouwer etc.) which philosophical position I personally find pusillanimous and untenable. --prime mover 13:01, 10 June 2011 (CDT)

No. I'm using "constructible" here variously to mean the set of constructible numbers and the points in euclidean geometry which can be shown to exist with a straight edge and compass. I'm not suggesting that they are or should be the only points that exist, and I've already mentioned that we know in the usual model of euclidean geometry there are lots non-constructible things. I am not insisting that things be constructible, and I'm not espousing intuitionism or constructivism. I am expressing skepticism and confusion at the idea of finding a bijection between some sets which I don't know to be the cardinality of the reals with sets which I do know to be the cardinality of the reals.

For more clarification and to take this from the opposite direct to help convince you I'm not trying to assert that only constructible things exist: I'm also not totally sure why we couldn't take some weird nonstandard model with "too many" points on the lines to get this bijection either. Hilbert's axioms mention the archimedean property which seems like it might prevent this, but I don't know if Euclid made implicitly use of this or whether it's included as a "usual axiom" in geometry. Again, my point isn't really specifically whether this particular thing is "the model of euclidean geometry", but rather I'm asking if the axioms of euclidean geometry prevent this from being a model (among the other models including the usual $\mathbb{R}^n$). -- Qedetc 14:33, 10 June 2011 (CDT)

To help clarify my thoughts here, I'm not suggesting that the points on lines in euclidean geometry have to be constructible or algebraic. We know that $\mathbb{R}^n$ is a model of euclidean geometry, and it definitely has nonconstructible points on its lines. What I'm wondering is whether the axioms of euclidean geometry force there to be anything more than the points you can construct. Do we know somehow that the axioms guarantee that if you have a line AB of length 4 at point A that there actually is a point on the line distance $\pi$ toward $B$? We know there's infinitely many points between $A$ and $B$, but that's not enough. This might involve knowing something about the line being a continuum rather than just dense. It wasn't clear to me from the axioms I had seen from The Elements that this was necessary.

No, the Euclidean axioms say no such thing, because the whole concept of countability / uncountability has no place in Euclid. But yes, I believe that the axioms do guarantee that "if you have a line AB of length 4 at point A that there actually is a point on the line distance $\pi$ toward $B$" because otherwise there would be a gap there, and by the very notion of what a straight line is, the notion is untenable - although admittedly at a "naive" level. Succinctly: the question is irrelevant in this context.

It has to (indirectly) assert something about the cardinality of the collection of points which belong to lines if this theorem is true (unless I'm misunderstanding the statement of the theorem). If lines must have their points in bijection with the reals, then something in the axioms must be forcing this to be the case. It doesn't matter if Euclid doesn't know anything about cardinality.

What do you mean by 'notion of a straight line'? I feel like you're going off your intuition on what it means to be a straight line, but our intuition is usually clouded by having used continuous straight $\mathbb{R}$-like lines our whole lives. I guess my point is, $\mathbb{R}^n$ with its interpretations of points, lines, planes, betweenness, etc. being a model for X (euclidean geometry) does not immediately imply that X (euclidean geometry) is the theory of $\mathbb{R}^n$ with those things. -- Qedetc 14:33, 10 June 2011 (CDT)

I just went and looked at some wikipedia pages and noticed Hilbert used an axiom ( http://en.wikipedia.org/wiki/Hilbert%27s_axioms#V._Continuity ) which seems like it might prevent countable models (or at least the ones I was thinking of, since they could be extended to the $\mathbb{R}$ based models). I don't know if Hilbert added this because it was an implicit assumption in The Elements or just because he felt like it (nothing like this seems mentioned in the axioms from The Elements, as far as I can tell, but Euclid might have used it somewhere).

Birkhoff ( http://en.wikipedia.org/wiki/Birkhoff%27s_axioms ) apparently took this bijection as an axiom.

Since Hilbert and Birkhoff, Cohen proved that the continuum hypothesis can be take n either way depending on whether you want it to be true or not.

Why are you mentioning this :/ -- Qedetc 14:33, 10 June 2011 (CDT)

Tarski ( http://en.wikipedia.org/wiki/Tarski%27s_axioms#Betweenness_axioms ) apparently has a weaker first-order version of euclidean geometry and includes an axiom that adds a sort of completeness property (but only for first-order definable subsets of lines, of which there are only countably many). I think we can prove there's a countable model for these axioms. This probably isn't what people think of when they think of euclidean geometry though.

I guess I'm asking whether (constructible numbers)$^n$ is ever considered a model of usual euclidean geometry. I don't think this is ridiculous, since, if you imagine taking the real plane and throwing out all the non-algebraic points, it still "looks like" a big dense plane. It's not clear to me that this isn't "enough". There might be some argument in The Elements which prevents it, but it looks like Tarski's weaker geometry doesn't forbid it (as far as I can tell), and Hilbert and Birkhoff kind of threw in axioms for it for reasons I'm not sure of.

The reason this is at all relevant is that if the axioms don't force uncountable models, then I don't see how anyone is going to define this bijection, since the axioms won't guarantee the points exist. If you've seen this proof somewhere, then I guess they've got something that does it. I'm expressing interest in seeing it (or knowing where you saw it :D ) and trying to fill in some gaps in my very incomplete knowledge. Again, I don't really know much about euclidean geometry or how its normally formally handled.

Qedetc 04:05, 10 June 2011 (CDT)

Not sure but I think it's covered somewhere in proving that $\R$ is a complete metric space, and also might use the concept of Dedekind cuts. I'm sorry but I was fairly sure this was an established (maybe even "taken for granted") result - if it wasn't, then I can't see why it wouldn't be as important as any other of the millennium problems: "Oh and by the way I suppose we ought to make sure that geometry provides an adequate model for the real world ..." (without going into the muddy waters of non-euclidean stuff).

If as you suggest there's a gaping hole and there is *not* a one-to-one correspondence between points on the real number line and points on an idealized straight line in space, then I'm afraid I'm going to have to curl up in a corner and suck my thumb until the whimpering stops. --prime mover 13:01, 10 June 2011 (CDT)

I'm willing to take $\mathbb{R}$ as complete and uncountable as an axiom for this discussion. The issue is whether we can go prove in euclidean geometry something like that a line is a complete and uncountable. Like, watch how I justify steps if I want to go naively start trying to define an order-preserving bijection between a euclidean geometry line and the rationals:

Base) Use a euclidean axiom saying any line contains at least two points $p_0, p_1$. Send them to $0, 1$ respectively.

Inductive step a) if $q$ is a rational and we want it in the range of the function, look at how $q$ relates in the ordering to the other rationals we've hit already. If $q_L < q < q_R$ where $q_L$ and $q_R$ are rationals we hit already and nothing else between them was yet handled, then use a euclidean axiom to pick a point between the preimages of $q_L$ and $q_R$ on the line. Extend the map by sending that point to $q$.

Inductive step b) If $p$ is a point on the line, look at its between-ness relations to other points on the line. If $p_L < p < p_R$ with $p_L, p_R$ points we mapped already with no other points between them yet handled, then use the denseness of the rationals to pick a point between the images of $p_L$ and $p_R$ and send $p$ to that rational.

This almost looks like it defines an order-preserving bijection between euclidean lines and the ordered rationals, except I don't know that the euclidean line is countable, so I might not have included all of its points in the domain of my function. I did manage to define an order-preserving bijection between some subset of the points on a line and the ordered rationals though.

I'm not just throwing this proof-thing in here for my own gratification. Note that when I wanted a point on the line I used an axiom from geometry to find it. When I wanted a rational, I used an axiom about dense linear orders (or provable theorem about the ordered rationals) to find it. My feeling is that a proof of the theorem claimed on this page has to argue doing that (appealing to the axioms and theorems when it wants a point), I don't know how else to "get at" the idea of a euclidean line. But again, this is my issue, I'm not sure what axioms are being used, or what theorems are already known. With Hilbert's axioms, I can use the above argument to embed $(\mathbb{Q}, <)$ into a line, and then extend this to an embedding of $(\mathbb{R},<)$ using supremums.

I'm really sorry this is dragging on, and I've got a terrible tendency to make my responses longer and longer when I'm trying to discuss something. I know this is probably taking a significant amount of time to read and respond to, so I'll thank you for that. But, I'm not an intuitionist :P

Qedetc 14:33, 10 June 2011 (CDT)

Okay then, let's take a step back: I'm trying to work out what your problem is:

a) That you don't believe that the points in a straight line are countable;

b) That you believe they may be countable but you believe it is impossible to prove it;

c) Because Euclid did not explicitly raise the subject of the cardinality of the points in an infinite straight line, it is fallacious to suggest what such cardinality it is;

d) As a "Euclidean straight line" (your words not mine, I just introduced it with how Euclid defined it) can consist only of points that can be constructed by Euclidean methods (i.e. ruler and compasses) it is invalid to discuss points on a straight line that can not be so constructed (which rules cube roots out for starters).

Or what? --prime mover 15:38, 10 June 2011 (CDT)

a) I don't know if the axioms of euclidean geometry force a particular cardinality for lines. This amounts to me not being sure that the cardinality of a straight line is determined. I don't have any particular beliefs about what the cardinality is or is not, apart from knowing that it is very clearly at least countable infinite. Analogy: we know from the axioms of dense linear orders that they are at least countably infinite; we cannot say that they are countable, nor can we say that they are uncountable. I am wondering if the same sort of thing is going on.

b) I never said I believe them to be one thing or the other. I mentioned that in at least one formulation (Tarski's) of euclidean geometry, I'm pretty sure it's possible to have countable models (and as a side note now, also models where lines are any arbitrary infinite cardinality; I think we can just use the Lowenheim-Skolem theorem on suitable formulations of Tarski's theory), though I doubt this is what people typically mean when they say "euclidean geometry". But, to motivate my skepticism, if this is so, the existence of these different size models prohibits a bijection from $\mathbb{R}$ to a line necessarily existing. It also prohibits a bijection from $\mathbb{N}$ to a line necessarily existing. This is for the same reason as the dense linear orders comment in (a). Such bijections might exist for lines in a particular model, but one would not be able to say it in general. In this case, it wouldn't make sense to say straight lines are countable or uncountable; the cardinality of a straight line wouldn't be a fixed thing. Again though, this was just one particular axiomatization, and probably not the normal one.

c) I never suggested it is fallacious to try to assign a cardinality (although I guess I'm suggesting it might be fallacious to do so, depending on the answer to my problem :P ). I'm entirely open to the possibility that despite not knowing anything about distinct infinite cardinals, Euclid may have had assumptions which ensure something about the cardinality of lines in his geometry. This wouldn't be anything crazy. Analogy: you can axiomatically characterize the real numbers without ever mentioning or knowing anything about cardinality, and yet someone can use your axioms to prove that no bijection between $\mathbb{N}$ and $\mathbb{R}$ exists using those axioms.

d) I never suggested that a line only consists of the points which can be constructed, nor did I suggest that I want this to be the case. I even ranted for a while about how I very much don't hold this view (though it's mixed in, indented into the other text, so you might have missed it). I mentioned, we know $\mathbb{R}^n$ is a model and clearly fails this; so it is definitely possible that there can be more than just the constructible points. The theorem on this page looks to me like it suggests however that there are necessarily more points than the constructible ones. If a proof exists, as far as I can tell, it must mean we're using some axioms for geometry that force there to be more points than just the ones that are constructible. Or we're using some fixed model of geometry or something. But, yes, if there is no guarantee from the axioms that $2^{1/3}$ exists, then it doesn't make sense to talk about $2^{1/3}$ all the time, even if it is an element in a particular model. It would be like trying to talk about $2^{1/3}$ when discussing infinite rings. It's definitely there when we think about $(\mathbb{R}, +, \cdot, 0, 1)$, but it isn't when we think about $(\mathbb{Q}, +, \cdot, 0, 1)$. Contrast this with talking about $4$, which is certainly always there for every model. We can prove from the axioms for infinite rings that there is an element $x$ such that $x = 1+1+1+1 = 4$. We cannot prove from the axioms of an infinite ring that there is an element $x$ such that $x^3 = 2$.

-- Qedetc 17:08, 10 June 2011 (CDT)

I surrender. :-) So much of this is way over my head. Thanks for taking the time to share all this.

I think the point I was trying to make for this page was to somehow bridge the gap between the "real world" of physical space (starting with one dimension) and the abstract world of the real numbers which have (barring one or two small gaps) been proved to exist from a handful of axioms of set theory and logic. But if, as you suggest, there is no such bridge, except for the one which consists of the assumption (and which was axiomatised itself by Hilbert et al) that "every point on a line can be identified by a real number" perhaps I'm being ambitious.

It is sort-of "understood" that positions in space can be modelled by means of a coordinate frame (for example: Cartesian) but what I thought we could reach was that it could be "proved" that the Platonic ideal of "perfect" space can be directly modelled by a technique for representing every point in that space by a series of three numbers.

How would you suggest this bridge between the ZFC-based axiomatic framework and Euclidean geometry be made rigorous? We're okay with applied mathematics and physics - we just need to talk about models and approximation, and all will be well. But the vexed issue of welding the discrete (ZFC) to the continuous (Euclidean geometry) now needs to be tackled. And from what I gather I'm probably not up to it. --prime mover 17:30, 10 June 2011 (CDT)

Blah surrender - I'm not trying to win something :P It would still be worthwhile to know that they coincide (though I guess the interest is diminished if it essentially is assumed). My guess from what I've seen while looking over this stuff is that Hilbert (and others) wanted euclidean geometry to be unique in the way that $\mathbb{R}$ is unique as e.g. a complete archimedean ordered field, so they need those assumptions.

I'm not going to claim I'm more prepared for this than you are. Like I keep saying, I don't know much geometry. But, I'd guess it doesn't need to make any more explicit appeals to set theory than you see in real analysis courses or group theory courses or whatever to be satisfactory though. I guess it depends what your aims are. -- Qedetc 19:09, 10 June 2011 (CDT)

What about Archimedes' work on surfaces and volumes? Much of that was a precursor to the Riemann integral, in that (in two dimensions) he inscribed and superscribed many-sided polygons about less tractable shapes -- it was a while ago I read any of it so I can't remember to what extent he used a limiting process. I think he showed arbitrarily small difference between the area of the exterior and interior polygon, so perhaps completeness was implicit in his work. --Linus44 19:34, 10 June 2011 (CDT)

Tarski's Proof

I'll quote Tarski's words here, just to have someone confirm I'm PW-izing the proof correctly.

"Suppose we have a half line issuing from the point $O$, with a segment marked off indicating the unit of length. Further let $Y$ be any point on the half-line. Then the segment $OY$ can be measured, that is to say, one can correlate with it a certain non-negative number $x$ called the length of the segment...[C]onversely, to every non-negative number $x$ we may also construct a uniquely determined segment $OY$ on the half-line under consideration, whose length equals $x$...(and it would be equally simple to set up a one-to-one correspondence between the points of the entire line and all real numbers)." --GFauxPas 19:17, 19 November 2011 (CST)

Resolution

I have found and put up all of Tarski's Axioms. Hopefully we can assuage Qedetc's concerns now, after painfully going through all of the axioms and figuring out if they're necessary for the proof. Not it. --GFauxPas 10:41, 29 January 2012 (EST)

I can see how to use transfinite recursion to define order-preserving injections from the reals to the line and vice-versa, using the axiom of Continuity as a sort of least-upper-bound property, but I don't quite know how to get to a bijection. Is there a CBS equivalent for order-preserving injections, or is some other variant needed? Alternatively, can we be more precise and explicitly define the bijection transfinitely? --Scshunt sometime on 1-Sept-2014

I asked the SA message boards and was directed to this http://math.stackexchange.com/questions/151076/a-cantor-schroder-bernstein-theorem-for-partially-ordered-sets --GFauxPas (talk) 19:19, 1 September 2014 (UTC)

It looks like for every line segment we choose, we need to pick just one of the endpoints; the left one under the usual convention. For every line segment on $L$, we make a subset of the 2 end points. AoC to pick the left one? --GFauxPas (talk) 20:10, 1 September 2014 (UTC)

Hmm... I'm not sure if that works. We could try to map the line segments from the line into the subsets of the reals, but I have a feeling this would be a more complex mapping. I think it may be easiest to try to show that the "least upper bound" is preserved via a transfinite induction. I'll chew on this over dinner. (Also sorry about forgetting to sign last time) Scshunt (talk) 22:51, 3 September 2014 (UTC)

Proof?

I fail to see why this proof cannot be applied on $\N$. --kc_kennylau (talk) 09:43, 1 November 2016 (EDT)

Because it is not necessarily the case that:

$\forall p \in L: \exists x \in \N: \left({p, x}\right) \in h$

--prime mover (talk) 10:59, 1 November 2016 (EDT)

Why not? --kc_kennylau (talk) 11:01, 1 November 2016 (EDT)

Don't know. Do you? --prime mover (talk) 11:03, 1 November 2016 (EDT)

The proof is incomplete as it is. It should invoke at some point the density of the straight line, as well as its infinitude and "completeness", to exclude $\N, \Q$ etc. — Lord_Farin (talk) 13:17, 1 November 2016 (EDT)

Quite sure infinitude is circular. --kc_kennylau (talk) 07:02, 2 November 2016 (EDT)