Questions tagged [order-theory]
The order-theory tag has no summary.
703 questions
3
votes
1
answer
92
views
"countable linear orders" = "free category with pointed endofunctor and $\omega$-shaped colimits"?
It is possible to show that the category of finite linear orders (i.e. the index category used to define augmented semi-simplicial sets) is equivalent to the free category with a pointed endofunctor ...
- 1,785
2
votes
1
answer
118
views
When is a mapping that is both a measure isomorphism mod 0 and an order isomorphism unique mod 0?
Suppose we have two measure spaces, $(\Omega, \mathscr{F}, \mu)$ and $(\Psi, \mathscr{G}, \nu)$, with $\mu(\Omega) = \nu(\Psi) < \infty$, and we consider the set of measure isomorphisms mod 0 ...
- 319
2
votes
0
answers
102
views
A Coxeter group associated to finite dimensional acyclic algebras
Let $A=KQ/I$ be an acyclic quiver algebra with Cartan matrix $U$ and let $n$ be the number of vertices of $Q$.
For example when $A=KP$ is the incidence algebra of a finite poset $P$, then $U$ is just ...
- 28.1k
0
votes
1
answer
177
views
Additively idempotent semirings that are not lattices
I am looking for examples of additively idempotent semirings (which are always join semilattices) that do not have an underlying lattice structure, i.e. either meets do not exist or exist outside the ...
- 1
0
votes
2
answers
88
views
Question on extending submodularity inequalities in lattices
On a lattice $\mathcal{L}$, I have a submodular, monotone, real-valued function $\rho$.
Submodularity means it satisfies the inequality $$\rho(x)+\rho(y)\ge \rho(x\wedge y)+\rho(x\vee y)$$ for all $x, ...
- 1,203
8
votes
1
answer
539
views
Which "specific cases" of order types outside of $M$ could Laver mean? What are examples of undecidable statements in order theory?
Richard Laver finishes his seminal paper "On Fraïssé's order type conjecture", with:
Finally, the question arises as to how the order types outside of $M$ behave
under embeddability. For ...
- 2,086
3
votes
2
answers
138
views
Size of cutsets in ${\cal P}(\omega)$ having infinite and co-infinite members only
A chain ${\cal C}\subseteq {\cal P}(\omega)$ is a set such that for all $A, B\in {\cal C}$ we have $A\subseteq B$ or $B\subseteq A$. Using Zorn's Lemma one can show that every chain is contained in a ...
3
votes
1
answer
151
views
Cardinality of the collection of maximal antichains in ${\cal P}(\omega)$
An antichain in $\mathcal P(\omega)$ is a set $\mathcal A\subseteq \mathcal P(\omega)$ such that for all $A, B\in \mathcal A$ with $A\neq B$ we have $(A\setminus B)\neq \emptyset$ and $(B \setminus A)\...
24
votes
1
answer
2k
views
Is Zorn's Lemma equivalent to the Axiom of Choice for individual sets?
It is well-known that in $\mathsf{ZF}$, the Axiom of Choice and Well-ordering Theorem are equivalent. What is perhaps less well-known is that there is a "local" version of this equivalence.
...
- 1,538
3
votes
1
answer
146
views
Disjoint maximal chain and maximal antichain in ${\cal P}(\omega)$
If $(P,\leq)$ is a partially ordered set, we say that $C\subseteq P$ is a chain if $a\leq b$ or $b\leq a$ for all $a,b\in C$. An antichain is a set $A\subseteq P$ with $a\not \leq b$ and $b\not\leq a$ ...
5
votes
1
answer
224
views
Chromatic number of the antichain hypergraph on $\mathcal P(\omega)$
If $H=(V, E)$ is a hypergraph, the its chromatic number $\chi(H)$ is the smallest non-empty cardinal $\kappa$ such that there is a map $c:V \to \kappa$ such that for every $e\in E$ containing more ...
7
votes
1
answer
375
views
Minimal cutsets containing no maximal antichain
If $(P,\leq)$ is a poset, we say that $C\subseteq P$ is a chain if $a\leq b$ or $b\leq a$ for all $a, b\in C$. Moreover, $A \subseteq P$ is an antichain if $a\not\leq b$ and $b\not\leq a$ whenever $a,...
18
votes
3
answers
823
views
Possible cardinalities of maximal chains in ${\cal P}(\omega)$
Let ${\cal P}(\omega)$ denote the power-set of $\omega$. We order it by set inclusion $\subseteq$ and say that ${\cal C}\subseteq {\cal P}(\omega)$ is a chain if for all $A, B\in {\cal C}$ we have $A\...
12
votes
0
answers
327
views
Is there a best one-variable approximation to commutativity (either from above or below)?
Let $T_R$ be the theory of rings in the language $\{+,\cdot,-,0,1\}$. Let $A$ be the set of one-variable sentences which imply commutativity over $T_R$, and let $B$ be the set of one-variable ...
- 19.4k
2
votes
1
answer
300
views
Is every directed graph the quotient of poset where boundary nodes are identified?
Let $k\in \mathbb{N}_+$, let $\mathcal{P}_k$ denote the set of directed graphs obtained as Hasse diagrams of posets on $k$ vertices, and let $\mathcal{Dir}_k$ denote the set of connected directed ...
- 4,822