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

24
votes
7answers
9k 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 ...
24
votes
6answers
909 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 ...
23
votes
2answers
495 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 ...
23
votes
2answers
975 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 ...
20
votes
7answers
16k 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 ...
19
votes
4answers
309 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
1k 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 ...
17
votes
4answers
7k 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 ...
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
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.
16
votes
2answers
365 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
0answers
702 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 ...
14
votes
3answers
995 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 ...
14
votes
2answers
290 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
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$, ...
13
votes
1answer
110 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
2answers
493 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
259 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
1k 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
316 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]$, ...
11
votes
4answers
1k 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 ...
11
votes
4answers
364 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 ?
11
votes
4answers
291 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
2answers
209 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 ...
11
votes
3answers
6k views

A finite set always has a maximum and a minimum.

I am pretty confident that this statement is true. However, I am not sure how to prove it. Any hints/ideas/answers would be appreciated.
11
votes
0answers
583 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 ...
10
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 ...
10
votes
1answer
619 views

Is directed set countable, if for each element there are only finitely many smaller ones?

A directed set is a pair $(A,\leq)$ where $\leq$ is a reflexive, transitive relation such that for any $x,y\in A$ we have some $z$ such that $x,y\leq z$. (This comes up when dealing with categorical ...
10
votes
5answers
559 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
2answers
388 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 ...
10
votes
1answer
393 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
273 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
1answer
206 views

$\mathbb{R}$ and $\mathbb{R}\setminus \{0\}$ are not isomorphic as linear orders.

Informal argument So, we know that $\mathbb{R}$ with its usual topology is connected, and of course $\mathbb{R}\setminus\{0\}$ is not. Any $``$supposed" isomorphism should grant us a homeomorphism ...
10
votes
2answers
825 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
246 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
97 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
187 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
497 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
154 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"), ...
10
votes
1answer
200 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
1answer
518 views

bijective homomorphisms between non isomorphic posets, example , explanation needed

Could someone please give a super simple example of a "bijective homomorphism between a non isomorphic poset"? I don't understand the sentence marked by green in the picture taken from Awodey's book. ...
9
votes
3answers
351 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
265 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
711 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
243 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
236 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
135 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
324 views

Proving equivalence of a tree-based version of Countable Choice for families of finite sets.

In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5: Each of the following statements imply those beneath it. The countable union of ...
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
575 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 ...