# Questions tagged [order-theory]

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. Order theory is not about the order of a group nor the order of an element of a group or other alegbraic structures.

2,728 questions
Filter by
Sorted by
Tagged with
18k views

### Is there a known well ordering of the reals?

So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $R$ , if every subset has a least element. My ...
45k 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 ...
23k 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 ...
1k 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 ...
28k views

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

I am reading Boyd & Vandenberghe's Convex Optimization. The authors use curved greater than or equal to (\succcurlyeq) $$f(x^*) \succcurlyeq \alpha$$ and ...
6k 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.
23k 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.
2k views

806 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 ...
5k 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 ...
2k 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 don'...
364 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 ...
2k 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 ...
11k views

### Simplest Example of a Poset that is not a Lattice

A partially ordered set $(X, \leq)$ is called a lattice if for every pair of elements $x,y \in X$ both the infimum and suprememum of the set $\{x,y\}$ exists. I'm trying to get an intuition for how a ...
5k 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$, ...
1k 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.
207 views

### strictly increasing function from reals to reals which is never an algebraic number

Let $f:\Bbb R\rightarrow\Bbb R$ have the properties $\forall x,y\in\Bbb R,\space x<y\implies f(x)<f(y)$ and $\forall x\in\Bbb R,\space f(x)\notin\Bbb A$ where $\Bbb A$ is the set of algebraic ...
4k views

### Isn't every totally ordered set well-ordered?

A well order is a total order on a set $S$ with the property that every non-empty subset of $S$ has a least element. But surely it follows from the definition of a total order that any non-empty ...
432 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. ...
577 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 ...
2k 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 ...
2k 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 ...
4k views

### Can I always order a countable set of numbers

Suppose I have a countable subset of the real numbers $A$. Then since it is countable there is a function $f: \mathbb N \to A$ which is bijective. This function is of course a sequence, so we can ...
485 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 ...
405 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 ...
4k 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 ...
4k views

### Formal proof for A subset of the real numbers, well ordered with the normal order of $\mathbb R$, is at most $\aleph_0$

I tried to write a formal proof for the theorem: $A$ subset of $\mathbb R$ well ordered by the normal order $\implies A$ is at most of cardinality $\aleph_0$. Any suggestions? Thanks.
6k views

### What is meaning of strict weak ordering in layman's term? [closed]

I gone through many pages using Google, but not understand exact meaning of Strict-weak Ordering term. I have this requirement while sorting strings.
584 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 ...
221 views

### Representation theorem for Complete Atomic Heyting Algebras

It is well known that within classical logic one can characterize complete atomic boolean algebras as powersets. Is it possible to provide any characterization/representation theorem for complete ...
16k views

### What is the difference between max and sup?

I am studying KS (Kolmogorov-Sinai) entropy of order q and it can be defined as $$h_q = \sup_P \left(\lim_{m\to\infty}\left(\frac 1 m H_q(m,ε)\right)\right)$$ Why is it defined as supremum over ...
13k views

### Infimum and supremum of the empty set

Let $E$ be an empty set. Then, $\sup(E) = -\infty$ and $\inf(E)=+\infty$. I thought it is only meaningful to talk about $\inf(E)$ and $\sup(E)$ if $E$ is non-empty and bounded? Thank you.
527 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 ?
704 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. ...
668 views

### What is the order-type of the set of natural numbers, when written in alphabetical order?

We are all familiar with the standard nomenclature for the smallish natural numbers, such as one, two, three, ..., one hundred, one hundred one, ..., fifteen thousand two hundred forty-nine. I ...
365 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 ...
3k views

### Show that it is impossible to list the rational numbers in increasing order

This is problem #6 from Section 1.2 of Ash's Real Variables With Basic Metric Space Topology. I am asked to show that it is impossible to list the rational numbers in increasing order. While I ...
1k views

### Is there an example of an ordered ring that is not isomorphic to any subring of the real numbers?

Somebody told me it's possible to show the existence of rings non-isomorphic to any subring of the real numbers using model theory, but they couldn't get an example.
605 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 ...
1k 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 ...
414 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]$, then ...
198 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 ...
3k 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 ...
Must a sequence be well-founded? Is $\Bbb Z=(\ldots-1,0,1,2,\ldots)$ a sequence? Conventionally we think of $\Bbb N=(0,1,2,3,\ldots)$ as a sequence, but what about if it has no starting value? ...