Questions tagged [order-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
587 views

Braided lobsters

If $(X,m)$ is a median algebra, then for each $x\in X$, define an operation $\wedge_{x}$ by letting $y\wedge_{x}z=m(x,y,z)$. Then $(X,\wedge_{x})$ is a meet-semilattice with least element $x$. Define ...
Joseph Van Name's user avatar
1 vote
0 answers
101 views

A question about pdfs with likelihood ratio order

Suppose $f_1,f_2,\dots$ are pdfs of absolutely continuous random variables with the same support (say an interval). Assume that $\{f_i\}$ are strictly positive in their support. Furthermore, $\frac{...
Ozzy's user avatar
  • 383
1 vote
1 answer
190 views

Self-embeddings of uncountable total orders

A nice theorem of Dushnik and Miller (from 1940) states that if $(\Omega,\leq)$ is a countable total order, then either there is an element $\omega \in \Omega$ such that $(\Omega \setminus \{\omega\}...
THC's user avatar
  • 4,313
5 votes
1 answer
239 views

Infinitely many initial ideals for non-Artinian monomial orders?

Consider the polynomial ring $R=\mathbb Z[x_1,\ldots,x_n]$ and an ideal $I\subset R$. Let $<$ be a monomial order, i.e. a total order on the set of monomials in $R$ such that for any monomials $a$, ...
Igor Makhlin's user avatar
  • 3,493
2 votes
2 answers
907 views

Is the intersection of Boolean sublattices a Boolean sublattice?

Let $L$ be a boolean lattice, $A$ and $B$ sublattices of $L$ that are themselves boolean lattices, and suppose that $I = A \cap B$ is nonempty. Is $I$ a boolean sublattice of $L$? Is it a ...
Jon Doyle's user avatar
2 votes
2 answers
428 views

(Types of) induction on infinite chains

This question may be trivial, or overly optimistic. I do not know (but I guess the latter...). I am a group theorist by trade, and the set-up I describe cropped up in something I want to prove. So ...
NotDominicRaab's user avatar
1 vote
1 answer
291 views

Countable union of well ordered sets [closed]

Assume I have a sequence $(A_i)_{i<\omega}$ of well-ordered subsets of an ordered set $S$. Assume that $A:=\underset{i<\omega}{\cup}A_i$ is also well-ordered. Let $\alpha$ be an ordinal upper ...
user avatar
4 votes
1 answer
764 views

Is this lemma equivalent to the axiom of choice?

Given any pre-ordering $\preceq$ of an arbitrary set $X$ is the following lemma: $$\text{There exists an inclusion minimal set }S\text{ satisfying }\{a\preceq b:b\in S\}=X\\\iff \text{ Every chain in ...
Ethan Splaver's user avatar
1 vote
0 answers
96 views

Generalization of the linear extension theorem to directed acyclic graphs

Using Zorn's lemma one can prove a generalization of the order extension theorem, that states any acyclic digraph is always contained in another acyclic unilaterally connected digraph on the same ...
Ethan Splaver's user avatar
0 votes
1 answer
51 views

Minimizing the set of "faulty" edges in a map between the vertex sets of $2$ graphs

The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$. ...
Dominic van der Zypen's user avatar
2 votes
1 answer
197 views

Basis or subbasis for Scott topology

Let $X$ be a partially ordered set. A subset $S\subseteq X$ is called Scott-open if and only if it is: Upward-closed: $x\in S$ and $x\le y$ implies $y\in S$; Inaccessible by directed suprema: if $D\...
geodude's user avatar
  • 2,129
2 votes
1 answer
129 views

Is the Scott topology generated by the ideals as the closed sets?

Let $X$ be a directed-complete partial order, or even a complete lattice. A subset $S\subseteq X$ is called Scott-closed if and only if it is: Downward-closed: $y\in S$ and $x\le y$ implies $x\in S$; ...
geodude's user avatar
  • 2,129
34 votes
11 answers
3k views

Open questions about posets

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
6 votes
2 answers
890 views

Poset dimension and width (Dilworth's theorem)

For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \...
Otto's user avatar
  • 1,006
2 votes
1 answer
230 views

Fixed point property and interval topology

Given a poset $(P,\leq)$ the interval topology $\tau_i(P)$ on $P$ is generated by $$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$ where $\downarrow x = \{y\in P: y\leq ...
Dominic van der Zypen's user avatar
8 votes
1 answer
313 views

A strictly decreasing function between uncountable subsets of the reals

By a standard technique of inductive killing everything relevant (in this case decreasing homeomorphisms between uncountable $G_\delta$-subsets of the real line) it is possible to prove the following ...
Taras Banakh's user avatar
  • 40.7k
2 votes
2 answers
182 views

Infima and suprema in the "transfer" function ordering

Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...
Dominic van der Zypen's user avatar
17 votes
1 answer
1k views

How is this fixed point theorem related to the axiom of choice?

I'm hoping the answer to this is well-known. Let $X$ be an ordered set (i.e. poset). An inflationary operator $f$ on $X$ is a function $f: X \to X$, not necessarily order-preserving, such that $f(x) \...
Tom Leinster's user avatar
  • 27.2k
2 votes
1 answer
144 views

Generating totally ordered free commutative monoids

Let’s say I have a set $A$. I build the free commutative monoid $M$ generated by $A$. When can a well-order on $A$ be extended to $M$, in a way that is compatible with its monoid structure? I am ...
Tartrate's user avatar
  • 341
1 vote
1 answer
71 views

What do you call this relation between pre-orders?

Let $\sqsubseteq_1,\sqsubseteq_2$ be two pre-orders. Say that $\sqsubseteq_2$ perfects $\sqsubseteq_1$ if: $a \sqsubset_1 b$ implies $a \sqsubset_2 b$, and if $a$ and $b$ are incomparable according ...
Marco's user avatar
  • 141
3 votes
1 answer
320 views

Triangular conjecture (that implies the Frankl conjecture)

Let $M$ be a $n\times n$ triangular matrix, that entries are $0$ and $1$ , and such that diagonal entries are $1$. A row or a column will be said to be small, if its number of $1$s is at most $(n+1)/...
jcdornano's user avatar
  • 469
4 votes
2 answers
331 views

The cofinality of the poset $[\kappa]^{<\kappa}$ for a singular cardinal $\kappa$

For a cardinal $\kappa$ let $[\kappa]^{<\kappa}$ denote the family of subsets of cardinality $<\kappa$ in $\kappa$. The family $[\kappa]^{<\kappa}$ is endowed with the partial order of ...
Taras Banakh's user avatar
  • 40.7k
0 votes
0 answers
89 views

Functoriality of indiscernible sequences

Let $T$ be a first order theory of, say, some type of combinatorial geometries which contain indiscernible sequences of points. Let $(\Gamma,\mathcal{O})$ be a model of $T$, where $\Gamma$ is the ...
THC's user avatar
  • 4,313
2 votes
2 answers
276 views

About the existence of a particular kind of "splitting" function on atomless complete Boolean algebras

Let $\mathbb{B} = \langle B, \wedge, \vee, \leq, \neg, 0, 1 \rangle$ be an atomless complete Boolean algebra. We call $f$ a splitting function on $\mathbb{B}$ iff $f : B-\{1\} \longrightarrow B \...
Zoorado's user avatar
  • 1,215
7 votes
2 answers
342 views

Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$

Let $X$ be a set, and let $\text{Part}(X)$ denote the collection of all partitions of $X$. For $A, B\in \text{Part}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ ...
Dominic van der Zypen's user avatar
4 votes
1 answer
210 views

Embedding ordinals with the order topology into connected $T_2$-spaces

Is there a limit ordinal $\kappa_0$ with $\kappa_0 \lt 2^{\aleph_0}$ and such that for every limit ordinal $\lambda$ with $\kappa_0\leq \lambda\lt 2^{\aleph_0}$ there is a connected $T_2$-space $X_\...
Dominic van der Zypen's user avatar
1 vote
2 answers
214 views

Can the Boolean Algebra of regular open sets be isomorphic to ${\cal P}(\omega)/(\text{fin})$?

Let $(X,\tau)$ be a topological space. $A\subseteq X$ is said to be regular open if $A = \text{int}(\text{cl}(A))$ and let $\text{RO}(X,\tau)$ denote the collection of regular open sets of $X$. A ...
Dominic van der Zypen's user avatar
5 votes
0 answers
140 views

Self-additive posets

We say that a partially ordered set $(P,<)$ is self-additive if the two natural embeddings of $P$ in $P\oplus P$ (the linear sum of $P$ and itself) are elementary. We have the following. ...
tomasz's user avatar
  • 1,184
-5 votes
1 answer
305 views

Borromean rings, Condorcet's paradox and Quantum chromodynamics [closed]

In https://plus.google.com/108432079989441783124/posts/LHewqvcj5Xo T. Abderrahman explains what Borromean rings are. As I noticed in a comment, the underlying order structure is the same as in ...
Sylvain JULIEN's user avatar
4 votes
3 answers
391 views

Problem understanding a passage of the proof of $\mathfrak{p}=\mathfrak{t}$ involving forcing

I've a problem with a passage of the proof of Claim 14.7 of the paper "Cofinality spectrum theorems in model theory, set theory, and general topolgy" by Malliaris and Shelah, or equivalently ...
Cla's user avatar
  • 685
12 votes
1 answer
439 views

Is each cover of the plane by lines minimizable?

A cover $\mathcal C$ of a set $X$ by subsets of $X$ is called $\bullet$ minimal if for every $C\in\mathcal C$ the family $\mathcal C\setminus\{C\}$ is not a cover of $X$; $\bullet$ minimizable if $\...
Taras Banakh's user avatar
  • 40.7k
0 votes
1 answer
131 views

Upward generators of $[\omega]^\omega$

If $(P,\leq)$ is a poset and $S\subseteq P$ we let $$\uparrow S = \{p\in P: p\geq s\text{ for some }s\in S\}.$$ Let $([\omega]^\omega,\subseteq)$ denote the collection of infinite subsets of $\omega$,...
Dominic van der Zypen's user avatar
2 votes
1 answer
130 views

Topologically Ordered Families of Disjoint Cantor Sets in $I$?

Suppose that we have an uncountable collection $C_\alpha$ of disjoint Cantor Sets contained in the closed unit interval $I$. Suppose we have ordered the indices $\alpha \in [0,1]$ as well. Then is ...
John Samples's user avatar
0 votes
1 answer
291 views

root of identity matrix and lexicographic order

I asked a question here order of a permutation and lexicographic order but it seems*** that a very powerful and rich generalization can be made! Let $A$ be a finite ring together with an arbitrary ...
jcdornano's user avatar
  • 469
1 vote
1 answer
178 views

order of a permutation and lexicographic order

Let $M$ be an $n\times m$ matrix, say with entries in $\left\{0,1\right\}$ ; and let $\mathcal C(M)$ be the $n\times m$ matrix such that there exists $P$, $m\times m$ permutation matrix such that $...
jcdornano's user avatar
  • 469
2 votes
1 answer
100 views

Is a simple graph matrix the sum of a "shiftordered" matrix and its transposed matrix

This is the generalization of a question Is a simple graph the "sum" of a partial order and its dual? Nik Weaver found a counterexample in a very nice, complete (and instantaneous!) answer,...
jcdornano's user avatar
  • 469
4 votes
3 answers
380 views

Is a simple graph the "sum" of a partial order and its dual?

A "$n$-order matrix" $T\in M_n(\mathbb F_2)$ is a matrix such that there exists a partial ordered relation $\leq_T\subset [1,n]^2$ such that : $T_{ij}=1\Leftrightarrow i\leq_T j$ (where $T_{ij}$ is ...
jcdornano's user avatar
  • 469
5 votes
1 answer
262 views

Order convergence vs topological convergence in partially ordered sets

Short version of the question. If $(P,\leq)$ is a partially ordered set (poset), a topology denoted by $\tau_o(P)$ can be defined (see below). There is also another notion of convergence, called order-...
Dominic van der Zypen's user avatar
5 votes
0 answers
162 views

(When) is the Dedekind-MacNeille completion of a po-set Hausdorff?

Let $X$ be a p.o. Consider the topology on $X$ generated by $$U_{x}^{-}:=X\setminus (x\uparrow),\quad U_{x}^{+}:=X\setminus (x\downarrow), \quad x\in X$$ Throughout this discussion I shall refer to ...
Thomas's user avatar
  • 263
0 votes
1 answer
247 views

Ordered group acting freely on partially ordered set

Let $(G, <)$ be a totally ordered group, and let $<$ be left-invariant. Let $G$ act (freely?) on a partially ordered set $(S, <)$, such that this group action preserves the ordering: $$ s_1 &...
lunchmeat's user avatar
4 votes
1 answer
116 views

Antisymmetry of the stochastic order

An ordered topological space is a topological space $X$ equipped with a partial order $\leq$ which is closed as a subset of $X\times X$. By antisymmetry of $\leq$, it follows that the diagonal of $X$ ...
Tobias Fritz's user avatar
  • 5,775
6 votes
0 answers
115 views

Closedness of the partial order in complete Hausdorff semitopological semilattices

First some definitions. A semilattice is a commutative semigroup consisting of idempotents (i.e., elements such that $xx=x$). A typical example of a semilattice is the unit interval endowed with the ...
Taras Banakh's user avatar
  • 40.7k
11 votes
2 answers
663 views

On Applications of Forcing in Domain Theory

An interesting feature of domain theory is to use partial orders in order to provide a mathematical model for the computational approximation in a potentially infinite computational process (e.g. ...
Morteza Azad's user avatar
0 votes
1 answer
64 views

Complements in $\text{Sub}(\text{Sym}(\omega))$

For any group $G$, we let $\text{Sub}(G)$ be the complete lattice of subgroups of $G$. Let $\text{Sym}(\omega)$ be the group of all bijections $f:\omega\to\omega$. What is an element of $U\in\text{...
Dominic van der Zypen's user avatar
0 votes
1 answer
192 views

$\text{Max}\big(\text{Sub}(\text{Sym}(\omega))\setminus \{\text{Sym}(\omega)\}\big)$

If $G$ is any group, then by $\text{Sub}(G)$ we denote the collection of all subgroups, ordered by $\subseteq$. If $(P,\leq)$ is a partially ordered set we let $\text{Max}(P)$ and the set of maximal ...
Dominic van der Zypen's user avatar
14 votes
1 answer
1k views

Characterizing $\mathbf{R}$ as an ordered group

A standard characterization of $\mathbf{R}$ uses the order and the field structure: any linearly ordered field that is archimedean and complete is isomorphic to $(\mathbf{R}, +, \times, <)$ as an ...
coudy's user avatar
  • 18.5k
1 vote
0 answers
53 views

getting one tower from two (stronger hypothesis than a previous question with same title)

Suppose that $(L,\leq_L,0,1)$ is a Boolean algebra that is dense as an order (i.e. if $a<_L b\in L$ then there exists $x\in L$, s.t. $a<_L x<_L b$) s.t all non trivial closed segments are ...
jcdornano's user avatar
  • 469
3 votes
1 answer
215 views

Fractional ideals of maximal orders in quaternion algebras

Let D be a skew field that is central and finite-dimensional over a number field F (in particular: a quaternion algebra over F). Let $\Delta$ $\subseteq$ D be a maximal $\mathcal{O}$$_{F}$-order. Let $...
jgerrit's user avatar
  • 31
0 votes
0 answers
272 views

Interval order(s) and the empty interval

I am working with the set of half-closed intervals (lower-bound is closed, upper-bound is open) and gleefully defined two interval order: the $≤$ partial order and the $<$ strict partial order. ...
Nonyme's user avatar
  • 101
1 vote
0 answers
38 views

Orderings derived from function sets (Marshall and Olkin book): looking for literature

I am looking into the book "Inequalities: Theory of Majorization and Its Applications, second ed. " of Marshall and Olkin. In chapter 14 (Ordering Extending Majorization, section E) the definition of ...
Fabio's user avatar
  • 329

1
3 4
5
6 7
13