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
1
vote
1answer
44 views

Prove the inequality $breadth(P) \leq dim(P)$

Definition 1: Let n be a positive integer. We say that an order P has breadth at most n if for all elements $x_0$, $x_1$, ..., $x_n$, $y_0$, $y_1$, ..., $y_n$ in P, if $x_i \leq y_j$ for all $i \neq j$...
1
vote
1answer
28 views

Partially ordered set's maximal and minimal

I have a few questions about a general partially ordered set which derive from a specific one. $R$ is a partially ordered set over $A=\{a,b,c,d\}$ (4 different item group). $S=R\cup {(a,b)}$ is an ...
1
vote
0answers
37 views

Complete embeddings into $Fn(\kappa \times \omega, \omega)$

I have problems to show the following: Let $\kappa$ be a regular uncountable cardinal, $\lambda < \kappa$ and let $\mathbb{P}=Fn(\kappa \times \omega, \omega)$, $\mathbb{Q}=Fn(\lambda \times \...
1
vote
0answers
18 views

Conditions for embedding to be part of Galois connection?

I am working though 7 sketches in compositionality and have almost reached the end of chapter 1, which is very much concerned with Galois Connections. One of the questions on the subject that is not ...
1
vote
1answer
102 views

Is there a name for an ordered algebraic structure that models the extended integers (i.e. enhanced with infinity)?

Is there a name for an ordered algebraic structure that abstracts the non-negative extended integers (extended in the sense that they include $\infty$), i.e. is there a name for a partially-ordered, ...
1
vote
0answers
36 views

Fractional ideals of maximal orders in quaternion algebras

Let D be a skew field that is central and finite-dimensional over a number field F (in particular: a quaternion algebra over F). Let $\Delta$ $\subseteq$ D be a maximal $\mathcal{O}$$_{F}$-order. Let $...
1
vote
0answers
37 views

How come these are distributive lattices?

On Wikipedia I can see examples of distributive lattices. But I don't get how they are distributive. To my eyes, they are not even modular. E.g. how does it fulfill the modular property of $$(x \...
1
vote
0answers
35 views

Check my understanding of proof that Partial order can be extended to total order

Induction step : let n be arbitrary natural number, and suppose that every partial order on a set with n elements can be extended to total order. Suppose A has n+1 elements and R is a partial order on ...
1
vote
1answer
79 views

Zeta polynomial of the Boolean Lattice

The task at hand is to compute the zeta polynomial $Z(B_k, n)$ of the Boolean Lattice in $k$ elements, which is the lattice formed by the subsets of $\left\{1, \dots, k\right\}$ under inclusion. The ...
1
vote
1answer
145 views

Well ordered set in both directions is finite

So I tried to prove the following statement: If $(X, \leq$) and $(X, \geq)$ are well orders, then X is finite. But I'm not sure wether it's entirely correct. Proof: A well-ordered set has the ...
1
vote
1answer
46 views

Proving something is a lattice .

Hi i was wondering if anyone could help me show the following $f\le^{*}g \iff \exists k\forall m\ge k(f(m)\le g(m)$ Show that $\le^{*}$ is a lattice. My definition of a lattice is the following let $...
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 \...
1
vote
0answers
70 views

Multiplicative absolute value

The absolute value of a real number $r$ is defined to be the additive inverse of $r$ is $r < 0$, and $r$ is $r \geq 0$, where $0$ is the additive identity of the commutative group $\mathbb{R}$. ...
1
vote
1answer
67 views

Cofinal sets and different definitions

Suppose that $A$ is an ordinal and $B\subset A$. We say that $B$ is Cofinal in $A$ iff $\sup(B) = A$. However, elsewhere I've read definitions that make no reference to ordinals. Here is the ...
1
vote
1answer
933 views

Is there a difference between a range and an interval?

Can the terms 'interval' and 'range' be used interchangeably or do they describe different things? I am talking specifically about sets of numbers under a suitable $<$ relation, such that they can ...
1
vote
0answers
26 views

Noetherianity of $\mathbb{R}^+$

I have some confusion about some properties of noetherian posets. I am defining a poset $X$ to be $\textbf{noetherian}$ if every ideal of $X$ Is finitely generated. I am trying to show that this is ...
1
vote
0answers
33 views

How to prove the minimum identity for finite number of real numbers

I have trouble in proving the following statement: Let $n$ be an integer no less than 3, and $a_1,\dots, a_n$ be real numbers. If $n$ is even, then \begin{align*} &\min\{a_1,a_2,a_3\}+...
1
vote
0answers
48 views

Which properties are invariant for totally ordered sets?

I am asked to find some number of totally ordered sets such that no one is isomorphic to a subset of another. To do this I wanted to think about the properties that are preserved for totally ordered ...
1
vote
0answers
49 views

Understanding when a strict partial order can be satisfied by a set of integers

I am playing with a problem (that's part of a much bigger problem) and trying to understand the best way to approach it and also if there are existing names for this or similar problems. If I have a ...
1
vote
1answer
63 views

Riesz space of functions from any set $X$ to $\mathbb{R}$

We collect certain functions from $f:X\to\mathbb{R}$ to $\mathscr{T}$ so that it is a vector space over $\mathbb{R}$ under the usual function addition, scalar product. Now we define an partial order ...
1
vote
0answers
192 views

Lexicographical covering of boolean poset

Consider the boolean poset $2^{[n]}$. Is it true that for each rank $k< \frac{n}{2}$ and each positive integer $t\le \binom{n}{k}$, there is a perfect matching between the first $t$ elements of ...
1
vote
1answer
70 views

Prob. 8 (b), Sec. 10, in Munkres' TOPOLOGY, 2nd ed: The union of any collection of disjoint well-ordered sets indexed by some well-ordered set …

Here is Prob. 8, Sec. 10, in the book Topology by James R. Munkres, 2nd edition: Problem 8 (a): Let $A_1$ and $A_2$ be disjoint sets, well-ordered by $<_1$ and $<_2$, respectively. Define ...
1
vote
0answers
53 views

chain decomposition on partial order set

I am trying to do exercise in this book (page 54, number 3.11). The question : Find orthogonal chain decomposition as required in the proof of theorem from Shearer & Kleitman for $n=3$ and $n=4$. ...
1
vote
0answers
23 views

Way of Ordering a ranked list

I am trying to find a good way of ordering and ranking a list of objects. They will be ranked multiple times by different people but i want their rank (out of 10) to update. e.g I rank the objects ...
1
vote
1answer
49 views

Is the indicated subring an order?

I have an exercise in my class that I don't seem to find an answer to: We are asked to tell whether the indicated subring of a number field is an order and whether it is a maximal order a) $\mathbb{...
1
vote
1answer
105 views

Hasse diagram for Four-valued Logic Algebra

For given algebra ({0,1,X,Z}, . , +) which “.” represent “Logical And” and “+” represent “Logical Or”, Following lookup tables are given (image): I guess the Hasse Diagram of a 4-Valued logic should ...
1
vote
0answers
31 views

“Is in the neighborhood of”-style relations

Consider a nonempty set $S$ with binary relations $\preccurlyeq$ and $\sim$ defined on it such that: $(S, \preccurlyeq)$ is a total ordering. $(S, \sim)$ is reflexive and symmetric. For all $x,y,z\in ...
1
vote
0answers
44 views

Function $f:\mathbb{Z}^+\rightarrow\mathbb{Z}^-$ such that $m<n\implies f(m)<f(n)$?

The title says it all; I'm wondering if there is a sequence $\{f(n)\}_{n<\omega}$ of negative integers such that successive terms get strictly larger. The issue seems to be that as soon as we fix ...
1
vote
0answers
47 views

Consider $A=^*B$ if and only if $A\triangle B$ is finite, What type of relation is $=^*$

Consider $A=^*B\iff A\triangle B$ is finite ($\triangle$ is the symmetric difference) what type of relation is $=^*$ First i start by checking if it is reflexive, anti-symmetric and transitive. so ...
1
vote
0answers
45 views

Concerning the existence of the $R-$smallest element of a subset of a partially ordered set $A$

Is the following Proof Correct? Theorem. Given that $R$ is a total-order on $A$, every finite, non-empty set $B\subseteq A$ has an $R-$smallest element. Proof. We construct the proof by recourse to ...
1
vote
0answers
65 views

Higher order version of Chebyshev's (algebraic) inequality

Let $(a_{i})_{i=1}^{n}$ and $(b_{i})_{i=1}^{n}$ be finite monotone increasing sequences (or both mon. decreasing) of real numbers and $m_{i}>0$ with $\sum_{i=1}^{n}m_{i}=1$. Chebyshev's (algebraic) ...
1
vote
1answer
25 views

Extension of a continuous preorder

Given a compact metric space $X$ and a preorder $R$ on $X$ (a reflexive and transitive relation) which is continuous in the sense that the upper and lower contour set of any point, \begin{equation*} U(...
1
vote
0answers
115 views

Poset test and Hasse diagram in GAP.

Given a finite set $X=\{x_1,...,x_r\}$ with a function $f: X \times X \rightarrow \mathbb{Z}$ on it, define a relation on it by $m \geq n$ iff $(m=n$ or $f(m,n)>0)$. Now for every element $m \in X$,...
1
vote
0answers
61 views

Closure interpretation of a lattice

Hello I am doing a bit of reading on lattices right now and I would appreciate some help. A species of algebra with meet and join operations and binary relation which is quasi ordering can be ...
1
vote
0answers
65 views

Find formula for number of dominated vectors in partial order

Below I consider vectors of same length $n$ and consisting of only $1$ and $-1$ elements. Let's call vector $v_1$ dominating for $v_2$ if count of $-1$ in $v_1$ is not less then in $v_2$ and position ...
1
vote
0answers
91 views

Compactness of modal logic by proving existence of a model for a maximal set (using Zorn's lemma)

TASK: Given a set $\Gamma$ of propositional modal formulas where every finite subset of $\Gamma$ is satisfiable (say: $\Gamma$ is finitely satisfiable), show that $\Gamma$ itself is satisfiable. IDEA:...
1
vote
0answers
34 views

Linear extension with restrictions

A problem has come up in which I have a partial order $\leq$ and I need to extend it to a linear order $\leq^{*}$ obeying a series of restrictions that, for given elements $a,b,c$, $a \leq^{*} b \leq^{...
1
vote
0answers
27 views

Counterexample to a set with a unquie maximal element implying existence of a largest element

In Willard's General Topology, he defines a maximal element to be an element of a set $A$ provided $(\forall b \in A) \ \ b_1 \leq b \implies b_1=b $. He provides this afterwards: I don't see how $b$ ...
1
vote
0answers
37 views

What is the definition of an “almost complete” order?

In a recent answer to a question of mine (https://math.stackexchange.com/a/2254369/11994) somebody mentions an "almost complete (partial) order" and an "almost complete dense order". But I couldn't ...
1
vote
0answers
204 views

Positive and negative elements of a cyclically ordered group

I am trying to prove A property of a cyclic order on a ring. In order to do it, I need the last two properties (lemmas 1.11 and 1.12) in this question. I separated them from the original theorem ...
1
vote
0answers
121 views

A property of a cyclic order on a ring

Is this property correct? If yes, is there a better way to prove it? If not, what would be an example of a ring that does not satisfy the condition? Theorem. In a ring with non-linearly cyclically ...
1
vote
0answers
68 views

Reference request: the category of adjunctions between posets as categories that induce a partiuclar monad

I am interested in the category $A$ of adjunctions that induce a monad $c : C \to C$ where $C$ is a poset. (The description of $A$ is in a previous math.se post.) For a general $C$, of course, $A$ ...
1
vote
0answers
80 views

A property of an Archimedean cyclically ordered group

I am trying to prove the following property: Lemma (?). For any non-negative element $x$ of an Archimedean cyclically ordered group there is a non-negative element $y$ such that $x + y$ is non-...
1
vote
0answers
133 views

Apex of a cyclically ordered group

Does it make sense to introduce the new definition? Definition 2.1. An element $\pi$ of a cyclically ordered group is an apex of the group iff $\pi = - \pi \ne 0$. Considering an element $x$ of a ...
1
vote
0answers
80 views

Construct a complete and totally ordered field that does not have the least upper bound property.

I have known about the uniqueness of real line. But I am told that it is possible to construct a field which is order and Cauchy complete without the least upper bound property in absence of the ...
1
vote
0answers
58 views

Reduction of $\lambda$-directed colimits

In [Adámek, Rosický - Locally presentable and accessible categories, p59], the authors state in exercise 1.b(2) for infinite cardinals $\lambda_0, \lambda$ if $\lambda_0$ is the cofinality of $\...
1
vote
0answers
16 views

How can I compute the likelihood of a given stochastic order for a set of Gaussian random variables?

Say that I have a set of $k$ random variables $X_{1}, X_{2}, ..., X_{k}$ which are normally distributed with means $\mu_{1}, \mu_{2}, ..., \mu_{k}$ and variances $\sigma_{1}^{2}, \sigma_{2}^{2}, ..., \...
1
vote
0answers
37 views

Supremum of an antichain in countably closed poset

In Kunen's new Set-Theory book, the hint for exercise V.5.13 requires proving the following: Given an atomless countably closed poset, there is an antichain $\{p_n | n\in \omega\}$ such that the ...
1
vote
1answer
185 views

Lattices and incomparable elements

I'm reading about lattices and order relations. I came up with a property that says. $a \land b \lt a$ and $a \land b \lt b$ iff $a$ and $b$ are incomparable. This confuses me up a litle because I ...
1
vote
0answers
117 views

A general formula for automorphism groups of finite Posets?

Every finite poset $P$ may be represented as a direct sum of products of directly irreducible posets, which is to say: $P = \sum\limits_i^n \prod\limits_j^{m_i} P_{i,j}$ where the $P_{i,j}$ are ...