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
1
vote
0answers
25 views

Characterising $\sigma$-algebras as posets

A $\sigma$-algebra is defined as a set $X$ together with a subset $\Sigma$ of the power set $\mathcal{P}(X)$, such that $X\in \Sigma$ $\Sigma$ is closed under complementation $\Sigma$ is closed under ...
0
votes
1answer
31 views

What concept of order is introduced in the twentyfold way?

Four of the folds not present in the twelvefold way but introduced in the twentyfold way, rows $5$ and $6$ of the linked table, are defined by the statement that order matters. However, my ...
1
vote
1answer
24 views

A proof of well-ordering theorem in “Set Theory and General Topology” by Fuichi Uchida.

I am reading "Set Theory and General Topology" by Fuichi Uchida. In this book there is the following theorem: Let $X$ be any set. There exists an order $\rho$ such that $(X, \rho)$ is a ...
1
vote
0answers
19 views

Is every Hasse diagram connected?

Is every Hasse diagram connected? In other words - is some antichain subset of a poset, a poset in its own right? I ask because I see no connectedness condition in the definition, but never seem to ...
2
votes
0answers
32 views

From cardinal comparisons to pointwise comparisons of functions.

Let $X$ be a set and let $Y$ be an ordered set. For $f, g : X \to Y$, if $f \le g$ pointwise, then for each $y \in Y$, $$\#\{x \in X \mid f(x) \le y\} \ge \#\{x \in X \mid g(x) \le y\}$$ $$\#\{x \in X ...
3
votes
1answer
45 views

Reverse order of a ring

When we think of an ordered structure with an order $\le$ we assume there is an opposite order $\le^{op}$ as well: $a \le^{op} b \iff b \le a$. I would suggest this is a fundamental principle for ...
1
vote
1answer
25 views

Is this a lattice of $6$ elements?

I am reading "Set Theory & General Topology" by Fuichi Uchida. In this book, the author wrote all lattices($15$ lattices) of $6$ elements. I wonder the following is also a lattice of $6$...
2
votes
0answers
21 views

Well-founded orders and sums

I am looking for a reference on well-founded ordered sets, that would mention the following notions and results: $\\$ a) Consider a well-ordered set $(I,<)$ and a family $(X_i,<_i)$ of well-...
0
votes
0answers
44 views

Forcing: to find strictly stronger or weakly stronger condition?

In the $(*)$ below, I would like to understand whether "all we have to do is find $q>p$ such that ..." or as I would say $q\geq p$ such that... I have two questions about this: does this ...
1
vote
0answers
43 views

Give an example of a strictly monotone function which is not injective.

The following question/task is from Taylor's, "Practical Foundations of Mathematics," page 175, ISBN 0 521 63107 6 hardback. I kind of answered it myself in typing this up, but I'll share it ...
3
votes
0answers
26 views

The discriminant of positive definite binary quadratic forms in partially ordered rings

Let $A$ be a commutative ring, partially ordered by $\le$. Consider the following proposition: Proposition 1. Let $a, b, c$ be in $A$ and assume $a \ge 0$ and $c \ge 0$. If $a n^2 + 2 b n m + c m^2 \...
1
vote
1answer
32 views

Please help me prove that the equational definition of Heyting Semilattice is equivalent to the Order-Theoretic definition

