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

11
votes
0answers
514 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 ...
8
votes
0answers
273 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
0answers
236 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 ...
7
votes
0answers
123 views

Reference request - the topology generated by upward and downward closures of antichains.

By definition, the order topology on a totally ordered set $T$ is the coarsest topology such that every subset of $T$ that can be expressed as the upward or downward closure of a singleton is closed. ...
7
votes
0answers
123 views

Monoids with positive and negative elements

By a pointed monoid I mean a monoid $M$ together with an absorbing element $0 \in M$ (i.e. $0x=x0=0$). Equivalently, this is a monoid in the monoidal category $(\mathsf{Set}_*,\wedge)$. By a ...
6
votes
0answers
114 views

Does order isomorphism of linear extensions of two partially ordered sets imply order isomorphism of themselves?

This question was firstly posted on Mathoverflow. Two answers are pretty interesting. The potential counter-example given in the second answer is really interesting, but it is not surely a ...
4
votes
0answers
132 views

Is there a name for those relations that behave a bit like $<$?

Consider a fixed but arbitrary preordered set $X$. Is there a name for those binary relations $R$ on $X$ satisfying the following? They seem to show up a lot. (Note that every such $R$ is necessarily ...
4
votes
0answers
55 views

Self-duality in a lattice

Is there any finite self-dual lattice $(X,\le)$ such that there is not any self-duality $f:X\to X$ such that $f\circ f = 1_X$? Let $f,g:X\to X$ be a self-dualities. Then $f^{-1}\circ g$ is an ...
3
votes
0answers
28 views

For which countable successor ordinals $\alpha$ is the reverse order isomorphic to the ideals of a PID ordered by inclusion?

Let $\alpha$ be a countable successor ordinal and $\alpha^{\mathrm{op}}$ the reverse order. For which $\alpha$ is there a commutative principal ideal ring $R$ such that the ideals of $R$ form a chain ...
3
votes
0answers
41 views

If a linearly ordered set $L$ has the property that every order-preserving injection $L \rightarrow L$ is expansive, is $L$ necessarily well-ordered?

Given a poset $P$, call a function $f : P \rightarrow P$ expansive iff $f(x) \geq x,$ for all $x \in P$. Now suppose a linearly ordered set $L$ has the property that every order-preserving injection ...
3
votes
0answers
53 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
3
votes
0answers
39 views

Divisibilty as relation set on $(\mathbb N \setminus \{0,1\})$

So i have to see if $\prec$ is order relation where two elements $(a,b)$ and $(c,d)$ are in relation $\prec$ if $a|c$ and $2b^{2}+6b\leq2d^{2} + 6 d$. This relation is defined on set $(\mathbb N ...
3
votes
0answers
33 views

(Almost) co-free objects?

another naming question from me, which comes up because I try to use category theory as a compass in developing some (new or not?) order-theoretic notions. According to my book (The Joy of Cats, ...
3
votes
0answers
41 views

Prove that for every 2 elements in the set F of all functions from N to N, there's an element in F that's bigger than both

let there be $\ F$ the set of all functions from $\ N \rightarrow N$. K is a relation on F, for every f,g$\in$F , (f,g)$\in$K $\leftrightarrow$ for all $\ n\in N$, $\ f(n)\leq g(n)$ Prove that for ...
3
votes
0answers
174 views

Power-set in Hypercube: historical background of indexing each term like Hasse Diagram?

My instructor wants references about the indexation over the hypercube, related question here, he does not believe that I was the first who used it -- [update] thanks to a comment, the name is Hasse ...
3
votes
0answers
23 views

Expect size of $k^{th}$ layer of a POSET

Is this known? What is the expected width of the $k^{th}$ layer (anti-chain layer) of a $d$-dimensional partially ordered set of $n$ elements formed by product of $d$ random liner orders chosen from ...
3
votes
0answers
113 views

Every subset of a poset has an inf implies every subset has a sup

P is a partial order with $\leq$, and L and U are the sets of all lower and upper bounds of A I already know that if every nonempty subset with a lower bound has an infimum, then every nonempty ...
3
votes
0answers
53 views

How can we define “trivially orthogonal” groups?

In any lattice-ordered group, we say that two elements are orthogonal if their meet is 1. I've been thinking of groups who have only "trivial" orthogonal relations, i.e. $x\perp y\implies x=1$ or ...
3
votes
0answers
78 views

Are there any texts on order theory that treat it as decategorified category theory?

I read this post on nLab and now I want to learn some order theory. What are good texts that contain the above referenced topics, and are there any that are explicitly about order theory as ...
3
votes
0answers
88 views

Non-isomorphic posets

Is there any formula or counting algorithm for the number of non-isomorphic posets (defined on finite n-element set)? I'm interested how to solve task *5, p.4 in Birkhoff's "Lattice Theory" the book ...
3
votes
0answers
120 views

Infinite set ordered like a “infinite tree”

Obviously I don't need to say that I'm still a newbie, so I'll try to explain my question with some pics too. I have a infinite set $T$ I have a visual idea of how this set is ordered, but I don't ...
3
votes
0answers
103 views

Reference request: Indecomposable representations of posets

Let $I$ be a finite poset. Definition: A representation of $I$ is a functor $I\to\mathrm{Vect}_{\mathbb C}\ $. Equivalently, a representation of $I$ is a module over its incidence algebra $\mathbb C ...
2
votes
0answers
32 views

When do finite linear orders have the same theory in MSO?

Let $\mathfrak A$ and $\mathfrak B$ be finite linears orders and $m<\omega$. Then we have $$\mathfrak A \equiv^m_{FO}\mathfrak B \quad\text{iff}\quad |A|=|B| \,\, \text{or}\,\, |A|,|B|\ge 2^m-1.$$ ...
2
votes
0answers
52 views

The width of a power set graph and its orientations

Let $G(\mathcal{P}(n),E)$ be the undirected graph for the power set of $[n]$ elements under the inclusion relation (i.e. a poset). The width of this poset - which is defined as the size of the maximum ...
2
votes
0answers
25 views

Let $P, Q, R$ be finite posets. Prove that $P^{Q+R} \cong P^Q \times P^R$.

Can someone please verify my proof and offer suggestions for improvement? I feel that my proof might have been a little hand-waving in showing that $\varphi$ is a bijection, and I feel that it is not ...
2
votes
0answers
165 views

Profinite completion of a partial order

In Johnstone's Stone Spaces it is proved that the category of profinite partial orders is (equivalent to) the category of ordered Stone spaces (also called Priestley spaces) and that the obvious ...
2
votes
0answers
52 views

Can the actual scope of “lattice theory” be summarized as “algebraic order theory”?

Lattice and order theory are often mentioned together. So I wonder how lattice theory is "intended" to differ from order theory. Lattice theory became important in the context of universal algebra. ...
2
votes
0answers
118 views

Back-and-Forth Argument vs. “One-Way” Argument

The wikipedia article on the Back and Forth Argument claims at the end: If we iterated only step $(1)$, rather than going back and forth, then in some cases the resulting function from A to B ...
2
votes
0answers
64 views

Cones and partial ordering

A positive cone always induces a partial ordering on a vector space. I wonder if the converse holds, so is every partial ordering in a vector space induced by a positive cone, or in other words, is ...
2
votes
0answers
71 views

Do subhomomorphisms / subfunctors have a standard name, and where can I learn more?

Sorry for all the mistakes in the original! I think they're mostly fixed now. Thank you for your patience. Part 1. If $A$ and $B$ are models in $\mathrm{Pos}$ of an algebraic signature $\sigma$, ...
2
votes
0answers
106 views

Partially ordered set exercise

Hi everyone is my first time working with posets and I'd like to know if the solution of the next exercise is really correct or maybe there is some errors that I cannot see. Thank in advance. ...
2
votes
0answers
58 views

Set Theory - Well Order (Lexiographical combination)

Question: Prove constructively that if $(A_{1},\prec_{1})$ and $(A_{2},\prec_{2})$ are two well-ordered sets then their lexicographical combination $(A_{1} \times A_{2},<_{1,2})$ is also well ...
2
votes
0answers
75 views

Is there a nice characterization of posets induced by trees?

Define that a tree in $X$ is a set of ordinal-indexed sequences with codomain $X$ that is closed under the operations of restricting to an ordinal. (I do not know if this definition is standard.) ...
2
votes
0answers
68 views

“Let A be a set. We are able to quotient all possible well-orders over the set A.” What does this mean?

"Let A be a set. We are able to quotient all possible well-orders over the set A." This was the first line in the set-up of some exercises I have to do (which ask specific questions depending on ...
2
votes
0answers
68 views

Relationships between zero morphisms and least morphisms

Zero morphism $0_{XY}$ is defined by the formulas $a\circ 0_{XY}=b\circ 0_{XY}$ and $0_{XY}\circ c= 0_{XY}\circ d$ for every morphisms $a$, $b$, $c$, $d$ of suitable sources and destinations. I ...
2
votes
0answers
85 views

Ordering of multisets in “Paramodulation based theorem proving”

I'm reading this paper: http://www.lsi.upc.edu/~albert/papers/handbook.ps.gz and I can't understand a part of it. it defines an ordering on multisets (it defines a multiset over $A$ as a function $A ...
2
votes
0answers
238 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
1
vote
0answers
7 views

Exponentiation on order types

How is exponentiation defined on order types? We know that $2^\omega=\omega$. What is $2^{\omega^*}$? Is it $\omega^*$? $\eta$? $\lambda$? I'm guessing $\eta$, but I'm not sure. $\omega$ is the ...
1
vote
0answers
38 views

Universal set for linearly ordered sets of given cardinality

It is easy to see that every infinitely countable linearly ordered set embeds into Q (rational numbers) with its linear order.("Linear order"="total order". All embeddings are assumed to preserve ...
1
vote
0answers
31 views

Partial order of a finite set is an intersection of a finite number of linear orders of this set

I am trying to prove that every partial order of a finite set is an intersection of a finite number of linear orders of this set. Can this be proved using these observations: a partial order has a ...
1
vote
0answers
52 views

Generalized semilattice morphism

Join-semilattice morphism from a join-semilattice $\mathfrak{A}$ to a join-semilattice $\mathfrak{B}$ is a function $\alpha$ conforming to the formula $\alpha(X\sqcup Y) = \alpha X\sqcup\alpha Y$ ...
1
vote
0answers
28 views

Uniqueness of smallest element in poset

Prove that a smallest element, if it exists, is determined uniquely. This is follows directly for definition. An element $a \in X$ is called the smallest element of $(X, \preceq)$ if for every $x \in ...
1
vote
0answers
31 views

Partially ordered sets

I have a question on Posets. Suppose we have $P = \{3, 6, 9, 18, 7, 14\} $ ordered by divisibility. We want to partition $P$ to subsets so that each two elements in each subset are related directly ...
1
vote
0answers
36 views

Subsets of $ \mathbb Q $ of order type $ \omega^{\alpha}$ for each countable ordinal $\alpha $.

My introductory text in Set Theory (Stillwell) includes an exercise (6.3.1) asking for an explicit example of a subset of $ \mathbb Q $ or order type $ \omega^2 $. This seems straight forward enough. ...
1
vote
0answers
33 views

Group of Orientation-preserving Homeomorphisms of the Reals.

Let $h: \mathbb{R}\rightarrow\mathbb{R}$ ; $\mathbb{R}$ Reals be an orientation-preserving homeomorphism. I can see $h$ includes linear maps $h=ax+b$ with $a>0$ . Can we say that every ...
1
vote
0answers
17 views

Stochastic Orders

Does the partial order below (R) has a name? Has anyone seem something somewhat similar or related before? The book Stochastic Orders (my bible for this stuff) has no reference on it. Any references ...
1
vote
0answers
42 views

Total ordering on the free group

The free groups can be totally (bi-)ordered. This paper shows how to do it (page 4). In short, you embed the group in multiplicative structure of the ring of power series in non-commuting variables, ...
1
vote
0answers
15 views

Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
1
vote
0answers
30 views

Prove that $P$ is a lattice (details inside)

Can someone please verify my proof or offer suggestions for improvement? There may be answers to the same questions elsewhere, but I need help with my proof in particular. Show that if $P$ is a ...
1
vote
0answers
61 views

A total order induce by a partial order

I have the following problem: Let $(A,\leq)$ a poset. Prove that there exist a total order $\leq^ *$ on $A$ such that if we have $a\leq b$ we can conclude $a\leq^*b$. (Hint: Use the Zorn Lemma) ...