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.

38
votes
0answers
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 ...
11
votes
0answers
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 ...
8
votes
0answers
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 ...
8
votes
0answers
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. ...
8
votes
0answers
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$-...
7
votes
0answers
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 ...
7
votes
0answers
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 ...
7
votes
0answers
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 (...
7
votes
0answers
104 views

Showing that poset of set of supports of a vector space is semimodular

Let $W$ be a subspace of the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is a field of characteristic $0$. The support of a vector $v = (v_1,\ldots, v_n) \in \mathbb{K}^n$ is given by $\text{supp}(...
6
votes
0answers
274 views

How many total orders consistent with a partial order?

I have a finite set of objects $X$, whose power set is partially ordered by $\subseteq$. Consider all possible total orderings of the power set $\mathscr{P}(X)$ which are compatible with the partial ...
6
votes
0answers
507 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 ...
6
votes
0answers
153 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 counter-...
5
votes
0answers
153 views

Alternative definition of “sheaf”

Let $(X,\tau)$ denote a topological space and $\mathcal{O}$ denote a presheaf on this space with codomain $\mathbf{Set}$. We can take the category of elements of $\mathcal{O}$, which consists of a ...
5
votes
0answers
159 views

The Term “Cofinal”

I was reading about ordered fields $\mathbb{F}$ with countable cofinality which means that there is a countable set $S$ that is cofinal. The definition of $S$ being cofinal is that for all $a \in \...
5
votes
0answers
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 ...
5
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
50 views

supremum of additive functions is additive

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 ...
4
votes
0answers
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 ...
4
votes
0answers
43 views

Prove, that relation $R(G,\preccurlyeq_G) \; (G_1 \preccurlyeq_G G_2: G_1 \text{ is subgraph of } G_2)$ is a Poset

I'm currently studying for my exams and want to know if my proof of the following task is done correctly: Prove, that the relation $R(G,\preccurlyeq_G) \; (G_1 \preccurlyeq_G G_2 \Leftrightarrow ...
4
votes
0answers
32 views

Linear representation of continuous maps with translation-invariant level sets

Let $$\mathbb R_{++}^2\equiv\{(x_1,x_2)\in\mathbb R^2\,|\,x_1>0\text{ and }x_2>0\}$$ be the positive orthant in the Cartesian plane. Suppose that $f:\mathbb R_{++}^2\to\mathbb R$ is a function ...
4
votes
0answers
51 views

Cardinality set of downsets

Let $(X, \leq)$ be a totally ordered set. A downset of $X$ is a subset $A$ of $X$ with the property $$ \forall x \in X \forall a \in A : ( x \leq a \Rightarrow x \in A ) $$ Denote $\mathcal{D}(X)$ for ...
4
votes
0answers
127 views

Generalized ordering on simplicial complex

The vertices of simplicial complexes are usually totally ordered so that face maps of each simplex can be defined easily for the purposes of homology. That gives an "oriented" simplicial complex. But ...
4
votes
0answers
188 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for $y=(y_1,...
4
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
184 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 ...
3
votes
0answers
108 views

About “Principles of Mathematical Analysis” by Walter Rudin Theorem 3.17(a).

I am reading Walter Rudin's "Principles of Mathematical Analysis". There are the following definition and theorem and its proof in this book. Definition 3.16: Let $\{ s_n \}$ be a sequence ...
3
votes
0answers
105 views

Can a partial order have a maximal antichain of maximal cardinality which is disjoint from a maximal chain?

Suppose $(S, \leq)$ is a poset. Let $C$ be a maximal chain in $S$. Suppose that the largest antichain of $S$ is of size $M$. Now consider the poset $(S \setminus C, \leq)$. Is it possible that the ...
3
votes
0answers
60 views

Arcs Contained In Continuous Injections of $[0,1)$

Suppose we have a metric space $X$ and a continuous injection from $[0,1)$ onto $X$. The case I had in mind will satisfy that $X$ is compact, but the problem I have can be stated more generally, as ...
3
votes
0answers
77 views

Partially-ordered and (semi-)lattice-ordered semigroups and monoids

I'm interested in expository material, in the form of books, chapters in books, articles, blogposts, etc., about partially-ordered, and lattice-ordered semigroups and monoids. I have found two ...
3
votes
0answers
130 views

Vector lattice and sublattice

Consider the integer lattice $(\mathbb{Z}^2,\leq)$ with the canonical partially ordered relation $(a,b)\leq(c,d)$ iff $a\leqslant c$ and $b\leqslant d$. Now just consider a partially ordered subset of ...
3
votes
0answers
111 views

Prob. 10 (a, b, c), Sec. 10, in Munkres' TOPOLOGY, 2nd ed: Let $J$ and $C$ be well-ordered sets such that . . .

Here is Prob. 10, Sec. 10, in the book Topology by James R. Munkres, 2nd edition: Theorem. Let $J$ and $C$ be well-ordered sets; assume that there is no surjective function mapping a section of $J$...
3
votes
0answers
29 views

Patterns in defining total orders

In Munkres $\S$3, there are a few boring exercises that involves proving a relation is a total order. To name a few (I changed the strict orders to non-strict ones), Q6: Define a relation on the ...
3
votes
0answers
52 views

Finding subgroups if an element has an order

Question 1: If $a$ has order $12$, find the subgroups $\langle a^{3}\rangle$ and $\langle a^{5}\rangle$. Also is $\langle a^{2}\rangle$ a subgroup of $\langle a^{4}\rangle$ ?Question 1b:If $\langle b^{...
3
votes
0answers
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 ...
3
votes
0answers
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\}$, ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
49 views

About elements of a poset

Consider a poset $\mathfrak{A}$. I denote $a\not\asymp b$ iff there is a non-least element $x\in\mathfrak{A}$ such that $x\le a$ and $x\le b$. I denote $\star a = \{ x\in\mathfrak{A} \mid x\not\asymp ...
3
votes
0answers
476 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. ...
3
votes
0answers
165 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 ...
3
votes
0answers
216 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 ...
3
votes
0answers
71 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
96 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 $n-...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
2k views

Is = (equality) a partial order relation?

We know that a partial order relation is a relation which is reflexive , antisymmetric and transitive. Example: (x,y) belongs to R iff x=y. For A={1,2,3}, we get R= {(1,1), (2,2), (3,3)}. Now R is ...
3
votes
0answers
72 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 $y=1$...