Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
1 answer
292 views

Is every finite poset a subset of a finite complemented distributive lattice?

Let $(X,\succeq)$ be a poset. I have the following two questions: Is it true that there exists a finite complemented distributive lattice (a Boolean lattice) $(S, \succeq^*)$ such that $X\subseteq S$ ...
3 votes
0 answers
123 views

A class of Kripke frames which preserves validity

The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame. For $1\leq s\leq n-2$, the frame $\mathcal{C}_n(s)$ denotes the frame which is ...
14 votes
1 answer
582 views

On certain order-automorphisms of the rationals

Consider the rationals $\mathbb{Q}$ with the usual order $\leq$. Now let $A$ be a subset of $\mathbb{Q}$, such that foreseen with the induced order $\leq$, $(A,\leq)$ is a dense linear order. ...
5 votes
0 answers
125 views

Which monomials are "leadable"?

Question: Let $k$ be a field, let $f \in k[t_1,\ldots,t_N]$ be a nonzero polynomial. Which monomials $m_a = t_1^{a_1} \cdots t_N^{a_n}$ appearing in $f$ are leadable in the sense that they are the ...
2 votes
0 answers
90 views

Can this order relation, defined in terms of all topological spaces, be defined in terms of the reals alone?

Let $K$ be the operator monoid under composition of Kuratowski's $14$ set operators generated by topological closure $k$ and complement $c.$ Kuratowski's 1922 paper gives the poset diagram of the ...
1 vote
0 answers
90 views

What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?

The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive ...
9 votes
0 answers
291 views

Mapping graphs to ordinals

Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...
1 vote
1 answer
193 views

does this relation associated with a poset have a name?

