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

3,934 questions
Filter by
Sorted by
Tagged with
31 views

### Construct a linear order on $Y\cup \{x\}$

Let $(Y , \le)$ be a linear order and $x \notin Y$, construct a linear order on $Y\cup \{x\}$. Well I actually don't understand what construct means and how to do it. Maybe anyone has an idea?
• 33
43 views

### Define a well order on $A \cup B$

Let $(A,\le_1)$ and $(B,\le_2)$ be well orders, define a well order on $A \cup B$. I really don't understand how to define well order on a union of two well orders. Please provide your ideas.
• 33
20 views

### Order ideals of a fence

Let $F_n$ be the $n$-element fence, that is, $F_n=\{a_1, \ldots, a_n\}$ with $$a_1>a_2<a_3>\cdots a_n$$ and no other elements related. Here is the Wikipedia article about fences : https://en....
• 83
21 views

### Does a ccc poset of size $\kappa$ always have $\kappa$ dense subsets?

Imagine we have a ccc poset ${p_{\alpha} : \alpha < \kappa }$ for some uncountable cardinal $\kappa$. Can we always find $\kappa$ many dense subsets ?
• 49
33 views

### Find a set of minimal elements in set $\langle \mathbb N\setminus\{0\},|\rangle$

We consider a relation $|$ on set $\mathbb N\setminus\{0\}$ Find set of minimal elements in set $\langle \mathbb N\setminus\{0\},|\rangle$ Prove that in set $\langle \mathbb N\setminus\{0\},|\rangle$...
• 1
10 views

### Does the following give a well-ordering on the quotient of a well-ordered set by an (unrelated) equivalence relation?

Let $X$ be a set equipped with a well-ordering $\leq$ as well as an (unrelated) equivalence relation $E$. We define a relation $\leq'$ on $X/E$, given for $a,b \in X/E$ by $a \leq' b$ iff there is ...
• 2,007
59 views

• 1,693
24 views

### Do all linear orders have Lebesgue dimension $\le 1$?

It seems intuitively obvious that a linear order should have Lebesgue covering dimension $1$, but I've spent quite a bit of time and been unable to prove this. I would like to know if it is true, and ...
• 398
38 views

### If for monos $u\leq v$ and $v\leq u$ then their domains are isomorphic

I'm unable to prove that if a mono $u:B\to A$ is less then mono $v:C\to A$ by $f:B\to C$ with $v\circ f=u$ and also $v\leq u$ by $u\circ g=v$ then $B\cong C$ by using some morphisms as above, but I ...
• 3,991
1 vote
39 views

### Filtered colimits and the free frame construction

Let $F : C \to D$ be a functor between categories with filtered colimits, and let Cat be the category of categories. Let $(M, μ, η)$ be a monad on Cat. What properties of $M$ are necessary to ensure ...
• 5,307
38 views

### Product of Countable Well-Ordered Set with $[0,1)$ is Homeomorphic to $[0,1)$

As part of a proof that the long line is locally Euclidean, I'd like to prove the following: Proposition. If $A$ is a countable well-ordered set, then $A \times [0,1)$ with the dictionary order is ...
• 1,953
36 views

