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

2,701 questions
20 views

### Why must a directed complete partial order with an increasing self map F contain a “roof” with respect to F?

I'm trying to solve exercise 8.20 in Davey & Priestley's "Introduction to Lattices and Order". The problem asks me to prove the third CPO fixpoint theorem: If $P$ is a directed complete partial ...
84 views

42 views

### Proving that Zorn's lemma does not imply there exists well-ordered chains that contain their own upper bounds

We have the following statement: Zorn's lemma is equivalent to the following statement: every partially ordered ser $\langle A,<_R\rangle$ has a chain which contains is own upper bounds I have ...
38 views

31 views

### I need to come up with a rule for a set and their relation

2 different Set Relations. I need to come up with a rule for each Relation. R1 = {(a,b) ∈ A x A : rule} where A = {1, 2, 3, 4, 6, 12} I know that they're all positive integer and are divisors of ...
292 views

### Counterexample: a pair of linearly ordered sets that are isomorphic to subsets of the other, but not isomorphic between them [duplicate]

I have encountered myself with the following exercise: Let $\langle A, <_R\rangle$ and $\langle B, <_S\rangle$ be two linearly ordered sets so that each one is isomorphic to a subset of the ...
50 views

### How to understand the proof of the below statement similar to Zorn's lemma?

Proposition: Let $A$ be a partially ordered set such that every chain (total ordered subset) of A has a supremum in A; assume that A has a least element p. Show that there exists an element $m ∈ A$ ...
19 views

57 views

### Suppose R is a partial order on A and S is a partial order on B. Define a relation T on A × B such that (a1, b1) T (a2, b2) iff a1 R a2 and b1 S b2.

Suppose R is a partial order on A and S is a partial order on B. Define a relation T on A × B such that (a1, b1) T (a2, b2) iff a1 R a2 and b1 S b2. Is T a partial order on A x B? So far: R is a ...
22 views

### Example for a po-group

Consider a po-group $(G,\cdot,1,\leq)$ as a small category, a convex normal subgroup $S\vartriangleleft G$ and the group actions of $G$ on $\leq$ via left and right operations. The orbits are of the ...
44 views

### Is there a modified Cartesian product that accounts for order?

Let $f:X\to Y$ be a bijective function. The graph $G(f)$ is given by a subset of the Cartesian product $X\times Y$. Now, given the ordering relation $\preceq_X$ on $X$, it is possible to specify an ...
31 views

### Doubts in demonstrating Tarski's fixed-point theorem

The book I'm using enunciates: $\textbf{Theorem:}$ Let X be set and $\sigma:P(X) \to P(X)$ increasing function $(x_1 \subset x_2 \subset X \Rightarrow \sigma(x_1) \subset \sigma(x_2) \subset X)$ then ...
31 views

### Functions between ordered sets [closed]

Many studies try to define functions between ordered set and prove monotoniciy of such functions. What are the possible benefits of such functions without considering that they are always increasing ...
60 views

### Dedekind cut/additional property

Consider the following lemma and its proof. My question follows. Let $(P,<)$ be a dense unbounded linearly ordered set. Then there is a complete unbounded linearly ordered set $(C,\prec)$ such ...
35 views

### Does 'a graph is a DAG $\iff$ there exists a topological sorting' hold for graphs with a non-finite number of nodes?

Does 'a graph is a DAG $\iff$ there exists a topological sorting' hold for graphs with a non-finite number of nodes? I see this statement at a lot of places e.g. wiki. However it is not specified ...
47 views

### Maximal and minimal element in preordered set

Generally the notion of maximal and minimal element is defined in a partially ordered set (binary relation is reflexive, antisymmetric and transitive). A preorder is a binary relation that is ...
59 views

### When is the Subgroup Lattice Graded?

Let $G$ be a finite group. We say that the lattice of subgroups of $G$ is graded if it is possible to assign a non-negative integer rank $r(H)$ to each subgroup $H$ in such a way that the following ...
23 views

### Preserving relations and operations in an automorphism

An automorphism is an isomorphism of an algebraic structure with itself. Let's review an isomorphism $i$ of two linearly ordered groups $G(+,<)$ and $F(*,<)$. $i$ is linear order-preserving ...
43 views

### What is a cut pair in partially ordered class?

I haven't understood the definition of a cut in POSET. Let $A=\{1, 2, 3, 4, 5, 6, 7\}$. Which of the following is a cut ? a) $\{\{1, 2, 3\}, \{4, 5, 6, 7\}\}$ - Separates such that no element in ...
50 views

### Question about totally ordered family of open subsets of a topological space.

Suppose $X$ is a topological space, $\{U_i|i\in I\}$ is a family of open subsets of $X$, which is totally ordered: that means for any $i,j\in I$, either $U_i\subset U_j$ or $U_j\subset U_i$. Denote by ...