Super densely ordered sets
mar...@gmail.com
that S is super densely ordered by > iff:
For all subsets X and Y of S with |X| <= Aleph_0 and |Y| <= Aleph_0
such that a < b for all a in X, all b in Y, there exists c in S such
that a < c < b for all a in X, all b in Y.
Do super densely ordered sets exist?
If so, do we get smaller collection of such sets if we replace Aleph_0
with a greater cardinal in the above definition?
I think that there are no super densely ordered denumerable sets
because:
Let assume that S is denumerable and w is an element of S such that
there are x and y in S with x < w < y. Then the sets X = {a : a < w}
and Y = {b : w <= b} will satisfy |X| <= Alpeh_0, |Y| <= Aleph_0 and a
< b for all a in X, all b in Y. However according to the super density
property in this case there must exist c in S such that a < c < b for
all a in X, all b in Y. So c must lie outside of X and Y, but X \/ Y =
S. Therefore c is in S and is not in S, which is a contradiction, so
the assumption is false.
Is this reasoning correct?
Thanks in advance,
Marc
quasi
Yes.
quasi
Dave L. Renfro
> Let S be infinite set and > be a strict linear order on S. Let say
> that S is super densely ordered by > iff:
>
> For all subsets X and Y of S with |X| <= Aleph_0 and |Y| <= Aleph_0
> such that a < b for all a in X, all b in Y, there exists c in S such
> that a < c < b for all a in X, all b in Y.
>
> Do super densely ordered sets exist?
> If so, do we get smaller collection of such sets if we replace Aleph_0
> with a greater cardinal in the above definition?
Without reading this very carefully (I only have a few moments to
comment where I'm at), I'll just suggest that you might want to
look at Hausdorff's eta_alpha orderings. Look in most any book
on set theory that has a non-trivial amount devoted to ordered
sets (Sierpinski's "Cardinal and Ordinal Numbers", for example)
or Joseph G. Rosenstein's book "Linear Orderings".
Dave L. Renfro
Mariano Suárez-Alvarez
> Let S be infinite set and > be a strict linear order on S. Let say
> that S is super densely ordered by > iff:
>
> For all subsets X and Y of S with |X| <= Aleph_0 and |Y| <= Aleph_0
> such that a < b for all a in X, all b in Y, there exists c in S such
> that a < c < b for all a in X, all b in Y.
>
> Do super densely ordered sets exist?
If k is a cardinal, let us say that a total order S
is k-super dense if whenever X and Y are
non-empty subsets of S of cardinality at most k,
and such that for all x in X and all y in Y we have
x < y, there exists an element z in S such that
for all x in X and all y in Y we have x < z < y.
Pick any linear order (S, <) and pick a cardinal k.
Consider the set P(S) of all pairs (X, Y) of
non-empty subsets of S such that
- |X| <= k, |Y| <= k;
- for all x in X, for all y in Y, x < y; and
- there does not exist an element z in S such
that for all x in X and for all y in Y,
x <= z <= y
Let S' = S union P(S), and define a relation << on
S' such that
- if x, y are in S, then x << y if and only if
x < y;
- if z is in S and (X, Y) is in P(S), we put
z << (X, Y) iff there exists x in X
such that z < x;
- if z is in S and (X, Y) is in P(S), we put
(X, Y) << z iff there exists y in Y
such that y < z;
- if (X, Y) and (U, V) are in P(S), then
(X, Y) << (U, V) iff there exist y in Y
and u in U such that y < u.
The relation << is anti-symmetric and transitive.
Therefore its reflexive clausure is an order on
S'. It is not necessarily a total order, but
it is well know that there is another relation
<<< on S' extending << which is total.
Notice that whenever (X, Y) is in P(S), we have
x <<< (X, Y) <<< y
for all x in X and all y in Y.
Thus S' is `closer' than S from being k-super dense,
since we've added all the missing points. Of course,
since we have added new points, we cannot claim that
S' itself is k-super dense.
But we can do transfinite induction so as to
repeat the process many times. That is, let us we put
S_0 = S, and define inductively for any ordinal
alpha
S_{alpha+1} = (S_alpha)'
and, when alpha has no immediate predecessor,
S_alpha = union_{beta < alpha} S_beta
with the obvious order.
Then I claim that there exists an ordinal eta such
that S_eta is k-super dense. I don't have space
in this margin, though. (The proof should be along
very standard lines)
If eta is the least ordinal such that S_eta
is k-super dense, call S_eta the k-super dense
closure of S and call eta the k-wholiness of S
> If so, do we get smaller collection of such sets if we replace Aleph_0
> with a greater cardinal in the above definition?
I have not thought this through, but I would expect that
if k and k' are two cardinals such that k < k', and we start
with a totally ordered set S of cardinal strictly less than k,
then the k-wholiness of S is strictly less that the k'-wholiness
of S, and that the cardinal of the k-super dense closure of S
to be strictly less than the cardinal of the k'-super dense
closure of S. This in particular would entail that
some k-super dense sets are not k'-super dense.
-- m
Mariano Suárez-Alvarez
Indeed, let eta be the smallest regular initial
ordinal which has cardinal strictly bigger than
k. If X and Y are non-empty subsets of S_eta of
cardinality at most k such that for all x in X
and all y in Y we have x < y, then since eta
is a limit ordinal, every element of X union Y
belongs to S_gamma for some ordinal gamma < eta.
Since the cardinality of X union Y is
strictly less than k, there exists an ordinal
phi < eta such that all the elements of X union
Y are in S_phi. There exists an element
z in S_{phi+1} such that x < z < y for all
x in X and all y in Y. Since S_{phi+1}
is a subset of S_eta (with matching orders),
we see that S_eta is k-super dense.
-- m
Aatu Koskensilta
> Indeed, let eta be the smallest regular initial
> ordinal which has cardinal strictly bigger than
> k. If X and Y are non-empty subsets of S_eta of
> cardinality at most k such that for all x in X
> and all y in Y we have x < y, then since eta
> is a limit ordinal, every element of X union Y
> belongs to S_gamma for some ordinal gamma < eta.
> Since the cardinality of X union Y is
> strictly less than k, there exists an ordinal
> phi < eta such that all the elements of X union
> Y are in S_phi. There exists an element
> z in S_{phi+1} such that x < z < y for all
> x in X and all y in Y. Since S_{phi+1}
> is a subset of S_eta (with matching orders),
> we see that S_eta is k-super dense.
An exercise for set theory aficionados: where does the above rely on
choice? Extra points if you figure out if we can do without choice or
not.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Mariano Suárez-Alvarez
wrote:
> On 2008-02-15, in sci.math, Mariano Suárez-Alvarez wrote:
>
> > Indeed, let eta be the smallest regular initial
> > ordinal which has cardinal strictly bigger than
> > k. If X and Y are non-empty subsets of S_eta of
> > cardinality at most k such that for all x in X
> > and all y in Y we have x < y, then since eta
> > is a limit ordinal, every element of X union Y
> > belongs to S_gamma for some ordinal gamma < eta.
> > Since the cardinality of X union Y is
> > strictly less than k, there exists an ordinal
> > phi < eta such that all the elements of X union
> > Y are in S_phi. There exists an element
> > z in S_{phi+1} such that x < z < y for all
> > x in X and all y in Y. Since S_{phi+1}
> > is a subset of S_eta (with matching orders),
> > we see that S_eta is k-super dense.
>
> An exercise for set theory aficionados: where does the above rely on
> choice? Extra points if you figure out if we can do without choice or
> not.
I used already the axiom of choice once per
step in the transfinite construction of S_eta,
in order to complete a partial order to a total
order, so this is rather academic (not that
the whole thing isn't academic, of course ;-) )
-- m
Aatu Koskensilta
Obviously I wasn't paying attention! I had in mind that without
choice, for a cardinal kappa there need be no regular cardinal greater
than kappa.
William Elliot
> Let S be infinite set and > be a strict linear order on S. Let say
> that S is super densely ordered by > iff:
>
> For all subsets X and Y of S with |X| <= Aleph_0 and |Y| <= Aleph_0
> such that a < b for all a in X, all b in Y, there exists c in S such
> that a < c < b for all a in X, all b in Y.
>
> Do super densely ordered sets exist?
Obviously nulset and {a} are super dense linear orders. ;-)
Q, R are not superdense.
Let X = { -1/n | n in N }, Y = { 0, 1/n | n in N }
or X = { 0 | n in N }, Y = { 1/n | n in N }
Let S be a complete linear order.
Let X = { aj | j in N } be an increasing sequence
a1 < a2 < a3 <
X and Y = { sup X } shows S is not superdense.
In fact for a superdense linear order to exist, it's necessary
it's a dense order,
every increasing sequence does not have a supremum,
every decreasing sequence does not have an infinum.
This implies, it's at least totally disconnected.
I'd suppect it's extremely disconnected.
Mariano Suárez-Alvarez
FWIW, the above construction is not really correct.
One needs a slightly weaker order on the set S', for
otherwise things do not work as well as implied above.
I wrote up the whole thing, hopefully corrected, and
the result is available at <http://mate.dm.uba.ar/~aldoc9/
Publicaciones/Notas/dense.pdf>
Any comments welcome, of course.
-- m
Denis Feldmann
A much simpler construction (equivalent ?) was discussed here a few
years ago : the idea is to use analog of the binary construction of
reals (as sequences of 0 and 1) : we take the lexicographic order on the
sequences of {0,1]^alpha (where alpha is a cardinal aleph _x), the trick
being of using only those sequences such that there is a *last* 1, i.e
an ordinal beta <alpha such that s_beta =1 and for all beta'>beta,
s_beta'=0.
>
> -- m
Mariano Suárez-Alvarez
wrote:
I guessed there was a direct construction. Yet arguments
like the one above, in which one simply tries to fix a
non-example into becoming an example with so much
persistence that it finally gives up and it just gives
up and does what you want, have always struck me as fun ;-)
-- m
William Elliot
> >> On Feb 15, 12:27 pm, marc...@gmail.com wrote:
> >>
> >>> Let S be infinite set and > be a strict linear order on S. Let say
> >>> that S is super densely ordered by > iff:
> >>> For all subsets X and Y of S with |X| <= Aleph_0 and |Y| <= Aleph_0
> >>> such that a < b for all a in X, all b in Y, there exists c in S such
> >>> that a < c < b for all a in X, all b in Y.
> >>> Do super densely ordered sets exist?
If S is cofinal to aleph_0, then S isn't super dense.
Let X be a cofinal set and Y empty.
> A much simpler construction (equivalent ?) was discussed here a few
> years ago : the idea is to use analog of the binary construction of
> reals (as sequences of 0 and 1) : we take the lexicographic order on the
> sequences of {0,1]^alpha (where alpha is a cardinal aleph _x), the trick
> being of using only those sequences such that there is a *last* 1, i.e
> an ordinal beta <alpha such that s_beta =1 and for all beta'>beta,
> s_beta'=0.
Because of the above, aleph_xi cannot be cofinal to aleph_0.
In particular, xi /= 0, omega_0.
To detail your 'last one', you are requiring that there is at
least one 1. Otherwise the zero sequence O, is bottom element and
S = lex { 0,1 }^aleph_xi restricted to 0 terminating sequences
isn't superdense for letting X be empty and Y = { O }.