# 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.

564 questions
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 ...
308 views

### Order-preserving map of regressive functions on $\omega_1$

This questions has now been published in a journal, see update at the bottom. I posted the following question in March 2014 on MO. It did receive some attention, but the answer there remains ...
117 views

### Infinite palindromes in number of nonisomorphic posets is independent of $\mathsf{ZF}$

The following is an "exercise" in P. Stanley's book "Enumerative Combinatorics": Let $f(n)$ be the number of nonisomorphic $n$-element posets (...) let $\mathcal{P}$ denote the statement that ...
171 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. ...
303 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 $\pm$-...
30 views

### What is the smallest poset with automorphism group $C_n$?

I've recently been interested in finding small finite posets (and thereby finite $T_0$ topologies) with a given automorphism group. I came upon the paper of Barmak and Minian in which they provide an ...
107 views

### Can $(\mathcal P(\mathbb N),\subseteq)$ be partitioned into maximal antichains?

If you look at the set of finite subsets of $\mathbb N$ (side question: Is there a standard notation for that?) partially ordered by the subset relation, you see that it can be partitioned into ...
203 views

### Why is the symbol for the exterior product a meet rather than a join?

I've moved this over to HSM. It seems odd that something that looks so much like a join [see below] would get given "the wrong symbol". It's even worse when you dualise it and get something called (...
104 views

87 views

### Terminology for functions such that $f(x)\ge x$ for all $x$

Is there a common terminology for a real function $f$ such that $$f(x)\ge x$$ for all $x$? same question for the conditions $\forall x,f(x)>x$; $\forall x,f(x)\le x$; $\forall x,f(x)<x$. (I'm ...
179 views

### Order and Metric

Consider the Reals as a totally ordered set via its natural order ( linear continuum ). Such order induces an order topology ( basis is the collection of open-intervals of that order), which ...
78 views

### Classifying the chains of orderable sets' power sets up to isomorphism

Recently, while trying to understand another result, I began to wonder about the following question: Given some orderable set $A,$ what (if anything) can we conclude about the order type or ...
50 views

I need some help for one equality in the following proposition. It was a hint to conclude that $\sup\{f(\cdot):f\in\Phi\}$ is additive. I highlighted it blue. Ultimately I am interested in proving the ...
189 views

### combinatorics: a variant of set covering/subset selection problem?

Given a set $N = \{1, 2, \dotsc,n\}$, let $F \subseteq 2^N$ represent a family of subsets of $N$. Each subset $S \in F$ has a reward $+1$ or $-1$. We seek to select a subset $K \subseteq N$ such that ...
43 views

72 views

### Squares of adjunctions / Galois correspondences

$\newcommand{\Spec}{\operatorname{Spec}} \newcommand{\PS}{\mathcal P} \newcommand{\Idl}{\operatorname{Idl}}$ There are many situations where one encounters a square of things which are related by ...
567 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 ...
184 views

200 views

### The rule of three steps for a cyclically ordered group

Is this rule correct? If yes, is there a better way to prove it? If not, what would be an example that does not satisfy the rule? Theorem. For any element $a$ of a group with a non-linear cyclic ...
70 views

### Minimum number of comparisons sufficient to rank any set of $n$ objects?

Say you're given a set of objects, and you don't know the value of any of the objects, but, given a pair of two objects you are always told which one is bigger. For a set $\{x_1, x_2, \cdots, x_n\}$, ...
261 views

### A construction on boolean lattices is itself a boolean lattice?

Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) boolean lattices (with lattice operations denoted $\sqcup$ and $\sqcap$, bottom element $\bot$ and top element $\top$). I call a boolean funcoid a ...
171 views

### Assume n is an even integer. For an odd integer m, a sequence of m sets S1,…,Sm ⊆ [n] is a graceful chain of length m if…

Assume $n$ is an even integer. For an odd integer $m$, a sequence of $m$ sets $S_1, \dots, S_m \subseteq [n]$ is a graceful chain of length $m$ if: $S_1 \subset S_2 \subset \dots \subset S_m$ For ...
49 views

49 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 ...
364 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 ...
31 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 ...
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 $y=1$...