Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
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 ...
4
votes
2answers
84 views

Why are ordinals multiplied in reverse order

When two ordinals, $\alpha$ and $\beta$, are multiplied together, $\beta$ is taken as the most significant multiplicand and $\alpha$ as the least significant multiplicand in the product $\alpha \cdot \...
1
vote
1answer
39 views

Confusion about Reflexive, symmetric, anti-symmetric and transitivity

So some equations are easy to understand and figure out. But, my lack of understanding of the basic info makes a lot of questions very hard: for reflexive its pretty easy all i have to do is change y ...
2
votes
1answer
50 views

Order preserving injection $f$ from set of rationals $Q$ into $R$ with discrete image.

How to construct an order-preserving injection $f:Q\rightarrow R$ , such that the image of $f$ is discrete subspace of $R$ (set of reals).
2
votes
0answers
41 views

Recursive way of calculating cofinality of ordinals

I was trying to understand why A regular ordinal is always an initial ordinal. and in the course of this, came to the following hypothesis. For any ordinals $\alpha$ and $\beta$ such that $$\...
0
votes
1answer
24 views

Help on Proving Reflexive, Symmetry and Transitivity for xy>= 1, with relation r E Z , xy E integers,IF AND ONLY IF xy >= 1

My working so far that: Reflexive: Yes as suppose x E in r, we get x^2 >= 1 which true for all so this is true. Symmetric: I think it is true since xy >= 1 and xy = yx order not important? ...
0
votes
0answers
35 views

Assuming a deductive theory is an ordered set of propositions, how could its order be defined mathematically ? Is it, for example, a lattice?

In this You Tube video, at 3:39 : https://www.youtube.com/watch?v=enZpq8jvFEs Monsieur Phi ( understand " Monsieur Philosophie") a philosophy teacher ( and also a logician) gives a visual ...
0
votes
2answers
19 views

Definition of similarity mapping between ordered sets: why is a “ strictly precedes” relation required on each side of the biconditionnal?

As a definition of " similarity mapping" I read in Lipschutz, Set Theory : the mapping f from A to B ( A and B being ordered sets) is a similarity mapping iff, (a) f is a bijection and (b) for any ...
0
votes
1answer
18 views

Does there exist a pairing function which preserves ordering?

Suppose we define a total order on pairs of integers where $(x_1, y_1) > (x_2, y_2)$ when $x_1 > x_2 \lor (x_1 = x_2 \land y_1 > y_2)$, i.e., first comparing the first element and then ...
-1
votes
1answer
37 views

Minimal Transitive Closure

Any binary relation over any set (finite or infinite) must has a transitive closure. Moreover, every binary relation must has a minimal transitive closure. Who proved this well-known result in ...
0
votes
0answers
35 views

Natural unwound of a cyclically ordered group

The Rieger's unwound (https://arxiv.org/pdf/1311.0499.pdf) of a cyclically ordered group $G(+)$ is the Cartesian product $\mathbb Z \times G$ with a binary operation defined as: $(m, a) + (n, b) =$ $...
0
votes
1answer
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 ...
0
votes
2answers
38 views

Finding maximal chain and maximal anti-chain in partially ordered set

We define $R$ on $\mathbb{N}^\mathbb{N}$ such that: $\forall f,g:\mathbb{N}\to \mathbb{N}$, $fRg$ if and only if $\forall n\in \mathbb{N}, f(n)\leq g(n)$. Then, $R$ is partially ordered set on $\...
0
votes
0answers
24 views

Three dimensional representation of a set

A graph $G$ with vertex set $V$ has $\dim(G) \leq d$ if and only if there exists a sequence $<_{1},<_{2}, \ldots , <_{d}$ of total orders on $V$ satisfying the following conditions: the ...
4
votes
2answers
242 views

Why does the set $\{1,3,5,7… ; 2,4,6,8…\}$ qualify as well-ordered? How to explain this notation?

The set {odd natural numbers greater than 0 }U {even natural numbers} that is, the set $\bigcup \{ \{1,3,5,7...\}, \{2,4,6,8...\} \}$ also strangely written $\{1,3,5,7... ; 2,4,6,8...\}$...
1
vote
0answers
65 views

Natural cut of a cyclically ordered group

It is well known that a cyclically ordered set may have more than one cut. I am trying to prove that a cyclically ordered group cannot have more than one cut compatible with the group operation. Is ...
3
votes
1answer
24 views

Is There A Name For This Type Of Partially Ordered Set

Suppose that $\langle P, \leq , \bot \rangle$ is a partially ordered set (poset) with least element $\bot$. Is there a commonly usedname for a poset that satisfies: For all $p, q \in P$ such that $p, ...
1
vote
1answer
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 ...
7
votes
1answer
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 ...
-2
votes
1answer
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$ ...
1
vote
1answer
19 views

Prove if there is no strictly decreasing sequence of elements in linear order A, then A is well ordered [duplicate]

