Order theory deals with properties of orders, usually partial orders or quasi orders but not only those. Questions about properties of orders, general or particular, may fit into this category, as well as questions about properties of subsets and elements of an ordered set.

learn more… | top users | synonyms

23
votes
2answers
453 views

Are irrational numbers order-isomorphic to real transcendental numbers?

I know that rational numbers are order-isomorphic to real algebraic numbers. Does it imply that irrational numbers are order-isomorphic to real transcendental numbers? I know that the order type of ...
22
votes
2answers
891 views

Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?

I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago. Reading the wikipedia article linked above, I ...
21
votes
6answers
727 views

Embedding ordinals in $\mathbb{Q}$

All countable ordinals are embeddable in $\mathbb{Q}$. For "small" countable ordinals, it is simple to do this explicitly. $\omega$ is trivial, $\omega+1$ can be e.g. done as $\{\frac{n}{n+1}:n\in ...
18
votes
4answers
290 views

Is there a name for this kind of “betweenness structure”?

A homeomorphism $\mathbb R\to\mathbb R$ is almost the same thing as an order isomorphism, except that a homeophorphism can also be an order anti-isomorphism. I'm wondering whether there is a natural ...
18
votes
2answers
808 views

Order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$

Do you have a simple example of order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$? On $\mathbb Q$, I use the usual order and on $\mathbb Q\times\mathbb Q$, I define the ...
16
votes
6answers
2k views

Is the set of real numbers the largest possible totally ordered set?

Because I find any totally ordered set can be "lined up" in a straight line, I'm guessing that the set of all the real numbers is the biggest totally ordered set possible. In the sense that any other ...
16
votes
2answers
351 views

Is $(\pmb{1} + \pmb{\eta})\cdot\pmb{\omega_1} = \pmb{1} + \pmb{\eta}\cdot\pmb{\omega_1}$?

$\pmb{\eta}$ - order type of $\mathbb{Q}$. $\pmb{1}$ - order type of a singleton set. $\pmb{\omega_0}$ - order type of $\mathbb{N}$. $\pmb{\omega_1}$ - order type of the first uncountable ordinal. ...
15
votes
7answers
6k views

difference between maximal element and greatest element

I know that it's very elementary question but I still don't fully understand difference between maximal element and greatest element. If it's possible, please explain to me this difference with some ...
15
votes
7answers
10k views

Example of Partial Order that's not a Total Order and why?

I'm looking for a simple example of a partial order which is not a total order so that I can grasp the concept and the difference between the two. An explanation of why the example is a partial ...
14
votes
4answers
5k views

What does “curly (curved) less than” sign $\succcurlyeq$ mean?

I am reading "Convex Optimization" by Stephen Boyd. He is using a curved greater than and curved less than equal to signs. $f(x^*) \succcurlyeq \alpha$ or $f(x*) \preccurlyeq \alpha$ Can someone ...
14
votes
2answers
265 views

The preorder of countable order types

Consider the set $\mathcal{O}$ of order types corresponding to all posets of cardinality at most $\aleph_0$. The set $\mathcal{O}$ is a preorder under embeddability of its elements (note that some ...
13
votes
2answers
2k views

Every partial order can be extended to a linear ordering

How do I show that every partial order can be extended to a linear ordering? I think that I manage to prove that claim for finite set, how can I prove it for infinite set? Thank you.
13
votes
1answer
101 views

Is there a nice well-behaved order isomorphism between the real algebraic numbers and the rationals?

Via Cantor's back-and-forth method we know that the linearly ordered set of all rational numbers and the linearly ordered set of all real algebraic numbers are isomorphic. But from the point of view ...
12
votes
3answers
660 views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
12
votes
2answers
470 views

Any good decomposition theorems for total orders?

I'm learning about set theory and partial orders, well orders, total orders, etc. I'm curious to know of any good decomposition theorems that apply to all (or very general types of) total orders. ...
12
votes
2answers
230 views

Is it possible to construct an ordered field which is also algebraically closed?

It is well known that while the real numbers are totally ordered, they are not algebraically closed, and while the complex numbers are algebraically closed, they are not totally ordered. Is it ...
12
votes
3answers
842 views

Examples of rings with ideal lattice isomorphic to $M_3$, $N_5$

In thinking about this recent question, I was reading about distributive lattices, and the Wikipedia article includes a very interesting characterization: A lattice is distributive if and only if ...
12
votes
2answers
297 views

Is every suborder of $\mathbb{R}$ homeomorphic to some subspace of $\mathbb{R}$?

Let $X \subset \mathbb{R}$ and give $X$ its order topology. (When) is it true that $X$ is homeomorphic to some subspace of $Y \subset \mathbb{R}$? Example: Let $X = [0,1) \cup \{2\} \cup (3,4]$, ...
12
votes
0answers
598 views

How to find a total order with constrained comparisons

There are 25 horses with different speeds. My goal is to rank all of them, by using only runs with 5 horses, and taking partial rankings. How many runs do I need, at minumum, to complete my task? As ...
11
votes
6answers
2k views

Is there a real number which comes just after a particular real number?

This is like when we say that the integer which comes just after $2$ is $3$. Is there a real number which comes just after a particular real number? For example: Is there a number which comes just ...
11
votes
4answers
274 views

Given an infinite poset of a certain cardinality, does it contains always a chain or antichain of the same cardinality?

It is known that given an infinite poset, it always contains an infinite chain or antichain; moreover, there is a constructive proof that we can find a continuous chain in $P(\mathbb{N})$; so, in ...
11
votes
3answers
2k views

Showing any countable, dense, linear ordering is isomorphic to a subset of $\mathbb{Q}$

I'm trying to knock out a few of the later exercises from Enderton's Elements of Set Theory. This problem is #17, found on page 227. A partial ordering $R$ is said to be dense iff whenever $xRz$, ...
11
votes
2answers
175 views

Which of these constructions are left adjoints?

A groupoid can be regarded as a small category in which every arrow is an isomorphism A monoid can be regarded as a small category with only a single object A preorder can be regarded as a small ...
10
votes
5answers
437 views

Foundation of ordering of real numbers

This might be a silly question, but what is the mathematical foundation for the ordering of the real numbers? How do we know that $1<2$ or $300<1000$... Are the real numbers simply defined as ...
10
votes
4answers
766 views

Examples of Galois connections?

On TWF week 201, J. Baez explains the basics of Galois theory, and say at the end : But here's the big secret: this has NOTHING TO DO WITH FIELDS! It works for ANY sort of mathematical gadget! If ...
10
votes
1answer
379 views

Linearly ordered sets “somewhat similar” to $\mathbb{Q}$

$\pmb{\eta}$ - order type of $\mathbb{Q}$. $\pmb{\eta} + \pmb{1}$ - order type of $\mathbb{Q}\cap(0, 1]$. $\pmb{\omega_1}$ - order type of the first uncountable ordinal. Let's say that a linear ...
10
votes
1answer
256 views

Is this a characterization of well-orders?

While grading some papers and thinking about a question related to well-orders (in particular, pointing a mistake in a solution), I came to think of a reasonable characterization for well-orders. I ...
10
votes
2answers
751 views

The p-adic numbers as an ordered group

So I understand that there is no order on the field of p-adic numbers $\mathbb{Q_p}$ that makes it into an ordered field (i.e.) compatible with both addition and multiplication. Now, from the ...
10
votes
1answer
192 views

Is there a non-trivial countably transitive linear order?

A linear order $<$ on a set S is countably transitive iff, whenever A and B are order-isomorphic countable subsets of S, there is an order-automorphism of S which maps A onto B. Does such an order ...
10
votes
1answer
94 views

a totally ordered set with small well ordered set has to be small?

doing something quite different the following question came to me: 1)If you have a totally ordered set A such that all the well ordered subset are at most countable, is it true that A has at most the ...
10
votes
1answer
175 views

Is $\pmb{\eta}\cdot\pmb{\omega_1} = (\pmb{\eta} + \pmb{1})\cdot\pmb{\omega_1}$?

$\pmb{\eta}$ - order type of $\mathbb{Q}$. $\pmb{1}$ - order type of a singleton set. $\pmb{\omega_0}$ - order type of $\mathbb{N}$. $\pmb{\omega_1}$ - order type of the first uncountable ordinal. ...
10
votes
3answers
483 views

An order type $\tau$ equal to its power $\tau^n, n>2$

In this question we are concerned only with linear (aka total) order types. By a cardinality of an order type we understand a cardinality of an instance of this type, which obviously does not depend ...
10
votes
1answer
183 views

What is known about this well-ordering of the rationals in a finite interval?

Given any interval $I=(a,b) \subset \mathbb R^+$, we may order the rationals in $I$ with a denominator-first lexicographic order, as follows: First, we list, in increasing order of numerator, all $q ...
9
votes
3answers
314 views

A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets

If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ?
9
votes
2answers
322 views

How many ordinals can we cram into $\mathbb{R}_+$, respecting order?

I've been pondering the following question. How can we measure the amount of "space" above an element $p$ in a partially ordered set $P$? One way would be to try to cram the elements of ...
9
votes
3answers
331 views

With Choice, is any linearly ordered set well-ordered if no subset has order type $\omega^*$?

I've been fumbling around with order types and ordinals these past few days. I read about partial, total, and well-ordered structures, and I'm curious to see if a linearly ordered set has no subset ...
9
votes
2answers
248 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
9
votes
2answers
585 views

Are ideals in rings and lattices related?

There are (at least) two notions of ideals: An ideal in a ring is a set closed under addition and multiplication by arbitrary element. An ideal in a lattice is a set closed under taking smaller ...
9
votes
2answers
235 views

When does a left adjoint between Heyting algebras preserve 1?

This is an exercise from Johnstone's book Stone Spaces: Let $f: A \to B$ and $g: B \to A$ be order-preserving maps between complete Heyting algebras with $f$ left adjoint of $g$. Show that $f$ ...
9
votes
1answer
213 views

Atoms necessary for the existence of a generic filter?

I'm reading Some applications of the method of forcing by Todorchevich and Farah and one of the exercises seems to be wrong to me. Definitions We fix some partially ordered set $(P,\preceq)$. A ...
9
votes
1answer
144 views

The “Largeness” of Subsets of the Natural Numbers

Recently, I was thinking about the Erdős conjecture on arithmetic progressions, which says that, if, for a set $A\subseteq\mathbb{N}$, the sum $\sum_{a\in A}\frac{1}a$ diverges (i.e. "A is large"), ...
9
votes
1answer
123 views

Intuition for a certain tensor product.

Tensor products occur in lots of places and until recently I thought I understood them at least reasonably well. During the past few weeks, however, I've attended several talks where the tensor ...
9
votes
0answers
289 views

What do linearly ordered abelian groups look like?

Recently a post on MathOverflow connected a theorem about ordered abelian groups to the axiom of choice, and it made me want to try and play with these objects a bit. But it appears to me that I ...
8
votes
7answers
1k views

Give an example of a simply ordered set without the least upper bound property.

In Theorem 27.1 in Topology by Munkres, he states "Let $X$ be a simply ordered set having the least upper bound property. In the order topology, each closed interval in $X$ is compact." (The LUB ...
8
votes
3answers
432 views

Ordinal exponentiation - $2^{\omega}=\omega$

This is my understanding of ordinal arithmetic - two ordinals are the same as one another if there is an order-preserving bijection between them. So for instance $$1+\omega = \omega$$ because if ...
8
votes
3answers
418 views

Without appealing to choice, can we prove that if $X$ is well-orderable, then so too is $2^X$?

Without appealing to the axiom of choice, it can be shown that (Proposition:) if $X$ is well-orderable, then $2^X$ is totally-orderable. Question: can we show the stronger result that if $X$ is ...
8
votes
4answers
342 views

Is there an element with no fixed point and of infinite order in $\operatorname{Sym}(X)$ for $X$ infinite?

Let $X$ be an infinite set. Let $\operatorname {Sym}(X)$ denote the group of all bijections from $X$ onto itself. I have been thinking about the existence of elements of infinite order in this group. ...
8
votes
2answers
337 views

Existence of a utility function on the reals

Suppose I have $\preceq$, a total order on $\mathbb R^n$. I wish to show that there is a utility function $u:\mathbb R^n\to\mathbb R$ such that $x\preceq y \leftrightarrow u(x)\leq u(y)$. I came up ...
8
votes
1answer
175 views

Do there exist totally ordered sets with the 'distinct order type' property that are not well-ordered?

Define that the order type of an element $x$ in a totally ordered set $X$ is the order type of $\{w \in X\mid w < x\}$. Under this definition, distinct elements of a well-ordered set have distinct ...
8
votes
2answers
436 views

Why do torsion-free abelian groups admit linear orders?

I have read a theorem that says that every torsion-free abelian group admits a linear order. The proof used tensor products and so was above my head. I tried to find another proof on the web and I ...