Given a partial order $P$ on a set $S$ does the set of ordered pairs $(x,y)$ in $S\times S\setminus P$ such that $P\cup\{(x,y)\}$ is a partial order have a name? (If so then it would apply to all ...
3 votes
0 answers
69 views

What are all the order types of maximal chains of $\Delta^0_2$ sets?

A set of natural numbers is $\Delta^0_2$ if it’s computable from the halting set. Consider the quasi-order/pre-order of all $\Delta_0^2$ sets ordered by $m$-reduction, or equivalently consider the ...
10 votes
0 answers
256 views

Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$?

Let $X$ be a finite set of $n$ ($>1$) elements and $\tau$ be a topology on $X$ having exactly $m$ elements. Can we give any description of $m$ as it relates to $n$? Obviously $2\le m\le 2^n$ and ...
2 votes
0 answers
79 views

Ordered vector space that can be embedded into its bidual

We say that an ordered vector space $(V, \ge)$ (over $\mathbb{R}$) is "bidual embeddable" (I made up this name, not sure whether this concept already exists) if for every $x \in V$, if $x$ ...
6 votes
1 answer
349 views

Is every homogeneous poset a lattice?

A poset $(P,\leq)$ is homogeneous if $P\cong [a,b]$ for all $a,b\in P$ with $a<b$ (where $[a,b] := \{x\in P: a\leq x\leq b\}$). Examples of homogeneous posets include $[0,1]$, $[0,1]\cap \mathbb{Q}$...
4 votes
1 answer
255 views

Is ${\cal P}(\omega)/\text{(fin)}$ a fractal poset?

If $(P,\leq)$ is a partially ordered set and $a,b\in P$ we set $[a,b]:=\{x\in P: a\leq x\leq b\}$. We say that $P$ is fractal if whenever $a,b\in P$ and $[a,b]$ contains more than one element, then $[...
-3 votes
1 answer
96 views

Order-embeddability of ${\frak b}$ and ${\frak d}$ in $\mathbb{R}$ [duplicate]

The starting point of this question is the observation that in ${\sf (ZFC)}$, all ordinals $\alpha < \omega_1$ can be order-embedded in $\mathbb{R}$. Let $\omega^\omega$ denote the set of all ...
1 vote
0 answers
102 views

Causal-net category and poset category

Order is a fundamental mathematical structure. There are two natural ways to represent order structures, by posets and by causal-nets (acyclic directed graph). How can we compare these two ways, and ...
1 vote
1 answer
79 views

Characterization of edge posets

Given an acyclic directed graph $G$, the set $E(G)$ of edges of $G$ equipped with the reachable order $\to$ is called the edge poset of $G$, where for two edges $e_1\to e_2$ means that there is a ...
11 votes
1 answer
345 views

Synthetic differential / conformal geometry of Lorentzian manifolds?

Let $M$ be a sufficiently nice Lorentzian manifold of dimension $\geq 3$. It's known [1] (see also [2]) that the differential and even conformal structure of $M$ is completely encoded in the causal ...
2 votes
0 answers
60 views

Countable highly order-transitive subgroups of $\mathrm{Aut}(\mathbb{Q},\leq)$

Consider $A := \mathrm{Aut}(\mathbb{Q},\leq)$, the group of order-automorphisms of $(\mathbb{Q},\leq)$. Call a subgroup $U$ highly order-transitive if for any two finite ordered sequences $s_1$ and $...
8 votes
3 answers
544 views

closure of separative quotients

Does there exist a partial order, nontrivial for forcing, that is countably closed, but whose separative quotient is not countably closed? Supposing the answer is yes, then is there a partial order, ...
11 votes
1 answer
646 views

Do all toposes satisfy the internal Zorn's lemma?

I came up with this question when trying to give a more detailed answer to a question by Tim Campion in a comment to Ingo Blechschmidt's answer to Examples of statements that are valid in every ...
8 votes
2 answers
1k views

How this set of functions is ordered?

Notation: $k, m, n$ are non-negative integers $f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$ $f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$ $f \prec g$ means ...
2 votes
1 answer
160 views

Non-cofiltered derived limits

As far as I know, the inverse limit and its derived functors can be defined even in case we are dealing with a functor $F: I \to A$ from a category $I$ that is not cofiltered. I would content myself ...
2 votes
0 answers
62 views

Total orders on subsets

Let $X$ be some finite ground set. Let $\prec$ be a total order on the powerset $\mathcal{P}(X)$, such that if $A\prec A’,B\preceq B’$ and $A\cap B= A’ \cap B’ = \emptyset$, then $A \cup B \prec A’ \...
22 votes
1 answer
2k views

Why do we need "canonical" well orders?

(I asked this question on Math.SE earlier but received no response and am therefore moving it here, please note that I realise this question is probably incredibly naïve for the experienced set-...
2 votes
1 answer
77 views

Request for literature recommendations on isotonic mappings

An isotonic mapping is a function between two partially ordered sets that preserves the ordering between the elements. Specifically, given two partially ordered sets $(X,\le)$ and $(Y,\le)$, a ...
1 vote
1 answer
184 views

Lower bound on ratio of extreme order statistics

This question relates to bounds on expectations of order statistics, elaborated upon in the Book by Arnold and Balakrishnan (1989). Let $X_1,\ldots,X_n$ be i.i.d. continuous random variables ...
1 vote
1 answer
134 views

Thinning directed sets ${\frak P}$ of partitions of $\omega$ with no ${\frak P}$-discrete subsets

This question branches from Taras Banakh's recent question on a cardinal characteristic connected to families of partitions that are directed in the ordering of partition refinement. A partition $\...
2 votes
2 answers
335 views

Algorithm to compute certain poset from a given poset.

Hi. Associated with a finite poset $P$, one can consider the poset $S(P)$, whose elements are the intervals of $P$, ordered by inclusion. (See Discrete version of Nullstellensatz? for some motivation ...
5 votes
2 answers
483 views

Do germs of open sets around a point form a frame?

Let $X$ be a topological space and $x \in X$ a point. Let $\Omega$ be the set of open sets (viꝫ. the topology) of $X$, and $\Omega_x$ the set of germs around $x$ of open sets, that is, $\Omega_x = \...
8 votes
1 answer
333 views

Example of trickiness of finite lattice representation problem?

I'm trying to come up with a good explanation for my students of why the finite lattice representation problem is difficult. I've already shown that the "greedy approach" to representing the ...
6 votes
1 answer
245 views

Poset as union of posets of lower cofinality

Let $ \mathbb{P}$ be any directed, well-founded poset of cofinality $ \aleph_{n+1}$, where $n$ is a natural. Can we write it as an increasing union $ \mathbb{P} = \bigcup_{\alpha < \omega_{n+1} } \...
3 votes
0 answers
127 views

Is there an ordered algebra analogue of the HSP theorem?

For an algebraic signature (= set of function symbols) $\Sigma$, say that an ordered $\Sigma$-algebra is a pair $\mathfrak{A}=(\mathcal{A};\le)$ where $\mathcal{A}$ is a $\Sigma$-algebra in the sense ...
2 votes
0 answers
75 views

$\sigma$-fields as closure systems

Let $(\Omega,\mathcal A, P)$ be a probability space and let $\Sigma(\mathcal A) \subset 2^{\mathcal A}$ be the collection of all sub-$\sigma$-fields of $\mathcal A$. Then, $\Sigma(\mathcal A)$ is ...
4 votes
1 answer
196 views

Exactly how much (and how little) can partial ordered sets (classes) embed to the cardinalities

In the paper "Convex Sets of Cardinals", Truss mentioned a result of Jech: If $M$ is a countable transitive model of ZFC, and $(P,<)∈M$ is a poset, then there exists a Cohen extension of ...
2 votes
1 answer
591 views

Complete De Morgan algebra

Recall that an algebra $(A,\sim)$ is a De Morgan algebra if $A$ is a bounded distributive lattice and $\sim$ is a unary operation which satisfies: ${\sim} (x\vee y)={\sim} x\wedge {\sim} y$ and ${\sim\...
5 votes
0 answers
195 views

Weak compactness is to trees as [?] is to lattices?

Let $\kappa$ be an inaccessible cardinal. Recall that $\kappa$ is weakly compact if every tree of height $\kappa$ has either a level of size $\kappa$ or a branch of size $\kappa$. So if $\kappa$ is a ...
6 votes
0 answers
690 views

What is the structure of a space of $\sigma$-algebras?

Let $X$ be a compact metric space, and consider the Banach space $\Omega = C(X,\mathbb R)$ of continuous, real-valued functions on $X$, equipped with the supremum norm. Let $\delta_x \in \Omega^*$ be ...
5 votes
0 answers
615 views

A poset with small "cycles"

(A followup to this recent question.) I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that…): Suppose that $z$ is covered by $x$...
8 votes
1 answer
771 views

A characterization of the poset of filters on a set

For the lattices of all subsets of a given set, an axiomatic characterization is known: A poset is isomorphic to a set of all subsets of some set iff it is a complete atomic boolean algebra. The ...
28 votes
1 answer
6k views

What is the cofinality of the co-infinite subsets of ${\bf N}$?

Let ${\mathcal A}$ be the family of subsets $A$ of the natural numbers ${\mathbf N}$ which are co-infinite (i.e., their complement is infinite). We partially order this family by set inclusion. A ...
33 votes
7 answers
4k views

What's a non-abelian totally ordered group?

Because I have heard the phrase "totally ordered abelian group", I imagine there should be non-abelian ones. By this I mean a group with a total ordering (not to be confused with a well-ordering) ...
6 votes
2 answers
1k views

Embedding a Brouwerian lattice into a Boolean lattice

I have already asked a similar question at https://math.stackexchange.com/questions/470704/can-a-brouwerian-lattice-be-extended-into-a-boolean-algebra but have received no answer. Sorry, I ask a ...
6 votes
1 answer
216 views

Smallest ordinal $\mu$ not embeddable in ${\cal P}(\omega)$

The motivation for this question is the startling fact that there is an order-preserving injective map (embedding) from $\mathbb{R}$ into ${\cal P}(\omega)$. (Think Dedekind cuts.) I am wondering how &...
0 votes
0 answers
205 views

Vector-valued valuations on lattices

There's a fair amount of work on valuations on (modular) lattices, by which I mean functions $v : \mathcal{L} \rightarrow R$ that satisfy the modular expression $$v(x) + v(y) = v(x \wedge y) + v(x \...
2 votes
1 answer
211 views

Measuring how "close" $\alpha\in[0,1]\setminus\mathbb{Q}$ is to being rational

Let $\mathbb{N}_+$ denote the set of positive integers and let $\mathbb{N}_0 = \mathbb{N}_+\cup\{0\}$. Fix $\alpha\in[0,1]\setminus \mathbb{Q}$. For $n\in\mathbb{N}_+$ we let the approximation radius ...
2 votes
1 answer
290 views

Uniqueness of minimal completions of a partially ordered set

The partially ordered set $(Y,\le)$ is called a superspace of the partially ordered set $(X,\le')$ iff $X\subseteq Y$. $\le' \:\:=\: (\le\cap X^2)$. and a completion of $(X,\le')$ if in addition $~~ ...
5 votes
1 answer
161 views

Scott topology: Suprema of sequences are topological limits

I read that, with the Scott topology, suprema of sequences are topological limits (See page 1 of this article). Let $(X, \le)$ be a DCPO, and $D$ be a directed subset of $X$. I can easily see that the ...
7 votes
2 answers
776 views

Counterexample on completely distributive lattices

I would like to see an example of a complete lattice $C$ which is both a frame and a dual-frame, i.e. finite meets distribute over arbitrary joins and finite joins distribute over arbitrary meets (...
4 votes
1 answer
139 views

Existence of more distributive Boolean lattices

Is there a Boolean lattice $(X,\le)$ and a nonempty collection $(a_{ij})_{i\in I,j\in J}\subseteq X$ such that $$\bigvee_{i\in I}\bigwedge_{j\in J}{a_{ij}}\ne \bigwedge_{f:I\to J}\bigvee_{i\in I}a_{if(...
6 votes
1 answer
371 views

Poset of automorphism groups of variants of a structure

Say that two structures $\mathfrak{A},\mathfrak{B}$ in possibly different finite languages are parametrically equivalent - and write "$\mathfrak{A}\approx\mathfrak{B}$" - iff they have the ...

1
2
3 4 5
13