I managed to quite easily show the reverse direction $\Leftarrow$, but the following direction is giving me a lot of problems: no strictly decreasing sequence of elements in linear order $A$ $\...
1
vote
1answer
58 views

Determine which pairs of linearly ordered sets are order isomorphic

Hi I've got an exam this Saturday and I don't understand this question at all. Could someone please explain it to me please? It would be much appreciated. Here is the question: and here is the ...
4
votes
5answers
586 views

Combinatorics problem, right solution?

We have $6$ lawyers, $7$ engineers and $4$ doctors. We plan on making a committee of $5$ people, and we want at least one person of each profession on board. So for the first place I choose an ...
0
votes
1answer
45 views

How to Compute the Pareto-front of this set? [closed]

I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst ...
0
votes
1answer
35 views

In an infinite linearly ordered set every initial section is finite. ¿Is it isomorphic to $\langle\mathbb{N}\,,\,\text{<}_{\mathbb{N}}\rangle$? [duplicate]

As the title of the question suggests, if $\langle A\,,\,<\rangle$ is an infinite linearly ordered set such that for each $a\in A$, the initial section $\text{sec}(a,A,<)$ is a finite set, ¿is ...
1
vote
2answers
68 views

Adjoint of the inclusion functor from Preord to Cat

Suppose $F : Preord \to Cat$ is the inclusion functor. Suppose that $G : Cat \to Preord$ is the functor which maps each category $C$ to its associated preorder (each object is an element and $X \leq Y$...
5
votes
1answer
95 views

How can I compute the 'average rank' of an infinite set?

Note: I will use $\in^n$ will to indicate that an object "is an element of an element of an..." of a set. e.g. $x\in^4 X$ means that there exist $X_1,\ldots,X_3$ such that $x\in X_1\in X_2\in X_3\in X$...
0
votes
0answers
44 views

Boolean Algebra: Demonstrate that the pentagon lattice is non-distributive

I just started learning Boolean Algebra and have this homework question Demonstrate that the pentagon lattice is non-distributive I know this is non-distributive because $b$ complements $a$ and ...
0
votes
0answers
17 views

Lexicographical order in context of identifiability of mixture of two Normal distributions

I want to understand a method used in a paper on identifiability of mixture of two Normal distributions. This is Teicher 1963 "Identifiability of finite mixtures", fragment of the proof The author ...
0
votes
1answer
32 views

Directed set and partially/totally ordered sets.

I am barely new to order theory and this motivates if the question is trivial. I understood the definitions of preorder, partially and totally ordered sets and well ordered sets. In particular there ...
0
votes
1answer
41 views

Counterexample: linearly ordered sets for which there exists more than one isomorphism

In my axiomatic set theory notes, there appears that, if $A$ and $B$ are well-ordered isomorphic sets, then there exists one isomorphism between them. However, as a side note, it is stated that this ...
0
votes
1answer
47 views

Math theory that deals with ordered attr-value items?

There is partially ordered sets and lattices. Is there a branch of math that deals with ORDERED Attribute-Value items/objects. F.e. av-items /see that attrs also can be missing i.e. doors&roof/ : ...
0
votes
1answer
60 views

Proving isomorphism between two sets

Let A and B be two sets. Let 𝑓: A→B be a one to one correspondence. Show that (P(A),⊊) and (P(B),⊊) are order isomorphic. I am kinda lost with this question. How can I prove that these two are ...
1
vote
0answers
28 views

Rewriting a set of integers to get rid of repetition but keeping subset sum ordering

Say, I have a set of 6 +ve integers sorted in ascending order: $A = \{2,4,4,4,5,7\}$ Now to make it easier to deal with (Minimum one starts with 1) I deducted one from all of them: $\therefore B= ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
1
vote
0answers
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 ...
-1
votes
2answers
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 ...
9
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
31 views

Reference for convex partitions

I am looking for a reference for the following result: Let $(X,\leq)$ be a linear order and let $\Pi$ be a partition of $X$ into convex subsets. Then the relation $x\preceq y$ defined by $\forall P,...
0
votes
1answer
57 views

Definition of Order in real Analysis

In Walter Rudin's Principle of Mathematical Analysis 3ed, what's the difference between $<$ sign, which is used to denote the order relation and $<$ sign, which is used to compare $x$ and $y$ in ...
1
vote
2answers
32 views

What is this notation $( \mathbb{N},|)$

My book has this notation for examples of a poset $( \mathbb{N},|)$ and $(\mathbb{Z^*},|)$ and I need to verify it if it is a partially ordered set. Can someone tell me how to read this notation?
-2
votes
1answer
19 views

Prove that the partial order ((D * D), ⊆) is a complete partial order with bottom.

Let D be a non-empty set and (D-->D) be the set of all partial functions from D to D. Prove that the partial order ((D--> D), ⊆) (i.e., the set of partial functions ordered by set inclusion) is a ...