Questions tagged [order-theory]
The order-theory tag has no usage guidance.
644
questions
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 ...
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{...
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\}...
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$, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$.
...
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\...
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$;
...
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 = \...
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 ...
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 ...
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 ...
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) \...
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 ...
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 ...
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)/...
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 ...
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 ...
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 \...
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$ ...
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_\...
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 ...
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.
...
-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 ...
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 ...
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 $\...
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$,...
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 ...
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 ...
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 $...
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,...
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 ...
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-...
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 ...
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 &...
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$ ...
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 ...
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. ...
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{...
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 ...
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 ...
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 ...
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 $...
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.
...
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 ...