Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
2 answers
489 views

The union of two cuts is a cut?

Every poset $\langle P, \leq \rangle$ has a Dedekind-MacNeille completion, a complete lattice that embeds $\langle P, \leq \rangle$. For $A \subseteq P$, the upset $U(A) = \{p \in P\ |\ \forall a \in ...
1 vote
0 answers
201 views

How many more join-irreducibles can there be in a sub join-semilattice of a finite lattice?

Let $L$ be a finite lattice. Then $L$ is generated by its join-irreducible elements $J(L)$ or alternatively its meet-irreducible elements $M(L)$. If $S \subseteq L$ is a sub join-semilattice then $|M(...
4 votes
1 answer
315 views

Posets (partially ordered sets) in equational logic

I know about equational logic, cf. https://en.wikipedia.org/wiki/Lattice_(order)#As_algebraic_structure, and understood that lattices are expressed equationally, i.e., in terms of equational logic (...
-1 votes
3 answers
680 views

Reference Book for supremum and infimum theorems [closed]

For my work I need many of the very easy and basic properties of suprema and infima. While they are all pretty easy to prove, I would prefer to refer to a standard text book. However I did not find ...
0 votes
0 answers
38 views

Is the set of sub-dcpos a dcpo (directed-complete partial order)?

$\newcommand{\sub}{\mathrm{sub}}$Given a dcpo (directed-complete partial order) $\mathcal{X} = (\le, X)$, consider the set $\mathcal{X}^{\sub}$ of all sub-dcpos of $\mathcal{X}$. Can one define a ...
19 votes
1 answer
1k views

Is the theory of a partial order bi-interpretable with the theory of a pre-order?

A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric. A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
14 votes
5 answers
804 views

Birkhoff's representation theorem vs matroid-geometric lattice correspondence

This question is motivated by the superficial observation that Birkhoff's representation theorem and the cryptomorphism between matroids and geometric lattices are sort of similar. The former says ...
4 votes
2 answers
185 views

Ordinal-universal linear order on $\kappa$ elements

The starting point of this question is the observation that if $\lambda$ is a countable ordinal, then there is an order-embedding $e:\lambda \hookrightarrow \mathbb{Q}$. Given an infinite cardinal $\...
3 votes
1 answer
230 views

Representing a binary relation

Consider a binary relation $R$ over a finite set $X$ of size $n$. Assume $R$ is antisymmetric and connected but not necessarily transitive. In essence, we are modeling an "option x beats option y&...
10 votes
0 answers
361 views

Can one define in ZFC a directed system of embeddings on the class of all linear orders realizing the surreal line as the direct limit?

Consider the surreal line $\langle\newcommand\No{\text{No}}\No,\leq\rangle$, in its order structure only. This is a proper class linear order, which is universal for all set-sized linear orders, as ...
1 vote
1 answer
97 views

The quantity of poset with a given number of pairs of incomparable elements

$\DeclareMathOperator\inc{inc}$Let $|X|=n$ and $\inc(X,\leq)=\{\{x,y\} : \neg (x\leq y)\wedge \neg (y\leq x)\}$, where $(X,\leq)$ is poset (possibly unconnected). Define the function: $$\pi(n,m):=|\{(...
10 votes
2 answers
655 views

Status of Barany's conjecture?

One of Barany's most intriguing conjectures is about the $f$-vectors of convex polytopes. It asks: Let $P$ be a convex $d$-polytope. Is it always true that $f_k \geq \min(f_0, f_{d-1})$? A convex $...
2 votes
0 answers
113 views

Product-decomposition of ${\cal P}(\omega)/\rm{fin}$ [closed]

For $A,B\in {\cal P}(\omega)$ let us say that $A\simeq_{\rm{fin}} B$ if both $A\setminus B$ and $B\setminus A$ are finite. It is easy to see that this establishes an equivalence relation on ${\cal P}(\...
7 votes
2 answers
477 views

Counterexample for Chvatal's conjecture in an infinite set

Let $X \neq \emptyset$ be a set. We say that ${\cal F} \subseteq {\cal P}(X)$ is a down-set if ${\cal F}$ is closed under taking subsets. Whenever $a \in X$, we let ${\cal F}_a = \{ S \in F : a \in S\}...
5 votes
1 answer
248 views

Question about a family of nested countable subsets of $\mathbb{R}$

Let $\mathcal{F}$ denote a family of countable subsets of $\mathbb{R}$, such that for each $U, V\in\mathcal{F}$ we have that $U\subseteq V$, or $V\subseteq U$. Let $(\mathcal{F}, \preceq)$ denote the ...
4 votes
1 answer
103 views

Searching for cofinal subsets of directed sets subject to finite constraints

Let $(P,\leq)$ be a directed set with uncountable cofinality. For every element $p\in P$, we are given a finite set $c_p\subset P\smallsetminus \{p\}$ of "incompatible elements". We say that ...
4 votes
0 answers
173 views

To whom is the classification of atomic, modular finite lattices due?

Here lattice means a poset with meets and joins. A lattice is called atomic if every element is a join of atoms. There are a few different ways to define modular for finite lattices: one is that the ...
3 votes
1 answer
133 views

Ideals of an ordered ring

Suppose $R$ is a strictly ordered (non-commutative) ring, in particular $ab > 0$ for any $a,\, b > 0$, that is also discrete in that there are no elements between $0$ and $1$. Now consider a two-...
1 vote
0 answers
94 views

Reference request: Time and proofs of shared pasts

Is there research about structures for notions of time with distributed systems of information, as with blockchains? I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where $I$, $T$ and $P$ ...
10 votes
4 answers
897 views

Are arbitrary nonempty intersections of principal filters principal?

Suppose $\langle L,\leq\rangle$ is a lattice with join $\sqcup$. Let $F_1$ and $F_2$ be principal filters on $L$. Thus, for $i\in I=\{1,2\}$ there are $x_i\in L$ so that $F_i=\{y\in L:x_i\leq y\}$. In ...
2 votes
0 answers
50 views

Can we decompose an increasing net of functions into two increasing nets with prescribed supports?

Let $K$ be a compact Hausdorff space and let $U,V\subset K$ be open. Let $\left(f_{i}\right)_{i\in I}$ be an increasing net of continuous non-negative functions such that $f_{i}\le 1$ and $f_{i}$ ...
3 votes
0 answers
95 views

Order type of monotone functions on $\Bbb N$ up to affine conjugation

Let's introduce order on non-strictly monotone functions $\Bbb N \to \Bbb N$ such that $f \leq g$ if $f(n) \leq Cg(Cn + C) + C$ and, of course, identify such $f, g$ if $f \leq g \leq f$. (Note absence ...
2 votes
2 answers
243 views

Of what kind of complemented bounded poset are the structures in my quasi-variety?

I feel that my question is very basic, but, somewhat suprisingly, nobody was able to give me an answer so far: Let $\mathbf{M} := \langle \{ 0,1 \}, 0, 1, \leq, \neg \rangle$ be the structure with ...
2 votes
2 answers
221 views

Maximal uncountable 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\...
6 votes
0 answers
148 views

Natural bijection between join- and meet-irreducibles in modular lattices?

A well known property of finite modular lattices is that they have the same number of join-irreducible and meet-irreducible elements. I was wondering if there exists a natural bijection between these ...
8 votes
1 answer
390 views

Smallest relation in complement of partial order that prohibits its extension

Let $P$ be a partial order on a finite set $S$ (assume that every element is related to at least one other element besides itself…this raises a few quick questions: is this implied by the definition ...
5 votes
1 answer
780 views

Height of ordered set

In all "constructive" fixed-point theorems for functions on ordered sets that I am aware of, where the fixed point is obtained as the limit of a stationary increasing transfinite sequence, it is ...
3 votes
1 answer
114 views

When does a clone on a two-element set have almost abelian symmetry groups?

Say that a clone (in the sense of universal algebra) $\mathfrak{C}$ has almost abelian symmetry groups (= aasg) iff for each function $f(x_1,...,x_n)\in\mathfrak{C}$ there is an abelian subgroup $A\...
3 votes
1 answer
122 views

Spectral join in a $C^*$-algebra relative to its enveloping von Neumann algebra

I have a $C^*$-algebra $\mathcal{A}$, and would like to make use of the spectral order $\preceq$ coming from (the self-adjoint part of) its enveloping von Neumann algebra $\mathcal{A}^{**}$. I am most ...
1 vote
2 answers
129 views

Embedding $^\omega\omega$ and $S_\omega$ with lexicographic order into $\mathbb{R}$

Let $^\omega\omega$ be the collection of all functions $f:\omega\to\omega$. We order $^\omega\omega$ lexicographically, that is: For $f\neq g \in \,^\omega\omega$ let $m(f,g):= \min\{n\in\omega:f(n)\...
5 votes
1 answer
99 views

Computable functionals avoiding embeddings of linear orderings

Given a linear order $\mathcal{S}$, let $\mathbb{A}_\mathcal{S}$ be the class of all ordertypes which do not embed $\mathcal{S}$ (= do not have a suborder isomorphic to $\mathcal{S}$). Say that a ...
5 votes
1 answer
213 views

Classification of multiplicative lattices

Question 1:Is there a classification of finite lattices which admit a multiplication making them into a finite multiplicative lattices? (see https://encyclopediaofmath.org/wiki/Multiplicative_lattice ...
10 votes
1 answer
740 views

How can you order a free group?

A left order on a (discrete) group $G$ is a total order on $G$ satisfying $\forall g,h,k \in G: g < h \implies kg < kh$. A right order is defined symmetrically, and a biorder is an order that is ...
15 votes
5 answers
7k views

infinite permutations

This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...
2 votes
0 answers
38 views

Continuous analogue for Szpilrajn Theorem: complete preorder extends a continuous preorder

A corollary of Szpilrahn Theorem states: Any preorder on nonempty $X$ has a complete and transitive extension. I am thinking about the "Szpilrahn Theorem" for continuous preorder on ...
4 votes
0 answers
57 views

Are the countable (rayless) trees with wqo labels wqo?

It has been proved by Corominas that the countable trees with vertex-labels coming from a better-quasi-ordered set are better-quasi-ordered. My question is whether this holds if we replace bqo by wqo ...
0 votes
1 answer
145 views

Partial orders on downward closed sets [closed]

Let $P = (V, \sqsubseteq)$ be a partial order and $\mathfrak{D}(P)$ denote the class of downward-closed subsets of the partial order $P$ (i.e, the class of $A \subseteq V$ such that $y\in A \;\&\; ...
3 votes
1 answer
553 views

Sum of $q$-binomial coefficients

Denote by $ \binom{n}{k}_q = \prod_{i=0}^{k-1} \frac{ q^{n-i} - 1 }{ q^{k-i} - 1 } $, $ k = 0, 1, \ldots, n $, the $ q $-binomial (Gaussian) coefficients. These numbers are symmetric, in the sense ...
2 votes
0 answers
95 views

References discussing the category of ordered commutative rings

Is there a reference anywhere discussing the category of ordered commutative rings? I'm thinking of ordered commutative rings and ring homomorphisms preserving the order, but I would also be ...
7 votes
0 answers
138 views

poset of lattice properties

Is there a good overview of the dependencies between properties that a (finite) lattice poset can have? To give a practical example, I was looking for a property weaker than congruence uniform and ...
16 votes
3 answers
10k views

Proving that a poset is a lattice

I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably ...
1 vote
0 answers
86 views

Connected posets $P\not \cong Q$ such that $\text{Hom}(P,P) \cong \text{Hom}(Q,Q)$

Given posets $A, B$, we denote by $\text{Hom}(A,B)$ the collection of order-preserving functions $f:A\to B$. We put a partial order $\leq_{\text{Hom}(A,B)}$ on $\text{Hom}(A,B)$ by setting $$f \leq_{\...
7 votes
1 answer
713 views

Does ⬦ generate all De Morgan algebras?

(Asked by Nathaniel Hellerstein on the Q&A board at JMM) This question is about De Morgan algebras (see also Wikipedia), which are something like Boolean algebras, but with a different weaker ...
6 votes
2 answers
403 views

Characterising subsets of the reals as ordered spaces

There are concise and elegant characterisations of the real line as a topological space and as an ordered space in the literature. I am interested in the harder case of characterising subsets of the ...
10 votes
1 answer
484 views

is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?

It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively. However, I wonder ...
7 votes
2 answers
407 views

RELU representation of $\max(x,y,z)$

Here is a question that occurred to me while learning about neural networks. For $t\in\mathbb{R}$ put $t_+=\max(0,t)$, so $t_+=t$ if $t\geq 0$ and $t_+=0$ if $t\leq 0$. (This is RELU=rectified linear ...
0 votes
0 answers
128 views

How to estimate sums over arithmetic progressions?

For $x>1$ $$ N(x)=\sum_{0<n<x \\n \equiv 1 \pmod 4\\ n\text{ squarefree}} 1 $$ How to estimate $N(x)$'s order? (Like $N(x) \sim Ax$) Furthermore, for $n=p_1p_2\cdots p_v$, define $\alpha (n)=...
4 votes
1 answer
134 views

Example of a bicontinuous poset which is not jointly bicontinuous?

Recall that a poset $P$ is said to be continuous if, for every $p \in P$, the set $\{q \in P \mid q \ll p \}$ is directed with supremum $p$. Here $q \ll p$ is the "way below" relation (see ...
2 votes
1 answer
212 views

closure operator on a complete lattice arising from adjunction on lattice itself

Define a closure operator on a complete lattice $L$ as a function $f:L \to L$ which is order preserving and idempotent and satisfies $x \leq fx$. Every closure operator arises from an adjunction ...
12 votes
1 answer
778 views

Is it known whether every $\omega$-tree with an infinite antichain has an infinite chain in $\mathsf{ZF}$?

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

1 2
3
4 5
13