Prior to about five minutes ago, for some reason I had the idea that a countably infinite well-ordered set can have a first member or a last member but not both.
But I’m starting to think that was wrong.
Could some kind set-theory type provide a hint as to how I might decide the question one way or the other?
On further reflection, I’m even more convinced they can indeed have both first and last members. For example (and there are surely better examples), here’s a well-ordering of the natural numbers with both a first and last element. Take 0 to be the least element. Take 1 to be the greatest element. Now the successor of 0 is 2, the successor of 2 is 4, and so on. Meanwhile, the decessor of 1 is 3, the decessor of 3 is 5 and so on. Now, given any pair of natural numbers, I can tell you which is greater. If one is even and the other odd, then the odd one is greater. And if both are odd, then the one closest to 1 on the well-ordering line is greater. And if they’re both even, then the one furthest from 0 on the well-ordering line is greater.
Normally, well-ordering is taken to mean “Every inhabited subset has a least element” (or, non-classically, that the set is totally ordered and every inductive subset contains every element, where a subset is inductive if it contains X whenever it contains all the elements below X). Your example would not be well-ordered in this sense; the odd numbers would have no least element. You seem to be using well-ordered to mean simply “totally/linearly ordered”.
That having been said, it is possible to have a countably infinite well-ordered set: for example, just use the standard ordering on 1, 2, 3, …, and make 0 higher than all of those. Lowest element: 1. Highest element: 0. You can see for yourself that it is not only totally ordered, but in fact well-ordered, in the above senses.
(Ah, I recall now that conventionally well-ordered sets are always said to have a “least” element. Sorry about that. Hopefully the question I was asking shows through the muddle.)
Yeah, having just looked up a bunch of definitions rather than trying to remember them from years ago, I see all this now.
Something else I’d forgotten was that there can be elements other than the least element of a well-ordering which have no predecessor.
I had this argument that the reals can’t be well-ordered, and I was trying to figure out where it went wrong, thinking surely I’d made some error somewhere. And it turns out the error was everywhere, because I’d been using a completely incorrect concept of what “well-ordering” means… :smack:
Hey, while I have your attention, here’s a related question.
What’s it called when you’ve got two ordered sets that are put into one to one correspondence such that if a is greater than b according to the first set’s ordering, then f(a) is greater than f(b) according to the second set’s ordering?
Okay, sorry, another question before anyone’s even answered the last one:
Am I right to (now) think the following sentence false?:
If S is the set of all natural numbers plus a single additional element p, together with an ordering identical to the greater-than relation for the naturals except that p is considered to be “greater” (on this new relation) than all the naturals,* then the elements of S can be put into one-to-one correspondence with the naturals N1, N2, N3 etc in such a way that Nx > Ny iff f(nx) >> f(ny). (">>" being the ordering relation on S, of course.)
*Could I have just put this in terms of the set of all naturals plus omega?
I thought for a while that the above was true. But now I’m thinking it is false, and that I thought it true because I’d forgotten about the idea of an order type, i.e., accidentally confused cardinality and ordinality. S and the naturals have the same cardinality, but not the same ordinality (right?) and their differing ordinalities mean that while they can be put into one-to-one correspondence, they can’t be put into such a correspondence that respects both of their orderings. (Right?)
Assuming that “if” is meant as an “if and only if”, one term for this would be an order-isomorphism. In general, any structure-preserving map with an inverse which also preserves the same structure is called an isomorphism (of whatever structure).
Yes, this is false; whatever natural p is put in correspondence with would have to be greater than all other naturals, which is impossible.
Sure. But it doesn’t matter; “omega” is just the name conventionally given to an object defined by the same ordinal properties you used above to define “p”.
f is an order-preserving map (alternately, monotonic).
ETA: If you mean a < b iff f(a) < f(b), that’s an order isomorphism. But if you just mean a < b implies f(a) < f(b), that’s the order preserving map. Note that it’s customary to talk in terms of < rather than >, although the choice is arbitrary.
Missing words reinstated in bold (not that anyone seems to have been tripped up by their loss)
Also, just to clarify ultrafilter’s comment: any function f with the property that a < b implies f(a) < f(b) is considered order-preserving, whether or not f is also a one-to-one correspondence/bijection/isomorphism of sets/whatever you want to call it. I don’t know that it’s common to talk about functions which are both bijections and order-preserving without further requiring that their inverses are also order-preserving (i.e., without requiring that they be full-on order-isomorphisms), but I suppose you could call them order-preserving bijections, though this is liable to be misinterpreted, so really the best thing to do is to note that possible misinterpretation upfront and spell out that it is not what is intended (if, indeed, it is not…).