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
485 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 ...
7
votes
0answers
260 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 ...
7
votes
0answers
200 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 ...
5
votes
0answers
107 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
106 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
34 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 ...
4
votes
0answers
39 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 ...
4
votes
0answers
94 views

adjoints and duality

Let $X$ and $Y$ be posets seen as a category. Let $F:X \to Y$ and $G: Y \to X$ be an adjunction. That is, $(G \circ F) (x) \ge_X x$ and $(F \circ G) (y) \le_Y y$. Now, $F$ is additive and $G$ is ...
4
votes
0answers
103 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 ...
3
votes
0answers
39 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
34 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
26 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
134 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
19 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
83 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
51 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
76 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
71 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
56 views

Can all non-archimedean groups be written as a product of archimedean groups?

All the non-archimedean groups I know of can be written as the product of archimedean groups. I'm wondering if this is generally true. I think I've found a proof, but I haven't heard this theorem ...
3
votes
0answers
105 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
92 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
155 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
39 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
94 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
55 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
70 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
68 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
49 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
66 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
82 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
203 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

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
52 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
26 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
46 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
23 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. ...
1
vote
0answers
28 views

Prove/disprove questions on equivalence relations and ordered sets

If $R$ is an equivalence relation and a partial order over $A \neq \emptyset$ then every equivalence class contain at least one element. If $(A,\le)$ an ordered set, and $a\in A$ is a single ...
1
vote
0answers
23 views

Has an order with this property a special name?

If $a$ is an element in a preorder then you can eventually go 'a step back' (and repeat this) in the sense of finding an element with $b\leq a$ and not $a\leq b$. Is there a special name for ...
1
vote
0answers
18 views

Proving isomorphism in lattices

The question is as follows: Let f be a monomorphism from a lattice $L$ to a lattice $M$.Show that $L$ is isomorphic to a sublattice of $M$. My attempt: Since $f$ is a monomorphism from a lattice ...
1
vote
0answers
16 views

Hasse Diagrams - Relations

I have the following question: Draw the Hasse diagram for the following partially-ordered set: The relation $X$ is a subset of $Y$, on the set $\{ \{0\}, \{2\}, \{0,1\}, \{0,2\}, \{2,4\}, ...
1
vote
0answers
17 views

Small posets with prescribed number of linear extensions

Given a natural number $n$, I want to construct a (finite) poset $P_n$ such that $P_n$ has exactly $n$ linear extensions. This can always be done, for instance taking $P_n$ to be a chain of length ...
1
vote
0answers
50 views

How many different proper subfields does $K$ have, where $K$ is a field of order$p^n$?

If $p$ is a prime, and $d$ is an integer greater than or equal to 1. Let $n= p^d$, then there exists $K$ being a field of order $p^n$. But how many different proper subfields does $K$ have? The ...
1
vote
0answers
24 views

Set theory chain proof help!

Let $A_i$ be a partially ordered set and $C_i$ a chain of $A_i$. Order $A_1\times A_2$ lexicographically. Prove that $C_1\times C_2$ is a chain of $A_1\times A_2$. This is a set theory proof ...
1
vote
0answers
17 views

Recommendation for Order Theory texts

Order Theory, Lattice Theory, or any directly relatable subject is not taught at my university, and quick searches don't give much clue into good textbooks for the subjects. My question is: what are ...
1
vote
0answers
29 views

Order-preserving embeddings

(Follow-up to Existence of a utility function on the reals.) Say we have a totally ordered set $X$ which has a countable, dense subset $C$. I believe we can find an $f:C\to\mathbb R$ which is ...
1
vote
0answers
24 views

Does an homeorphism function maps an interval in X to an interval in Y?

Let $(X,\leq_X)$ and $(Y,\leq_Y)$ be two well-ordered sets. Let $f:X\rightarrow Y$ be an homeorphism between $X$ and $Y$ and their order topology (relative to $\leq_X$ and $\leq_Y$). My question is, ...
1
vote
0answers
34 views

The null set as the underlying set of a relation structure

Can the null-set underly a relation structure? Can it underly a well-order? If so, would such a well-order have order-type $0$? (Can one even have an order-type of $0$?) My motivation for this ...
1
vote
0answers
70 views

Does the Riemann zeta function tell us about the order theoretic properties of the natural numbers?

The classical Möbius function $\mu(n)$ fulfills the multiplicative inversion formula, e.g. see this thread. Now I see in the theory of posets, they generalize the concept of that function, see ...
1
vote
0answers
33 views

Monoid Ring of a Commutative Cancellative Ordered Monoid

Suppose $M$ is a commutative cancellative monoid with $0$ as the identity and $+$ as the operation, and $M$ is equipped with an order $\preceq$ defined by $$ m \preceq m' \text{ if and only if there ...