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

10
votes
0answers
506 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
227 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
267 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 ...
5
votes
0answers
41 views

Is there a linear order with this property

I was trying and failing to construct a linear order L each of whose uncountable subsets contains an uncountable well ordered subset but L is not a countable union of well ordered subsets. Is this ...
5
votes
0answers
108 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. ...
5
votes
0answers
112 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 ...
5
votes
0answers
111 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
50 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
40 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
49 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
38 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
27 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
161 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
22 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
107 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
52 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
77 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
84 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
114 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
98 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
41 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
24 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
163 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
46 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
110 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
62 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
98 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
55 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
73 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
67 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
84 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
231 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
29 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 ...
1
vote
0answers
19 views

Why is every monomial order a well-ordering?

Let $R$ be a commutative, unital ring. According to wikipedia, a monomial order is a total order $\leq$ on the space of monomials of a given polynomial ring of $R$ such that If $u\leq v$ and $w$ is ...
1
vote
0answers
26 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
29 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
23 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
29 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
14 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
36 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
14 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
53 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) ...
1
vote
0answers
31 views

A partial order with more properties than would be expected

Consider the relation: $$\langle x_1,x_2\rangle\prec\langle y_1,y_2\rangle\iff x_1,x_2,y_1,y_2\in\Bbb N\wedge x_1y_2<x_2y_1.$$ This is usually used for defining the (positive) fractions $\Bbb ...
1
vote
0answers
85 views

Order Preserving Isomorphism

If abelian group G has an archimedean order then there is an order preserving isomorphism $\phi$ of G onto a subgroup of $\mathbb{R}$. Here we can say that G is archimedean totally ordered abelian ...
1
vote
0answers
27 views

Principal order filters on a POSET

I have another problem, but in this one I have no idea how to start. Let be $(X,\leq)$ a POSET with a first element and gifted with the topology $\{ (a,\rightarrow) : a \in X \}$ (principal order ...
1
vote
0answers
57 views

Why are frames called “frames”?

Definition: A frame $F$ is a suplattice such that for any $x_{i}, y\in F$ (for $i\in I$, $I$ a set), we have $$y\wedge\left(\bigvee_{i\in I}x_i\right)=\bigvee_{i\in I}(y\wedge x_i).$$ Why are ...
1
vote
0answers
27 views

Are all preorders implication relations?

This question is for the people who know what consequence relations are. Just to clarify, a consequence relation C on L is a relation from the powerset of L, to L, that satisfies certain properties. ...