Questions tagged [order-theory]

Order theory deals with properties of orders, usually partial orders or quasi orders but not only those. Questions about properties of orders, general or particular, may fit into this category, as well as questions about properties of subsets and elements of an ordered set. Order theory is not about the order of a group nor the order of an element of a group or other alegbraic structures.

565 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
1answer
111 views

When is an ordered space scattered?

There is a concept of scattered in both order theory and topology. A topological space $X$ is scattered if every nonempty subspace has an isolated point. A linearly ordered set $( X , < )$ is ...
3
votes
0answers
49 views

About elements of a poset

Consider a poset $\mathfrak{A}$. I denote $a\not\asymp b$ iff there is a non-least element $x\in\mathfrak{A}$ such that $x\le a$ and $x\le b$. I denote $\star a = \{ x\in\mathfrak{A} \mid x\not\asymp ...
3
votes
1answer
43 views

On the definition of clone of relations

I am reading A short introduction to clones and I am stuck at this definition ($A$ is a set and $R_A$ the set of finitary relations on $A$) Definition A subset $R\subseteq R_A$ is called a clone of ...
3
votes
0answers
478 views

Subsets of $ \mathbb Q $ of order type $ \omega^{\alpha}$ for each countable ordinal $\alpha $.

My introductory text in Set Theory (Stillwell) includes an exercise (6.3.1) asking for an explicit example of a subset of $ \mathbb Q $ or order type $ \omega^2 $. This seems straight forward enough. ...
3
votes
0answers
168 views

The width of a power set graph and its orientations

Let $G(\mathcal{P}(n),E)$ be the undirected graph for the power set of $[n]$ elements under the inclusion relation (i.e. a poset). The width of this poset - which is defined as the size of the maximum ...
3
votes
1answer
318 views

A total order induce by a partial order

I have the following problem: Let $(A,\leq)$ a poset. Prove that there exist a total order $\leq^ *$ on $A$ such that if we have $a\leq b$ we can conclude $a\leq^*b$. (Hint: Use the Zorn Lemma) I ...
3
votes
0answers
217 views

Profinite completion of a partial order

In Johnstone's Stone Spaces it is proved that the category of profinite partial orders is (equivalent to) the category of ordered Stone spaces (also called Priestley spaces) and that the obvious ...
3
votes
0answers
72 views

(Almost) co-free objects?

another naming question from me, which comes up because I try to use category theory as a compass in developing some (new or not?) order-theoretic notions. According to my book (The Joy of Cats, [...
3
votes
0answers
98 views

Small posets with prescribed number of linear extensions

Given a natural number $n$, I want to construct a (finite) poset $P_n$ such that $P_n$ has exactly $n$ linear extensions. This can always be done, for instance taking $P_n$ to be a chain of length $n-...
3
votes
0answers
49 views

Prove that for every 2 elements in the set F of all functions from N to N, there's an element in F that's bigger than both

let there be $\ F$ the set of all functions from $\ N \rightarrow N$. K is a relation on F, for every f,g$\in$F , (f,g)$\in$K $\leftrightarrow$ for all $\ n\in N$, $\ f(n)\leq g(n)$ Prove that for ...
3
votes
0answers
365 views

Power-set in Hypercube: historical background of indexing each term like Hasse Diagram?

My instructor wants references about the indexation over the hypercube, related question here, he does not believe that I was the first who used it -- [update] thanks to a comment, the name is Hasse ...
3
votes
0answers
31 views

Expect size of $k^{th}$ layer of a POSET

Is this known? What is the expected width of the $k^{th}$ layer (anti-chain layer) of a $d$-dimensional partially ordered set of $n$ elements formed by product of $d$ random liner orders chosen from ...
3
votes
0answers
2k views

Is = (equality) a partial order relation?

We know that a partial order relation is a relation which is reflexive , antisymmetric and transitive. Example: (x,y) belongs to R iff x=y. For A={1,2,3}, we get R= {(1,1), (2,2), (3,3)}. Now R is ...
3
votes
0answers
72 views

How can we define “trivially orthogonal” groups?

In any lattice-ordered group, we say that two elements are orthogonal if their meet is 1. I've been thinking of groups who have only "trivial" orthogonal relations, i.e. $x\perp y\implies x=1$ or $y=1$...
3
votes
0answers
123 views

Are there any texts on order theory that treat it as decategorified category theory?

I read this post on nLab and now I want to learn some order theory. What are good texts that contain the above referenced topics, and are there any that are explicitly about order theory as ...
3
votes
0answers
585 views

Non-isomorphic posets

Is there any formula or counting algorithm for the number of non-isomorphic posets (defined on finite n-element set)? I'm interested how to solve task *5, p.4 in Birkhoff's "Lattice Theory" the book ...
3
votes
1answer
179 views

A generalization of Galois connections

Let $f(x)\ast y \Leftrightarrow x\ast g(y)$ for some binary relation $\ast$ and functions $f$ and $g$. This is a generalization of Galois connections. Are things like this studied before? Note that ...
3
votes
1answer
112 views

Existence of a minimal set of linear order that is equivalent to the given partial order

Let $\{(P, \leq_{\alpha})\}_{\alpha \in A}$ be a set of linear order on set $P$, $(P,R)$ be a partial order on the same set $P$. We say that the former is equivalent to the later, iff: $$\forall a, b ...
3
votes
1answer
75 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
3
votes
2answers
154 views

Is there an alternative definition of finite-coproduct categories?

In order theory, there's two possible definitions of the term unital join-semilattice. A unital join-semilattice is a poset $P$ with a least element $0$, such that for any two $x,y \in P$, there ...
2
votes
0answers
54 views

why is a ring ideal not called a filter

A ring ideal can be characterized by the two rules: $$(a\in I) \wedge (a ~ \textrm{divides} ~ b) \implies b \in I$$ $$ a,b \in I \implies \textrm{gcd}(a,b) \in I$$ (the usual definition states $a,b \...
2
votes
1answer
26 views

Number of chains in a symmetric chain decomposition

I need to show that the number of chains of length $n-2k$ in a symmetric chain decomposition of Boolean Lattice $B_n$ is $\binom{n}{k}-\binom{n}{k-1}$. But I have no idea how to do it. I also have a ...
2
votes
0answers
26 views

How can we show that the $k$th order statistic is measurable?

Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space $(E,\le)$ be a partially ordered set and $\mathcal E$ be a $\sigma$-algebra on $E$ $n\in\mathbb N$ $X_1,\ldots,X_n:\Omega\to E$ be $(\...
2
votes
0answers
47 views

Lattice definition and example

Guys I am struggling to understand the lattice concept: Could you help me with this silly example? Take the collection $\{\emptyset, \{0\}, \{1\}\}$ ordered by inclusion. This is a poset, but not a ...
2
votes
0answers
27 views

Is it possible to have a single axiom that subsumes axioms 8-10 in this list?

Think of a totally ordered set as an “order-theoretic line”. Similarly, cyclic orders are “order-theoretic circles”. I want to find the right axioms for an “order-theoretic plane”. My ultimate goal ...
2
votes
0answers
84 views

Showing equality of 2 suprema in complete lattice

Let $(M,+,0)$ be a naturally ordered commutative monoid (i.e. such that the natural preorder is antisymmetric) such that $(M,\sqsubseteq)$ is a complete lattice. Then $(M,\sum^*)$ is a summation ...
2
votes
0answers
24 views

reference request: writing intervals of totally-ordered sets in a “nice” way

Let $\Omega$ be a totally-ordered set. We need to introduce some symbolism and terminology, which is all very natural and intuitive. If $A$ and $B$ are subsets of $\Omega$ we write $A<B$ whenever ...
2
votes
0answers
37 views

In the set $(\mathbb N^{+})^{\mathbb N}$ we have partially ordered set

In the set $(\mathbb N^{+})^{\mathbb N}$ we have partially ordered set: $$f \le g \Leftrightarrow (\forall n \in \mathbb N) f(n)|g(n).$$ (a) Whether the partially ordered set $\left\langle (\mathbb N^{...
2
votes
0answers
47 views

Are Morphisms of a Category Order Isomorphisms?

Let the objects be all partially ordered sets $(S,\le)$ in a Category $\mathscr{C}$. A morphism $(S,\le) \to (T,\le)$ is a function $f: S \to T$ such that for $x,y \in S, x \le y \implies f(x) \le f(y)...
2
votes
0answers
70 views

Lower bound of $e(P)$, the amount of linear extensions of a poset $P$ of cardinality $n$

I am trying to solve the problem, stated as follows Let $P$ be an $n$-element poset. If $t \in P$ then $\lambda_t= \{ s \in P: s \leq t \}$ Show that $e(P) \geq \frac{n!}{\prod_{t \in P} \lambda_t}$ ...
2
votes
0answers
43 views

Maps $f:X\to X$ with $x \geq f(x$)

In order theory, what do we call maps $$f:X\to X \mbox{ with } \forall x\in X:x \geq f(x)$$ (with or without the demand that it is order preserving)? I'm thinking of contraction or something of the ...
2
votes
0answers
86 views

Let $(P,<)$ and $(Q,\prec)$ be countable, dense, and linearly ordered sets without endpoints. Then $(P,<)$ and $(Q,\prec)$ are order-isomorphic

It takes me much time to come up with this proof. Does it look fine or contain gaps? Let $(P,<)$ and $(Q,\prec)$ be countable, dense, and linearly ordered sets without endpoints. Then $(P,<)$...
2
votes
0answers
37 views

There is equivalence of norms and equivalence of metrics. Is there equivalence of order relations?

Two norms $||·||_1$ and $||·||_2$ over a space $X$ are equivalent iff there exist positive $c, C\in \mathbb{R}$ such that for all $x\in X$ $c||x||_1\leq ||x||_2\leq C||x||_1$. Two metrics $d_1$ and $...
2
votes
0answers
113 views

Suppose that every nonempty subset $X$ bounded from above has a supremum. Then every nonempty subset $Y$ bounded from below has an infimum

Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help! Let $(A,\le)$ be an ordered set whose every nonempty subset $X$ bounded from above has a ...
2
votes
1answer
35 views

Equivalence between conditions for induction on well-ordered sets.

Let $(L, \leq)$ be a well-ordered set, and $S\subseteq L$ an arbitrary subset. If $S$ is closed under the successor function (mapping $x$ to $x+1$) and under least upper bounds, then $S=L$. (...
2
votes
1answer
26 views

sum of a collection of truncated outer measures

An outer measure on a set $X$ is a function $\mu:{\cal P}(X)\to[0,\infty]$ such that $\mu(\emptyset)=0$, $U\subseteq V$ implies $\mu(U)\le \mu(V)$, and $\mu(\bigcup_{n\in \Bbb N}U_n)\le\sum_{n\in\Bbb ...
2
votes
0answers
90 views

What partial orders on tagged partitions generate the Riemann Integral?

Let $[a,b]$ be a closed interval in $\mathbb{R}$, and let $X$ be the set of tagged partitions of $[a,b]$. Now let’s define two partial orders over $X$. Let $P_1\geq_1 P_2$ if $P_1$ is a refinement ...
2
votes
0answers
74 views

An interior/closure Galois connection

In A Primer on Galois Connections, the authors define a Galois connection thus (definition 1, p. 104). Consider posets $\mathcal{P} = \langle P, \leq\rangle$ and $\mathcal{Q} = \langle Q,\...
2
votes
2answers
60 views

A Scott-like continuity between partially-ordered sets

Given two partially ordered sets $P$ and $Q$, a function $f : P → Q$ between them is Scott-continuous if it preserves all directed suprema, i.e. if for every directed subset $D$ of $P$ with supremum ...
2
votes
0answers
96 views

When is there an assignment that respects the natural constraints on a join-semilattice of systems?

This is inspired from the definition of consistency of states in Brassard and Robichaud https://arxiv.org/abs/1710.01380 . We have a family $(H_A)_{A \in {\cal S}}$ of arbitrary sets indexed by a ...
2
votes
0answers
143 views

Sorting on non-additive ratios

We are trying to aggregate and sort records by ratios (CTR = clicks/impressions). For some obscure reasons the technology we are using does not allow us to do this. We can group and sort on additive ...
2
votes
0answers
56 views

Kunen's exercise on antitransitive relations

I am working in an exercise from Professor K. Kunen's 2011 book. Let me write some definitions. Given a relarion $R$, one defines the relation $R^*$ as follows: $$aR^*b \leftrightarrow \exists n\in \...
2
votes
1answer
83 views

Understanding the dual of a partially ordered set

I would like to check my understanding regarding the dual of a partially ordered set $P$. The dual of $(P,\leq)$ is defined to be $(P^*,\geq)$ which satisfies the property $$x\leq_{P} y\...
2
votes
0answers
94 views

Modern theories of ordinals independent of set theory?

I know that in the early stages of set theory, e.g., by Cantor and I think largely until von Neumann's formalization of the notion of "ordinal" within his set theory, ordinals were often treated as ...
2
votes
0answers
43 views

Infimum and supremum And Net

We know that every Partially Ordered Set has to satisfy three conditions : Reflexive Anti-Symmetric Transitive If we have the partially ordered set $S$ with a relation $R$, and $S$ also satisfies ...
2
votes
1answer
127 views

Awodey: confusion about $\omega$-CPO

From P100, http://angg.twu.net/MINICATS/awodey__category_theory.pdf I am a bit confused about a part of the discussion on $\omega$-CPO. To briefly describe the problem, definition goes following $\...
2
votes
0answers
43 views

Symbol For Reversing An Ordered Set?

Is there a symbol for a reversed ordered set? E.g. the symbol which would mean the ordered set: (1, 2, 8, 4, 9, 6) Becomes: ...
2
votes
0answers
41 views

Find a subset of $(\mathbb N,\mid)$ isomorphic to $(\mathcal P (\{1, \dots, n \}), \subseteq)$ as a partially ordered set.

Find a subset of $(\mathbb N,\mid)$ isomorphic to $(\mathcal P (\{1, \dots, n \}), \subseteq)$ as a partially ordered set. I can only think of one isomorphism. Let $S$ be the subset of $\mathbb R$ ...
2
votes
1answer
51 views

Representing a co-Heyting algebra as a lattice of semialgebraic sets in a real algebraic variety

Every co-Heyting algebra can be embedded in the co-Heyting algebra of closed sets in a spectral space. (Co-heyting algebras are the order-theoretic duals of Heyting algebras.) Now I am told the ...
1
vote
0answers
30 views

Finding necessary/sufficient conditions for when a directed graph's geodesic function is unbounded.

Given any directed graph $G=(V,R)$ where $R\subseteq V\times V$ is an arbitrary binary relation, we have under the standard definition of distance in an unweighted digraph that $d_G:V\times V\to \...