# Questions tagged [order-theory]

The tag has no usage guidance.

622 questions
Filter by
Sorted by
Tagged with
322 views

### Generalization of the concept of a measure

Consider the following generalization of the concept of a measure: Let $L = (X, \lor, \land, \bot)$ be a semi-bounded lattice. Let $M = (Y, \bullet, e)$ be a commutative monoid. An $(L, M)$-measure is ...
• 1,721
157 views

### Find an order-embedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$

A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$. We partially order the Cartesian ...
• 1,198
425 views

### Progress on determining which partial orders embed into the rationals

The following result is relatively well-known: (for example in Math StackExchange answer #37161) For every countable linear order $(R,\prec)$, there is an $X\subseteq\mathbb Q$ such that $(R,\prec)$ ...
• 804
340 views

### Universal poset for cardinals $\kappa \geq \aleph_0$

Given a cardinal $\kappa\geq \aleph_0$, is there a poset $(P,\leq)$ with $|P| = \kappa$ such that every poset of cardinality $\kappa$ can be order-embedded into $(P,\leq)$?
1 vote
86 views

### Choosing a net of projections from a given collection

Let $\mathcal M$ be a von Neumann algebra. Let $S$ be a nonempty set. Consider $\Omega$ to be the collection of all finite subsets of $S$. Suppose for all $\omega\in\Omega$ we have $I_\omega$ a ...
193 views

### "Minimal" connected matroids

I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...
• 3,370
177 views

Let $L$ be a finite (upper) semimodular lattice. Recall that this means $L$ is graded and its rank function $\rho\colon L \to \mathbb{N}$ satisfies $$\rho(x) + \rho(y) \geq \rho(x\vee y)+\rho(x \... • 21.2k 2 votes 1 answer 102 views ### Decomposition of weak* convergent nets into positive weak* convergent nets Let F be an order unit Banach space with order unit e and topological dual space F^* ordered by the dual cone. Let E\subset F^* be a closed subspace that separates points of F and such that ... • 61 13 votes 1 answer 235 views ### Can any poset of cardinality \leq 2^{\aleph_0} be embedded in {\cal P}(\omega)/(\text{fin})? We endow {\cal P}(\omega) with an equivalence relation by saying that A\simeq_{\text{fin}} B iff the symmetric difference A\Delta B is finite. The resulting set of equivalence classes is denoted ... 3 votes 2 answers 191 views ### Posets such that the collection of principal down-sets does not have property {\bf B} We say that a hypergraph H=(V,E) has property {\bf B} if there is S\subseteq V such that for all e\in E with |e|>1 we have S\cap e \neq \emptyset \neq e \setminus S. Let (P,\leq) be a ... 2 votes 2 answers 249 views ### Topological characterisations of properties of posets Finite connected partially ordered sets are in bijective correspondence to connected finite topological spaces that satisfy T_0, see for example the Wikipedia article Finite topological space. Here ... • 24.9k 4 votes 1 answer 249 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 ... • 63 0 votes 0 answers 29 views ### When can we separate two pairs in {\mathbb H}_n, although it is not a lattice? Recall that a lattice is a partially ordered set E for which any pair a,b\in E admits a least upper bound and a greatest lower bound. Remark that given four elements a_i,b_j (j=1,2), in order ... • 50.2k 5 votes 0 answers 101 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 82 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 ... 3 votes 0 answers 111 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 ... • 63 1 vote 0 answers 75 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 ... • 4,471 1 vote 1 answer 182 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 62 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 ... • 4,471 2 votes 0 answers 65 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 ... 10 votes 0 answers 235 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 ... • 317 2 votes 0 answers 139 views ### End elementary extension in infinitary logic of some L_\alpha producing a L_\beta Let L_\alpha be some admissible level of the constructible hierarchy and M \supseteq L_\alpha an extension of L_\alpha. I am looking for conditions under which M \simeq L_\beta. It is not ... • 491 6 votes 1 answer 342 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 234 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 90 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 96 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 ... • 123 1 vote 1 answer 72 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 ... • 123 10 votes 1 answer 315 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 ... • 56.6k 2 votes 0 answers 59 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 ... • 4,003 2 votes 0 answers 48 views ### What is known about sublocales defined by regular nuclei? (For basic terminology, which is supposed to be standard anyway, see this other question, which inspired this one.) I am interested in nuclei j\colon L\to L on a frame L which are regular elements ... • 27.8k 3 votes 1 answer 178 views ### Computing the Heyting operation on the frame of nuclei (The following definitions are meant to be standard and are reproduced for completeness of the question.) A frame is a partially ordered set in which every finite subset has a greatest lower bound (“... • 27.8k 11 votes 1 answer 617 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 ... • 17.1k 2 votes 1 answer 150 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 60 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’ \... • 2,734 21 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-... • 313 2 votes 1 answer 73 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 ... • 21 5 votes 2 answers 471 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 = \... • 27.8k 8 votes 1 answer 317 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 ... • 18.1k 6 votes 1 answer 232 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 116 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 ... • 18.1k 4 votes 1 answer 189 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 ... • 1,533 27 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 ... • 103k 6 votes 1 answer 210 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 &... 5 votes 1 answer 158 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 ... • 466 2 votes 1 answer 208 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 ... 0 votes 0 answers 36 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 ... • 363 4 votes 2 answers 174 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 \... 10 votes 0 answers 345 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 89 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):=|\{(...
• 107
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&...