The situation: An algebraic semilattice $(L, \wedge, \top)$ satisfies the following axioms: $\forall x \in L. x \wedge \top = x$ $\forall x, y \in L. x \wedge y = y \wedge x$ $\forall x, y, z \in L. (...
2
votes
1answer
54 views

Comparability with identity of an ordered semigroup

It is possible to compare any ordered semigroup with $0$: Comparability with zero of an ordered semigroup Let's say an ordered semigroup $S$ is comparable with identity if it can be embedded into an ...
1
vote
1answer
43 views

Comparability with zero of an ordered semigroup

Is it correct that any ordered semigroup $S$ can be embedded into an ordered semigroup with zero $S_0$ in which every element is comparable with $0$, in a way that the order of $S$ is a subset of the ...
1
vote
2answers
129 views

Ordered semigroup with an absorbing element

According to Wikipedia, a partial order $\le$ on a semigroup $S(\bullet)$ is compatible with the semigroup operation if: $a \le b \implies a \bullet c \le b \bullet c$ and $c \bullet a \le c \bullet ...
0
votes
1answer
20 views

ƒ is a monotonic increasing function under two total orders, R and S, of a set A. How are R and S related?

This is problem #9 from section 7.4 of Axiomatic Set Theory by Patrick Suppes. Intuitively, it seems to me that either R=S, or S is R's converse. However, I don't see how one would approach proving ...
0
votes
0answers
26 views

Why is X not a legitimate Moore family?

According to the definitions in the appendix A.1 of Principles of Program Analysis, $L = (\mathcal{P}(S), \subseteq)$ for $S = \{1, 2, 3\}$ is a complete lattice. Furthermore, neither $X = \{\emptyset,...
0
votes
1answer
44 views

Dictionary ordering in $\mathbb{R}^2$ is not complete.

Show that the order "$\leq$" on $\Bbb{R}^2$ defined by, $(a,b)\leq(c,d)$ if ($a<c$) or, $(a=c$ and $b\leq d)$ is not complete. Hint: Use the set $E=\{(\frac1 n, 1-\frac1 n): n\in \Bbb{N}\...
4
votes
1answer
45 views

If $X$ and $Y$ are two ordered sets, how many orderings of $X \times Y$ exist that preserve the orderings of $X$ and $Y$?

Suppose $X$ and $Y$ are two totally ordered sets with $|X| = n_X$ and $|Y|=n_Y$. We'll say an ordering ($\preceq$) of $X \times Y$ preserves the orderings of $X$ and $Y$ if for any elements $x_1,\,x_2 ...
2
votes
1answer
44 views

Do these axioms define a boolean algebra?

In Awodey's "Category Theory", he defines a boolean algebra $\mathcal{B}$ as a poset $(B,\leq)$ along with two elements $0$ and $1$, along with two binary operations $\lor, \land$, and an ...
0
votes
0answers
34 views

Real-world example of a preorder relation which is not a partial order

I have tried long and hard to find a real-world occurrence of a preorder relation which is not a partial order, but couldn't find any. Can someone give a real-world example of a such a relation, that ...
1
vote
1answer
38 views

Is there a commonly used notion of regular language outside of finite order types and $\omega$?

There are correspondences between regular languages and finite automata, and $\omega$-regular languages and Buchi or Muller automata (as well as the characterisation in terms of the monadic second ...
1
vote
2answers
46 views

Is there a natural way to totally order the set of unlabeled binary trees on $n$ nodes?

Let $C_n$ be the $n^{th}$ Catalan number. There are $C_n$ unlabeled binary trees having $n$ internal nodes. I want to totally order these trees in some (hopefully not too complicated) natural manner. ...
0
votes
0answers
27 views

Relations and partial with some set A and a relation R b|d

$A=\{1,2,3,4,5,6\}$ and on B=$A\times A$ we define a relation R as follows : $<a,b>R<c,d>$ if and only if $a \leq c $ And $b|d$ (without Remainder) a) Prove that R is partial Order on B=$A\...
6
votes
2answers
62 views

Embedding of countable linear orders into $\Bbb Q$ as topological spaces

Any set $X$ with a linear order has a uniquely associated order topology generated by the open intervals. That makes it into a linearly ordered topological space (LOTS). It is also a standard result ...
3
votes
2answers
75 views

Decomposition of $2^{[n]}$ into $\binom{n}{n/2}$ chains

I am struggling with this problem: Let n be an even number, and denote $[n]=\{1,2,...,n\}$. A sequence of sets $S_1 , S_2 , \cdots , S_m \subseteq [n]$ is considered graceful if: $m$ is odd. $S_1 \...
1
vote
1answer
25 views

Characters on inverse semigroups: Hahn-Banach?

Let $S$ be an inverse semigroup with zero $0\in S$, $$ 0s=0=s0,\quad\forall s\in S. $$ Let $e=e^2\in S$ be an idempotent and consider the character, $$ \phi:U\to\{0,1\}:\quad\phi(e)=1,\quad\phi(0)=0, $...
0
votes
1answer
22 views

A question on order-isomorphism with $\mathbb N$.

Let $A$ be a countable subset of $\mathbb R$ which is well ordered with respect to usual ordering $\leq$ of $\mathbb R$.Then does $A$ have an order preserving bijection with a subset of $\mathbb N$? ...
1
vote
1answer
38 views

Understanding the steps in Pugh's proof about the Least Upper Bound Property

2 Theorem The set $\Bbb R$, constructed by means of Dedekind cuts, is complete in the sense that it satisfies the Least Upper Bound Property:If $S$ is a nonempty subset of $\Bbb R$ and is bounded ...
0
votes
1answer
24 views

Inductive set, maximal elements and upper bounds

In my algebra notes : Definition of upper bound $x \in X$ is an upper bound of $Y$ if $y \le x\ \ \forall y \in Y$. Definition of maximal element We say $m \in X $ is a maximal element if $m\leqslant ...
0
votes
1answer
35 views

Non-emptyness of projective limit over countable set

I am doing exercise 1.9 from Lenstra's Galois theory for Schemes. Let $\left((S_i)_{i\in I},I,f_{ij}\right)$ be a projective system, where $I$ is countable, all $S_i$ are non-empty and all $f_{ij}$ ...
-1
votes
1answer
49 views

Chain that doesn't contain maximal element?

I cannot find a proof or example that every chain contains a maximal element (from Friedberg et al). A collection of sets is called a chain if for each pair of sets A and B in the chain, A ⊆ B or B ⊆ ...
0
votes
1answer
26 views

Hausdorff Maximal Principle implies Well-Ordering Theorem

While looking at a proof of "Maximum Principle implies Well-Ordering Theorem" in this web-page https://proofwiki.org/wiki/Hausdorff_Maximal_Principle_implies_Well-Ordering_Theorem#:~:text=By%20the%...
3
votes
1answer
42 views

If $X_i$ has supremum for any $i=1,…,n$ then $\sup\bigcup X_i=\max\{\sup X_i\}$.

Statement If $X$ is a totally ordered set and if $\mathfrak{X}=\{X_i\subseteq X:i=1,...,n\}$ is a finite subcollection of not empty subset of $X$ with supremum then $\bigcup\mathfrak{X}$ is limited ...
2
votes
1answer
64 views

Hessenberg power of ordinals (redux)

This is a follow-up to this question, in which the given definition failed. Let $f : \varepsilon_0 \rightarrow \mathbb{N} \rightarrow \mathbb{N}$ recursively defined by \begin{align} f\left(\sum_{...
1
vote
1answer
63 views

Prove that for k, the number of elements with prime order p, k = -1 (mod p)

Let p be a prime number and let G be a finite group whose order is divisible by p. Let k be the number of elements $x \in G$ of order p and let $l$ be the number of subgroups $ H \subseteq G $ of ...
1
vote
0answers
31 views

Partially ordered set with mixed-integer variables

I have a finite set of vectors $\mathcal{S} \subset \mathbb{R}^n$ with mixed-integer components (let's say $n_c$ and $n_i$, with $n = n_c + n_i$). I was wondering whether $\mathcal{S}$ is always ...
1
vote
0answers
26 views

Given a boolean matrix $M$ what are the matrices formed by replacing $1s$ in $M$ with $0s$ called?

Given two boolean matrices $A$ and $B$ over some common dimensions one can form an order via $A\leq B\iff \forall i,j(A_{i,j}\leq B_{i,j})$ under this order, what would the matrix $A$ be called in ...
2
votes
1answer
30 views

How can we express that a partial order is more complete than another one?

Suppose we have two partial orders $R$ and $I$ on $\mathbb{C}$ (conplex numbers) such that: $R$ is a total order on $\mathbb{R}$ (real numbers). $I$ is also a total order on $\mathbb{R}$ and, ...
-1
votes
1answer
68 views

Cauchy completion of transfinite “rationals”

Let the Hessenberg power $\alpha^\beta$ be the supremum of ordinals that are order-isomorphic to some well-order on the set of finite-support functions $\beta \rightarrow \alpha$ that extends the ...
0
votes
0answers
22 views

Definition of a successor in a cyclic order

There is a common accepted definition of a successor in a linear order: an element $b$ is a successor of an element $a$ of a linearly ordered set $S$ if $a < b$ and $\nexists c \in S: a < c <...
0
votes
0answers
19 views

Prove: If gcd(ord(x),ord(y))=1, then ord(xy)=ord(x) ord(y) when x,y in G (abelian) [duplicate]

$\newcommand{\ord}{\operatorname{ord}}$Let G be an abelian group and let $x,y \in G$ be two elements with finite order. Then, prove that if $\gcd(\ord(x),\ord(y))=1$, then $\ord(xy)=\ord(x) \ord(y)$ ...
0
votes
2answers
20 views

Isomorphism between two partially ordered sets.

I want to define an Isomorphism $\phi:\left\langle [n]\times[m],\leq_{Lex}\right\rangle \rightarrow\left\langle [n\cdot m],\leq\right\rangle $ I understand how to write down this isomorphism by hand: ...
1
vote
1answer
41 views

How to quantify asymptotic growth?

Specifically, my research question is to find operator $A: (\mathbb{R}^+\rightarrow\mathbb{R}^+)\rightarrow\mathbb{S}$, where $\mathbb{S}$ is some totally ordered set, such that for $f, g: \mathbb{R}^+...
0
votes
0answers
11 views

Can a non-total order define a prepositive cone in a field?

Fact: A total order $\le$ that satisfies the ordered field axioms defines a set $\{x:0\le x\}=P$ that is a prepositive cone. I proved this. I had to invoke trichotomy (as well as other lemmas) to ...
2
votes
1answer
29 views

Use a reflexive and transitive closure to transform an antisymmetric and acyclic relation into a partially ordered set.

The relation $R=\{(x,S_1),(S_1,S_2),(S_2,S_3),(S_3,S_4),(S_4,y)\}$ is antisymmetric and acyclic but not transitive or reflexive. We know that any antisymmetric and acyclic relation can be turned into ...
0
votes
0answers
20 views

well founded induction / difference to strong induction

We are given a chocolate bar with $n$ pieces (squares) and we already know by strong induction that $n-1$ are needed to break it in individual parts. https://web.stanford.edu/class/archive/cs/cs103/...
2
votes
0answers
48 views

dominating antichain

Let $P$ be a finite set with partial orderings $\leq_1$ and $\leq_2$. Then, there is a so-called dominating antichain $A \subseteq P$ where no two distinct elements of $A$ are comparabale in $\leq_1$ ...
0
votes
0answers
19 views

Find a binomial poset with factorial function $B(n) = q^\binom{n}{2}$

In Enumerative Combinatorics, Volume I, second edition,Example 3.18.3 e, page 323, Stanley describes this poset: Let $V$ be an infinite vertex set, fix $q \in \mathbb{P}$, and let $P$ be the set of ...
0
votes
0answers
12 views

A cut of a cut of a cyclic order

Working on the problem Is there an infinite set with a discrete cyclic order? I've found an interesting relation on a cyclically ordered set (https://math.stackexchange.com/a/3697168/427611). The ...

1
2 3 4 5
63