Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Wiki says that an infinite set may be way-below another set. More precisely, in a power set, pow(S), with subset order and with X and Y subsets of S, does X way-below Y entail that X is finite?

http://en.wikipedia.org/wiki/Domain_theory

"...but even infinite sets can be way below some other set"

share|improve this question

3 Answers 3

I think that Andrej Bauer's answer doesn't really address the important point. Obviously being way below is an order theoretic notion, i.e., it is preserved under isomorphism, while being a finite set is not an order theoretic notion. In particular, whenever you have any order with an element way below another, you can replace the smaller one by an infinite set that fits into the order exactly as the original element. Now there is an infinite set way below another set. But this is artificial and doesn't really say anything.

However, even in partial orders of sets an infinite set can be way below another set. Identify each $r\in\mathbb R$ with the set $\{q\in\mathbb Q:q\le r\}$, i.e., with the left half of a Dedekind cut in $\mathbb Q$ that corresponds to $r$.

Now the order on $\mathbb R$ is just set-theoretic inclusion of these sets of rational numbers. However, as Andrej points out, $0$ is way below $1$. This does not conflict with James Cranch's answer, since the partial order of sets that we are looking at is not the full power set of $\mathbb Q$ but just a subordering of that, and in particular one that does not contain any finite set.

It can be shown that every partial order is in fact isomorphic to a partial order of infinite sets ordered by inclusion, but the point in my example (or Andrej's example, for that matter) is that whenever $\mathbb P$ is a collection of sets such that $(\mathbb P,\subseteq)$ is isomorphic to $(\mathbb R,\leq)$, then the element corresponding to $0$ is way below the element corresponding to $1$, simply since this is an order theoretic notion, but $0$ is never represented by a finite set, since the corresponding element of $\mathbb P$ it has infinitely many sets below it, i.e., infinitely many subsets.

share|improve this answer
    
Indeed, an ad hoc way of doing that replacement is to consider two infinite sets $A\subset B$, and worth with the set of sets $A\subset X\subset B$: a kind of relative powerset. Of course, this is just the same thing as the powerset $\mathbb{P}(B\backslash A)$, so the sets that are way below others are the sets which are $A\cup F$ for $F$ finite. If $A$ is infinite, these are infinite sets! –  James Cranch May 12 '11 at 9:21

In a power set, isn't Y always the supremum of the directed set of all its finite subsets? That would seem to me to entail that X must be finite.


EDIT: Perhaps the authors were thinking of a different structure. If you consider the partial ordering on isomorphism classes of subsets of $A$, where $X\leq Y$ if there is an injection from $X$ to $Y$ (which need not be an inclusion), then things are rather different.

The poset then looks like a truncation of the poset of ordinals.

And the way-below relation is very different. For example, $X$ is way below $Y$ if there is a set whose size is a limit cardinal $Z$ such that $X\lt Z\leq Y$.

Hence a set of cardinality $\aleph_{17}$ will be way below a set of cardinality $\aleph_{\omega}$.

share|improve this answer
    
This is not a poset. –  Emil Jeřábek May 12 '11 at 16:15
    
I've edited it so that it will be. –  James Cranch May 12 '11 at 19:27

I think what Wikipedia wants to say (but does so badly) is that there can be other order relations in which one infinite set is way below another. For example, if we view real numbers as equivalence classes of Cauchy sequences, then every real is an infinite set, yet 0 is way below 1 with respect to the usual order of the reals.

Of course, the way below relation arising from the subset relation is "finite subset".

So, don't trust everything that's written in Wikipedia.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.