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

Problem on distributive lattice

Let $L$ be a distributive lattice, denote $upper(x)$ - a set of elements which cover $x$ (to be clear: $y$ covers $x$ if $x < y$ and there is no element $z$ such that $x < z < y$), $lower(x)$ ...
1
vote
0answers
43 views

Quadrants of a cyclically ordered group

I am trying to prove that if there are two different positive elements in a non-linearly cyclically ordered group, then every quadrant of the group is not empty. Is this a correct statement? ...
2
votes
0answers
23 views

How can we show that the $k$th order statistic is measurable?

Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space $(E,\le)$ be a partially ordered set and $\mathcal E$ be a $\sigma$-algebra on $E$ $n\in\mathbb N$ $X_1,\ldots,X_n:\Omega\to E$ be $(\...
4
votes
0answers
68 views

Classifying the chains of orderable sets' power sets up to isomorphism

Recently, while trying to understand another result, I began to wonder about the following question: Given some orderable set $A,$ what (if anything) can we conclude about the order type or ...
0
votes
1answer
25 views

The cartesian product of a well-ordered set with $[0,1)$ is a linear continuum in dict. order

Definition: A linear continuum is a simply ordered set $L$ such that: (1): $L$ has the least upper bound property; (2): For every $x<y$ in $L$ there is a $z$ sucht that $x<z<y$. I ...
2
votes
1answer
34 views

Finding an order isomorphism from $\text{On}\times\text{On}$ to $\text{On}$

Let $\text{On}$ be the class of all ordinals and let $\leq_{\text{c}}$ be the canonical well-ordering on $\text{On}\times\text{On}$. More specifically, $\preceq$ is defined as follows. Let $\left(\...
1
vote
0answers
52 views

Given a poset with a join such that any pair has a meet, find a total order with a special property.

Let $(A,\geq)$ be a partially ordered set such that there exists the join $\bigvee A$, i.e. $a\in A$ such that $a\geq b$ for any $b\in A$; for any pair $(b,c)\in A\times A$ there exists the meet $b \...
-1
votes
1answer
16 views

If Y is a subset of X, is always true that then Y inherits (always) a total order from X?

If Y is a subset of X, then Y inherits a total order from X. The set Y therefore has an order topology, the induced order topology What does it mean "inherits" ? Is this a a Kripke model M ...
0
votes
1answer
29 views

Sentence satisfied by parity ordering and unsatisfied by natural ordering

Let $>_1$ be the natural ordering on $\mathbb{Z}_{>0}$ and $>_2$ be the ordering on $\mathbb{Z}_{>0}$ with $m>_1n\Leftrightarrow m>_2n$ for all $m$ and $n$ of the same parity and $m&...
0
votes
1answer
24 views

What do we call a “nearly” order-isomorphism?

Suppose $f:X\to Y$ preserves $x_1\geq x_2\implies y_1\geq y_2$ but does not necessarily preserve $x_1> x_2\implies y_1> y_2$. In other words, an $f$ satisfying this relation might, upon ...
1
vote
0answers
42 views

Archimedean totally ordered ring with zero divisors

Investigating the Existence of totally ordered ring with zero divisors, I've got an interesting result: If an Archimedean totally ordered ring (or rng) has a nonzero zero divisor, then $ab = 0$ for ...
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
78 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
49 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
40 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
21 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
34 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
17 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
36 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
32 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
38 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
37 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
241 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
58 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
30 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
289 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
49 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
51 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
561 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
41 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
25 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
65 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
91 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
41 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
30 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
46 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
58 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
27 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= ...
0
votes
1answer
45 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
21 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
43 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
30 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 ...