Questions tagged [order-theory]
The order-theory tag has no usage guidance.
645
questions
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 ...