Let's assume we have a partial or total order relation $R$ defined on a set $S$. If $R$ was not strict (i.e. it denoted $\leq$ instead of $<$), an equality relation $E$ could be defined as such: $$... • 193 0 votes 0 answers 26 views ### Is there a name for this ordering on integer vectors? Let \mathbf{k} \in \mathbb{[n]}^{u} be u-dimensional arrays, where [n] = \{0,1,\dots,n\}. Now let us assume that \mathbf{k} are generated under u nested for loops running from 0 to n. For ... • 1,667 0 votes 1 answer 49 views ### Finding \inf(\{30, 40\}) and \sup(\{2, 5\}) in Hasse diagram I would like to ask what is \inf(\{30, 40\}) and \sup(\{2, 5\}). I think that \sup(\{2, 5\}) is 20 and \inf(\{30, 40\}) does not exist, but it may be 2, but 5 is on the same level and I ... 0 votes 0 answers 26 views ### quick question about posets using inclusion Let X be a collection of sets that is partially ordered by inclusion (\subseteq). I think I know that answer to this(I think it is yes), but are the linearly ordered subsets of X must always ... • 278 0 votes 0 answers 42 views ### Dilworth's Theorem for Totally Ordered Sets Dilworth's Theorem, states that in a poset the size of the largest antichain is the same size as the smallest chain decomposition. If I am understanding this correctly then, In a totally ordered set, ... 0 votes 0 answers 23 views ### How we can define Super-Greedy Linear extension of a Poset I am trying to understand the Super-Greedy linear extension of a poset. It is a topic of discrete mathematics, and I have tried to search the web, but only got one useful definition which I can't ... 0 votes 0 answers 46 views ### Supremum in [-1, 1]^\omega The Problem In this answer, a procedure for showing that every closed subspace of [-1,1]^\omega is separable is given by making use of the lexicographic order. As far as I can tell, there are ... • 715 1 vote 0 answers 59 views ### Does existence of \sup (A \cup B) imply existence of \sup A and \sup B? Let there be defined an order \langle X, \leq \rangle and two sets A, B \subseteq X. Does existence of \sup (A \cup B) imply that both \sup A and \sup B exist? Here is my reasoning so far: ... • 21 3 votes 1 answer 44 views ### Pullback map of monotone map I begun reading the “Applied Category Theory“ by Fong and Spivak, and I got stuck on this excercise (1.74): Let P and Q be preorders, and f \colon P \rightarrow Q be a monotone map. Then we can ... 0 votes 0 answers 43 views ### Set of Distributions on Finite Set with Monotone Likelihood Ratio Order forms a Complete Lattice? Let (X,\geq) be a finite, linearly ordered set, and \Delta(X) the set of distributions over X, that is, p \in \Delta(X) \Longrightarrow p:X \to [0,1] such that \sum_{x \in X}p(x)=1. For p,q\... 0 votes 0 answers 31 views ### For a finite irreducible Coxeter group, what’s the largest set of pairwise-mutually incomparable elements with respect to the weak order? Given a finite irreducible Coxeter group W, what’s the largest subset K\subseteq W such that for all u,v \in K, it is not true that u <_R v (nor v <_R u) where <_R denotes the ... 2 votes 1 answer 38 views ### Defining an order on strings from an alphabet given an order on the alphabet itself Let A be a finite nonempty alphabet, and let \leq be a partial order on A. I want to define a partial order on A^*, the Kleene closure of A, based on the partial order on the alphabet itself.... • 16.7k 1 vote 1 answer 47 views ### Is this a partial order relation? Let \;C = set of cities. The relation \,S=\big\{(x,y)\;|\;x\in C\text{ and }y\in C are less than 50 miles from each other\big\} to me understanding is : reflexive: all cities are less than ... 1 vote 2 answers 70 views ### Example of a complete unbounded dense linearly ordered set that isn't isomorphic to \mathbb{R} I know as a fact that \mathbb{R} is the unique (upto isomorphism) complete linearly ordered field. But if we remove the "field" condition and replace it with "dense unbounded set"... 4 votes 1 answer 150 views ### Are [0,1)\times\Bbb R and [0,1)\times\Bbb Q similar? Let a:=[0,1)\times\Bbb R and b:=[0,1)\times\Bbb Q and let \prec_a and \prec_b denote their respective antilexicographic orders. Are (a,\prec_a) and (b,\prec_b) similar? \underline{\... • 4,300 0 votes 0 answers 39 views ### Partial order, well order and initial segment I saw the following definition for initial segment in https://digitalcommons.kennesaw.edu/cgi/viewcontent.cgi?article=2161&context=facpubs If \leq is a partial order in a set X, then a chain ... • 175 2 votes 1 answer 64 views ### Which ordinals can be order-embedded in 2^\kappa for a given infinite cardinal \kappa? Let \kappa be an infinite cardinal. The set 2^\kappa=\{0,1\}^\kappa is given the lexicographically order in the usual way (f<g if f(\alpha)<g(\alpha) at the first position where the ... • 2,717 0 votes 0 answers 39 views ### Order relation notation \succeq My main concern is with the notation around order relations, specifically the use of \succeq, I briefly outline relations more generally to set up my thinking. But the questions really starts at the ... • 323 1 vote 1 answer 90 views ### are there transfinite equivalents to non-integer real numbers? Cantor first envisioned the transfinite ordinals as a kind of 'extension' to the finite integers, where 𝜔 followed on where ℕ left off and continued the sequence. In this way, we can see them as '... • 29 1 vote 1 answer 66 views ### Does every total order have a sequence tending to infinity? [duplicate] Is the following statement correct? Let X be a non-empty set. Let \le be a total order on X. There exists an infinite sequence S such that: for every natural number n we have S_n \in X. for ... • 77 0 votes 0 answers 26 views ### Linearisations of a preorder which 'preserve' equivalence classes. Suppose I have a preorder \leq on a (finite) set X (so \leq is reflexive and transitive). From this, I can construct an equivalence relation by x\sim y if and only if x\leq y and y\leq x. ... 3 votes 1 answer 32 views ### "Multiplicative" Archimedean property in ordered fields There following are two equivalent formulations of the Archimedean property of an ordered field F: \mathbb N is unbounded in F. (Formulation for the ordered group (F, +)). For any x, \... • 2,556 0 votes 1 answer 32 views ### Cofinality of a set Let (I, \leq) be a directed set. Suppose that I has uncountable cofinality and that one can decompose I as a countable union I = \bigcup_{n = 0}^\infty I_n, is it true that at least one of the ... • 474 0 votes 0 answers 69 views ### Hasse diagram for poset including pairs I created a Hasse diagram for the poset (\Box_4^2, \leq) with \Box_4 = \{0, 1, 2, 3\} and \leq being defined as$$(a,b) \leq (c,d) \quad\Longleftrightarrow\quad (a<c \text{ and } b<d) \;\...
I can think of two nonequivalent ways of defining an interval in a poset: An interval of a poset $P$ is a subset $I\subset P$ with the property that for all $x, y, z\in P$ such that $x < y < z$ ...