Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [order-theory]

The tag has no usage guidance.

2
votes
2answers
121 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 ...
16
votes
1answer
511 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) ...
1
vote
0answers
41 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
1answer
61 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 ...
2
votes
1answer
192 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 numer of $1$ is at most $(n+1)/2$. ...
4
votes
2answers
190 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
0answers
74 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
2answers
249 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 \...
8
votes
2answers
274 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$ ...
0
votes
0answers
61 views

Standard terminology for morphisms of binary relations

Dealing with relations in a set theoretic context, i.e. as just sets of ordered pairs what would one call a function $f:\text{fld}(R)\to\text{fld}(L)$ for any relations $R$ and $L$ in each of these ...
4
votes
1answer
156 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
2answers
80 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
0answers
117 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. ...
-4
votes
1answer
204 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
2answers
272 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
1answer
380 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
1answer
114 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
1answer
117 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
1answer
173 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
1answer
129 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
1answer
77 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
3answers
335 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 ...
4
votes
1answer
127 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-...
3
votes
0answers
66 views

Embedding finite partially ordered sets into antisymmetric monoids

I am wondering if there is an easy answer to the following question: Let us consider a finite partially ordered set $P$. It is clear that there exists a $k$ such that there is an order embedding $P\...
3
votes
0answers
52 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
1answer
103 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 &...
3
votes
1answer
75 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$ ...
3
votes
0answers
29 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 ...
9
votes
2answers
520 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
1answer
51 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
0answers
40 views

A weaker locally convex topology on a pospace

A pospace is a topological space $X$ endowed with a closed partial order $\le$. A pospace $X$ is locally convex if it has a base of the topology consisting of open order-convex sets. A subset $A$ of a ...
0
votes
1answer
171 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 ...
1
vote
0answers
46 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 ...
0
votes
0answers
23 views

Computing the inverse of a full lattice in a quaternion algebra

Let D be quaternion algebra over a number field F. Let $\Delta$ $\subseteq$ D be a maximal $\mathcal{O}$$_{F}$-order. Let $\mathfrak{b}$ be a fractional left $\Delta$-ideal. In his book "Maximal ...
1
vote
0answers
26 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
0answers
84 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
0answers
35 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 ...
8
votes
2answers
187 views

Spaces without maximal homogeneous subspaces

A homogeneous space $(X,\tau)$ is a topological space such that for all $x,y\in X$ there is a homeomorphism $\varphi:X\to X$ such that $\varphi(x)=y$. As a previous question implies, the union of an ...
2
votes
1answer
332 views

getting one tower from two

Suppose that $(L,\leq_L,0,1)$ is a distributive and complemented Lattice 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$) Suppose that there ...
1
vote
0answers
102 views

reflexive relations that are “tridiagonally cycle-indexed” (or “almost ordered” matrices/relations)

Let's take $M$ be a $n\times n$ matrix whose entries are $0$ or $1$. (then we can call it the characteristic matrix of any relation $R_M\subset \left\{a_1,...,a_n\right\}^2$, such that $M_{ij}=1$ iff ...
2
votes
1answer
94 views

Boolean completion of a partially ordered set

Given a poset $(P, \leq)$, is there a complete Boolean lattice $B$ and an order-preserving map $i_P: P\to B$ such that for any complete Boolean lattice $B'$ and order-preserving map $f: P\to B'$ ...
4
votes
1answer
97 views

Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants

In their paper "Theories with recursive models" [1] Lerman and Schmerl used a version of Kruskal's tree theorem about finite n-augmented trees. An n-augmented tree is a tree T together with $n$ unary ...
2
votes
2answers
88 views

Terminology: product on strict preorders corresponding to direct product of preorders?

I’ve had trouble finding a well-established term for the following very obvious and elementary construction on strict partial orders (i.e. transitive, irreflexive relations): Given two strict partial ...
2
votes
0answers
139 views

Galois action on posets of number fields and $p$-adic fields

In the theory of group actions on posets one studies the action of a group $G$ on a poset $\mathcal{P}$ (via order-preserving permutations) partly through its derived action on the order complex of ...
3
votes
2answers
90 views

In the context of directed graphs is it standard notation to allow an element of an independent vertex set to be contained in a loop?

Given any relation $R$, that is, any set of ordered pairs, we can associate a unique digraph $D$ to our relation $R$ by setting $D=(\text{fld}(R),R)$ where $\text{fld}(R)=\text{dom}(R)\cup\text{rng}(R)...
4
votes
2answers
92 views

Order-embedding, but no lattice embedding between distributive lattices

Let $L$ be the power set lattice ${\cal P}(\{0,1,2\})$. It is clear that there is an order-preserving injective map from $M_3$ into $L$, but no injective lattice homomorphism (because $L$ is ...
9
votes
3answers
352 views

Does the lattice of all topologies embed into the lattice of $T_1$-topologies?

Let $\kappa$ be an infinite cardinal, and let $\text{Top}(\kappa)$ be the lattice of all topologies on $\kappa$, ordered by $\subseteq$. Let $\text{Top}^{T_1}(\kappa)$ be the lattice of all $T_1$-...
5
votes
2answers
190 views

A “strong” Galois-Tukey connection between orders with suborders

(Background, may be skipped by the knowledgeable reader: A Galois-Tukey connection between two partial orders $(P,\le)$ and $(Q,\le)$ is a pair of maps $\varphi^+:P\to Q$ and $\varphi^-:Q\to P$ ...
1
vote
0answers
99 views

Ordinal corresponding to well-quasi-order on graphs

Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order. In terms of $K$, what is the maximal order ...
8
votes
0answers
201 views

Is there a 'local' version of Near Coherence of Filters?

The axiom Near Coherence of Filters (NCF) is known to be independent of ZFC. Axiom (NCF I): For any two free ultrafilters $\mathcal D$ and $\mathcal E$ on $\mathbb N$, there exist finite-to-one ...