# 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 algebraic structures.

4,223 questions
Filter by
Sorted by
Tagged with
1 vote
90 views

### Partition of $\mathbb R$ in convex subsets/badly ordered sets

Background: These questions come from two different exercises, but since the first is much shorter and of the same kind of one of the others, I preferred to put everything in only one thread. (We work ...
• 231
1 vote
52 views

### A partially ordered set has all suprema iff it has all infima

Let $(P, \leq)$ be a partially ordered set. We will show that every nonempty set bounded above in $P$ has a supremum iff every nonempty set bounded below in $P$ has an infimum. Obviously, it suffices ...
• 904
77 views
+50

### Partial order where only some elements are reflexive

Are there interesting examples of "almost" partial orders $\preccurlyeq$, where only some elements $x$ satisfy the reflexivity axiom $x \preccurlyeq x$, but every $x$ has at least some $y$ ...
• 2,000
16 views

• 904
31 views

### Binary subset rank and unrank [closed]

I want to rank and unrank a "K" bit binary subset within a set, where only $\leq$ "m" consecutive $0$s and $\leq$ "n" consecutive $1$s are allowed. I referred to the ...
• 1
33 views

### Find necessary and sufficient conditions for ordinal monotonicity.

First of all let's we remember the following result. Theorem Let be $\lambda$ and ordinal: a predicate $\mathbf P$ is true for any $\alpha$ in $\lambda$ when the truth of $\mathbf P$ for any $\beta$ ...
17 views

### Let $f(x) \in F[x]$, and $K / F$ an extension which contains $R_f$, the set of all root of $f(x)$. show the equivalence for a subfield $D \leq K$

I have to show the equivalence of this Let $f(x) \in F[x]$, and $K / F$ an extension which contains $R_f$, the set of all root of $f(x)$. show the equivalence for a subfield $D \leq K$ : (a) $D$ ...
1 vote
9 views

### Stratification associated to hyperplane arrangement induced by projective compactification of linear space

I am reading this Brief Introduction to Tropical Geometry and I am trying to understand section 5.4. In particular I want to understand the following construction given at the beginning of the chapter:...
• 535
65 views

### Law of Trichotomy for Well-Orderings

Often in beginning set-theory courses, and in particular in Jech's book Set Theory, it is proved from scratch that given any two well-orderings, they are isomorphic or one is isomorphic to an initial ...
16 views

182 views

### Are linearly ordered topological spaces well-based?

A linearly-ordered topological space or LOTS is one whose topology admits a basis generated by open intervals of a total ordering of its points. A well-based space is one which admits a local basis of ...
• 153
1 vote
46 views

### Does every set with a supremum contain a monotone net converging to that supremum?

It's well known that if $U \subset \mathbb{R}$ is bounded, then there exists a monotone increasing sequence $(x_{n})^{\infty}_{n=1}$ converging to $sup(U)$. My question is: Let $X$ be a lattice, and ...
33 views

• 5,584
38 views

### Necessity of denseness and completeness for a surjective monotone being continuous

It turns out that the familiar result that surjective monotones $\mathbb R\to\mathbb R$ are continuous extends to general LOTS (linearly ordered topological spaces): Theorem. If $X$, $Y$ are LOTS ...
• 3,925
187 views

### Number of surjective functions with given property

Let $n \in \mathbb{N}, n \geq 2$ and $M = \{1, 2, \ldots, n\}$. Show that there are more than $2^n$ surjective functions $f : \mathcal{P}(M) \rightarrow \{0, 1, \ldots, n\}$ such that $f(A) \leq f(B)$ ...
• 175
26 views

### Relabel According to the Order of First Occurrence

Let $a\in\mathbb R^n$ be a tuple of length $n\in\mathbb Z_{>0}$. Let $X=\{a_i:1\le i\le n\}$ be the set of elements of $a$ for $x\in X$ let $$i(x)=\min\{j:a_j=x\}$$ be the first occurence of $x$ in ...
• 3,558
1 vote
40 views

### How are the two definitions of Eulerian posets equivalent?

I have been following Stanley's Enumerative combinatorics for the definition of an Eulerian poset. It is defined as follows: Definition: A finite graded poset $P$ with $\hat{0}$ and $\hat{1}$ is ...
• 73
107 views

### Is $\emptyset : \emptyset \to \emptyset$ an isomorphism from $(\emptyset, \leq)$ to $(\emptyset, \leq)$?

I was asked to determine whether the following statement is true: If every function $F : P \to P$ is a homomorphism from $(P, \leq)$ to $(P, \leq)$, with $\leq$ an arbitrary order, then $|P| = 1$. ...
• 3,322
18 views

### Hasse Diagram multiple choice. Upper/lower bound and maximal/minimal.

Hi, this is one of the questions from my Discrete Mathematics exam that I got wrong. I believe I answered 2 since I did not see the "not" in the question. Which of the following statements ...
• 11
1 vote
50 views

### Complete a total ordered abstract set

Given a total ordered abstract set $(S,\preceq)$. The set is said to be complete if any non-empty subset that is bounded from above/below has a supremum/infimum. Given a $(S,\preceq)$ may not be ...
32 views

### How to frame the dual statement in a lattice ordered set or an algebraic lattice in general

I am learning the theory of posets and lattices which will eventually lead to Boolean Algebra. I am stuck with the proper understanding of the concept of duality. Followings are what I have gathered ...
1 vote
33 views

### Definition of 2-chain in Posets

The definition of a 2-chain comes from Fayer's paper at: https://qmro.qmul.ac.uk/xmlui/bitstream/handle/123456789/64468/Fayers%202-chains%3A%20an%20interesting%202020%20Accepted.pdf?sequence=2&...
33 views

### Weaker notion of topological ordering for directed graphs

Let $G = (V,E)$ be a directed graph with $v \rightarrow w$ denoting an edge from $v$ to $w$. Now if $\le$ is a total order on $V$ then $\le$ is called topological order of $G$ if $v \rightarrow w$ ...
• 204
1 vote
73 views

### Example where r.v. $X_2$ stochastically dominates $X_1$ but $P(X_1 > X_2) \geq 0.95$

The problem is from a textbook I'm reading, but even with the hint, I'm not being able to come up with a solution. Let $X_1$ and $X_2$ be two random variables with CDFs $F_1$ and $F_2$. We say $X_2$ ...
• 374
1 vote
33 views

### Does this poset property have a name?

I have a poset with the following property: For any infinite descending chain $x_1 > x_2 > \dots$ and any $y$ that is a lower bound for the chain ($y < x_i$ for all indices $i$), there ...
• 4,186
177 views

### Do all infinite posets contain an isomorphic proper subposet.

Given an infinite poset $P$, does it always contain a proper subposet $Q \subsetneq P$ such that $P$ and $Q$ are isomorphic as posets? What motivated this question is the following. It can be seen ...
• 63
42 views

### Proof of non-isomorphic orders

Task: Let $A = \{(n, k) ∈ N × N : k \leq n\}$ and $B = \{(n, k) ∈ N × N : n \leq k\}$. Consider the restriction of the lexicographic order $N ×_{lex} N$to these sets: a pair $(n_1, k_1)$ is less than ...
120 views

### Does $\mathcal{P}(\mathbb{N})$ contain an uncountable antichain?

I was given the following question on my homework: Given a set $B$, a subset $\mathcal{A}$ of $\mathcal{P}(B)$ is called an antichain if no element of $\mathcal{A}$ is a subset of any other element of ...
55 views

### The subspace topology of $Y_u$($Y$ with upper topology) is strictly coarser than the one induced from $X$?

Let $(X,\leqslant )$ be a poset, we define the upper topology has the principle upper sets, that is upper sets of the form $\left \{ \uparrow x:x\in P\right \}$, as the subbase. We can define ...
• 31
1 vote
43 views

### Embedding a Countable Linear Order into Q: How to use the Axiom of Choice

I have a question about the rigorous justification of how to construct an embedding of a countable Linear Order into Q. In brief, where/how is the Axiom of Choice applied in this construction? More ...
• 407
35 views

136 views

### Partial orders and antichains

Task: Let $(P, ⩽_{1} ), (P, ⩽_{2} )$ be such partial orders on one set (nonempty) that the size of the maximum antichain in the first is $k_{1}$ , in the second is $k_{2}$ . Is it true that the size ...
1 vote
191 views

### Antichains and chains in partial orders

Task: Give an example of a partial order in which there are exactly two antichains of size 10, and these antichains do not intersect; and there are exactly 100 chains of size 3 (the size of the chain ...
70 views

### Abelian subgroups of order automorphism group $({\rm Aut}(\mathbb R,\le), \circ )$

I am searching for any results regarding Abelian subgroups of $({\rm Aut}(\mathbb R,\le), \circ )$, the order automorphism group of $\mathbb R$ (order automorphisms of $\mathbb R$ with the composition ...
• 169
34 views

### Positive semidefinite inequality: $(AXA^T)^+ \geq (AXA^T + Y)^{-1}$ on $\textrm{Im}(A)$

I asked a question earlier but it wasn't quite correctly stated, so I'll reset. Let $A$ be an $n\times n$ matrix of rank $k<n$ and let $X,Y$ be two symmetric positive definite matrices. Let $Z^+$ ...
• 5,258
109 views

### Strict order and adjacent elements

Task: Prove that there is no strict order on 14 elements in which there are exactly 50 pairs of adjacent elements. Some clarifications: Elements x, y of order (X, <) are adjacent if x < y and ...
81 views

### Strict partial order and strict linear order

Task : A binary relation on a set of 7 elements contains exactly 20 pairs. Could it be : a) a strict partial order relation? b) a relation of strict linear order? In strict linear order, any pair of ...
65 views

### Number of orderings of a binary tree such that parent comes before children

I am currently making a research project on ILP based optimal unpacking of CHs and can not figure out a specific question. To compare my approach, I would like to know the total amount of possible ...
75 views

### Equivalence of existence of upper bound for totally ordered subset and increasing sequence.

Let $(X, \leq)$ be an ordered set. I would like to know if the following two conditions are equivalent: Every totally ordered subset of $X$ has an upper bound. Every increasing sequence of $X$ has an ...
• 845
1 vote
45 views

### If the direct product of two semilattices exists, what does its Hasse diagram look like in terms of its constituent semilattice Hasse diagrams?

This is likely to be a quick question. Definition: A semilattice $(L,\lor)$ is a commutative, idempotent semigroup. The Hasse diagram $H$ of $L$ is with respect to the order $x\le y$ iff $x\lor y=y$....
• 45.1k
1 vote
Note: This is a soft-question in the flavour of, say, "what does $X$ look like?" and "Is there a description of $Y$?" - so, hopefully, it is not too broad. Let's focus on the ...