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
461 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
170 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
248 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
99 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
101 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
90 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
76 views

Terminology for metric space with “anti-symmetric” distance

I'm interested in spaces that have a two-place function $d$ with non-negative real values, satisfying the following three conditions (for all $x$, $y$, $z$): $d(x, x) = 0$ $d(x, y) + d(y, z) \geq ...
4
votes
0answers
94 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
110 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
18 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
76 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
50 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
62 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
53 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
100 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
82 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

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
84 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
36 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
66 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
51 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
44 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
58 views

Is there a categorial description of the Cantorian sum of posets?

Given two partially ordered sets $P$ and $Q$, we can form the product $P \times Q$ and the coproduct $P \oplus Q,$ and these have their predictable interpretations. However, we can also form what we ...
2
votes
0answers
42 views

Is the class of countable posets well-quasi-ordered by embeddability?

The question is in the title. Here "$P$ embeds into $Q$" means there is a function $f : P\to Q$ such that for all $p,p'\in P$, $p \le_P p'$ if and only if $f(p) \le_Q f(p')$. A well quasi order $W$ ...
2
votes
0answers
57 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
75 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 ...
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
75 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
190 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 ...
2
votes
0answers
94 views

What is a binary relation like whose reflexive transitive closure is a partial order?

Let $R$ be a reflexive binary relation and $R^*$ be its reflexive transitive closure. The question is what is the equivalent condition in terms of $R$ to $R^*$ being a partial order. Intuitively, a ...
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
22 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
63 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
28 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 ...
1
vote
0answers
23 views

Positive domains

I define a positive domain to be a quintuple $(S, +, *, 0, 1)$ where $0$ and $1$ are distinct, $(S, +, 0)$ and $(S, *, 1)$ are commutative monoids, $0$ annihilates $*$, $*$ is distributive over $+$, ...
1
vote
0answers
56 views

How many possible DAGs are there with $n$ vertices

I am have $n$ vertices and trying to enumerate all possible DAGs $\theta$ over $n$. How many DAGs are there? For example when $n=2$, there are 3 possible DAGs and when $n=3$ I tried the following: ...
1
vote
0answers
62 views

Intuition behind prime subgroups

In any lattice ordered group, we say that a convex subgroup $P$ is prime if for any two convex subgroups $X,Y$: $X\cap Y \subseteq P$ implies that $X\subseteq P$ or $Y\subseteq P$. This is analogous ...
1
vote
0answers
38 views

Dimension of proset - the case of $\Delta_X$ and $X^2$

I juse met the defiition of dimension of proset and I found myself stuck on a question (actually I am having various troubles with it, so the one I am asking is only one part of the problem I found). ...
1
vote
0answers
88 views

Why are complete lattice homomorphisms defined that way?

Given a function $f : X \rightarrow Y$ and a set $A \subseteq X$, there's at least two possible ways of interpreting the direct image $f(A),$ as explained here. In the notation of that question, write ...
1
vote
0answers
60 views

Order relation with reversed order definition

I am trying to solve this exercise, but it is kind of confusing to me because the order relation involved "reverses" the standard order. Let $\tau$ a binary relation over $\mathbb N$ defined as ...
1
vote
0answers
53 views

Lexicographical Ordering versus Prioritized versus Pareto Composition

I am not sure if I understood it correctly. Lexicographical ordering is the same as prioritized composition principle (they all use the first order and then use others to break the ties). If that's ...
1
vote
0answers
64 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 ...
1
vote
0answers
33 views

Names of certain morphisms in Pos

Pos is the category of small posets and monotone maps. I call a morphism $f:\mathfrak{A}\rightarrow\mathfrak{B}$ of Pos monovalued iff it maps every atom of $\mathfrak{A}$ either into an atom of ...
1
vote
0answers
67 views

About function inj, surj and something else. Is this exercise resolved correctly?

This is my problem: For every couple of integers $(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ we denote with $r(a,b)$ the remainder of the division between $a$ and $b$. Consider the ...
1
vote
0answers
191 views

How to understand $\limsup$/$\liminf$ of a subset of a complete lattice with a topology

From Wikipedia: Let $Y$ be a partially ordered set which is also a topological space and a complete lattice so that the suprema and infima always exist. For a set $X ⊆ Y$, define $$ ...
0
votes
0answers
10 views

Going down from filters to sets for specific relations

Let $\mathfrak{A}$ be a bounded lattice. I call a $2$-staroid a relation $f\in\mathscr{P}(\mathfrak{A}\times\mathfrak{A})$ such that $i\sqcup j \mathrel{f} b\Leftrightarrow i\mathrel{f} b\vee ...
0
votes
0answers
22 views

Help with Quotient Groups, Order in D4.

What group is D4/ isomorphic? |D4/| = 8/2 = 4 so it can be isomorphic to V or Z4. How can I determine which group is it isomorphic to? I know that V (Klein-4 Group) is noncyclic and abelian and Z4 ...
0
votes
0answers
15 views

Order and Quotient Group Help

How do I find the order of 2+<6> in Z15/<6>? I know that |Z15/<6>| = 3 which is isomorphic to Z3, but I do not know how to find the order of 2 + <6>.
0
votes
0answers
19 views

What is total number of inversions in a permutation that is sorted except at indices that are a multiple of a certain number.

So say we have a permutation of integers that is indexed from 0 to n-1, and it is sorted in ascending order except for indices that are a multiple of a number call it x where x is smaller than all ...