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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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
-1 votes
0 answers
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
2 votes
2 answers
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
-2 votes
0 answers
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 ?
-2 votes
0 answers
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
0 votes
1 answer
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 ...
5 votes
1 answer
59 views

Two poset properties: are they related?

A bunch of infinite posets $P$ with $\hat 0$ have the following property For every $x\in P$, the principal filter $\{ y\in P : y\ge x\}$ is isomorphic as a poset to $P$ itself. Examples include ${\...
  • 1,700
0 votes
0 answers
25 views

Can strict partial orders be axiomatized using just one elementary sentence?

This is a follow-up to my previous question, here: Can equivalence relations be axiomatized using just one elementary sentence?. Referring back to that question, I define an elementary sentence to be ...
  • 16.7k
0 votes
0 answers
47 views

How many minimum and maximum elements are there in a set

Let $A = ${$X \in P(\{1,2,3.....10\}) : 2 \le |X| \le 7$} How many minum and maximum elements are in the partial order $(A, \subseteq)$ ? I am not quite sure, but it seems to me that there should be 5 ...
  • 1
-6 votes
0 answers
40 views

Write out all the elements of this collection in lexicographic order [closed]

Let $\Omega = \{a, b\}$ and let $\mathcal{X}$ be the set of all words in $\Omega$ with length not more than 3. Write out all the elements of this collection in lexicographic order. Could anyone ...
  • 1
0 votes
1 answer
55 views

Cardinality of subsets of $\mathbb{Q}$ (or $\mathbb{R}$) which are order isomorphic to $\mathbb{Q}$ (respectively $\mathbb{R}$)

I am supposed to solve these two exercises for a set theory course. I should have done the first one, but I do not have good ideas for the second one. Find the cardinality of the subsets of $\mathbb{...
0 votes
1 answer
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
0 votes
1 answer
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
0 answers
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 ...
0 votes
1 answer
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
0 votes
4 answers
36 views

Can a strict order relation imply an equality relation?

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 ...
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) \;\...
  • 1
3 votes
1 answer
56 views

Definition of an interval in a poset

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$ ...
  • 1,808
1 vote
0 answers
48 views

is there a common way of denoting the last element of an ordered set?

Ordered sets may (or may not) have last elements. Is there a common way of denoting the last element of an ordered set. For example if we define $A$ to be the ordered set $\langle \mathbb N, >\...
6 votes
1 answer
261 views

Continuous chain of $\kappa^+$ isomorphic linear orders on $\kappa\ge\aleph_1$

For $\kappa\ge\aleph_0$ an infinite cardinal, and for $\kappa<\alpha\le\kappa^+$ an ordinal, we ask the existence of a chain $\left\langle(I_i,{<}):i<\alpha\right\rangle$ of linear orders ...
  • 145
4 votes
1 answer
38 views

How do you prove that a set doesn't contain maximal elements?

I know that the Zorn's lemma (If every totally ordered subset of a partially ordered set S has an upper bound, then S contains a maximal element) can be used to prove the existence of a maximal ...
-1 votes
1 answer
29 views

ord((a,b)) in group theory [duplicate]

$G,H$ are groups and $a \in G$ and $b\in H.$ $\operatorname{ord}(a)=n$ and $\operatorname{ord}(b)= m.$ I need to find the order of $(a,b) \in G\times H.$ I know it supposed to be something with lcm ...
4 votes
2 answers
67 views

Is a point where any sequence that converges to it contains it the same thing as an isolated point?

Suppose I have a topological space $(X, \tau^X)$. Based on the Wikipedia definition of an isolated point, $p \in X$ is an isolated point if and only if $\{p\} \in \tau^X$. In one specific example I'm ...
  • 8,738
1 vote
1 answer
63 views

Is there a first-order sentence characterizing total orders with an order-automorphism with no fixed points?

I'm interested in Boolean rings since they model classical logic well. If you take an infinite Boolean ring whose induced order is total and cut off the top and bottom elements, then you get the kind ...
  • 8,738
1 vote
0 answers
18 views

What is the minimal number of partial orders whose union equals a given binary relation on a finite set?

I'm reading Bertrand Russell's 1901 On The Notion of Order. My question isn't from the book per se, but I say that for whatever context it provides. Probably none. Anyway, here is the question: Let $S$...
  • 1,559
0 votes
0 answers
6 views

Construct a well-order of a given order type on a set of well-orders

Let $\alpha$ be a countable ordinal. We look at the set of the well-order on $\mathbb{N}$ of order type $\alpha$ which we write: $$E = \left\{R \subset\mathbb{N}^2 \,| R \text{ is a well-order of ...
  • 173
0 votes
0 answers
18 views

Size of the n-th subset

Say I have some set $S$ with $n$ elements, then I know there are $2^n$ possible subsets. I sort these subsets in a sequence with increasing sizes, so the sequence starts with the empty set and ends ...
  • 11
0 votes
0 answers
35 views

How to prove that "$¬(x<y)$ is $y\le x$" and "$¬(x\le y)$ is $y<x$"(Assume that $\le$ is total orders and $<$ is strict total orders)

Suppose that $\le$ is total orders (satisfy reflexive, anti-symmetric, transitive, and comparable) Suppose that $<$ is strict total orders (satisfy irreflexive, transitive, and comparable) How to ...
  • 1

1
2 3 4 5
79