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.

learn more… | top users | synonyms

2
votes
1answer
187 views

Counting certain partitions of integers

[Recall that] Young's lattice is a partially ordered set in which all partitions of integers are ordered thus: The elements just one step below any partition are those that you can get by subtracting ...
0
votes
1answer
37 views

Does every tree have an upper portion that is a non-empty chain?

Given a poset $P$, call $A \subseteq P$ an upper portion iff $A^c < A$, by which I just mean that for all $a \in A^c$ and all $b \in A$ we have that $a < b$. Then every upper portion is upward ...
11
votes
3answers
6k views

A finite set always has a maximum and a minimum.

I am pretty confident that this statement is true. However, I am not sure how to prove it. Any hints/ideas/answers would be appreciated.
18
votes
2answers
1k views

Order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$

Do you have a simple example of order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$? On $\mathbb Q$, I use the usual order and on $\mathbb Q\times\mathbb Q$, I define the ...
0
votes
1answer
124 views

Is this poset a lattice?

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation $$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
0
votes
1answer
60 views

What is the terminology for this type of order-preserving function?

As I roughly know, a function $f$ in $\mathbb{R}$ is called order-preserving if $f(x)>f(y)$ for $x>y$, $x,y \in \mathbb{R}$. May I ask, if anybody knows the terminology for two functions $f$ ...
3
votes
2answers
235 views

Dense and complete totally ordered sets

The totally ordered set $\mathbb{R}$ has the following properties. [Density]. Given any two $x,y \in \mathbb{R}$, we can find $\eta \in \mathbb{R}$ such that $x < \eta < y$. [Dedekind ...
-1
votes
1answer
22 views

partial order and truth value

please,give a formula Q with free variables such that for any partial order ( A ; ≤ ; -) we have that [Q]=1 iff [z] is a join of [x] and [y]
0
votes
2answers
698 views

Example of a strict total order

A strict total order is a set $A$ with a binary relation $<$ on it, satisfying irreflexivity, transitivity and totality. Could you give an example of a strict total order, please?
1
vote
1answer
60 views

Proof of Jordan-Dedekind Chain property for graded posets

I have a question about the following proof. Suppose a partially ordered set $(P,\le)$ is graded by its height function $h$. All chains are finite and there is a smallest element $0$. Then the poset ...
1
vote
1answer
78 views

Question about primitive group actions

In Glass' Partially Ordered Groups Corollary 7.4.4 says: If $G$ is an ordered group and $(G,G)$ is the right regular representation, then $(G,G)$ is primitive if and only if $G$ is ...
0
votes
1answer
118 views

Isomorphism between partially ordered sets - What is wrong with my argument?

I'm trying to show Isomorphism between two partially ordered sets is an equivalence relation. Suppose $M$ and $M^{\prime}$ are two partially ordered set and $f:M\to M^{\prime}$ is isomorphism ...
2
votes
3answers
81 views

A notation for a morphism in a thin category

Consider a thin category with objects $A\leq B$. There exists a unique morphism $A\rightarrow B$. Is there a standard notation for this morphism (given $A$ and $B$)?
1
vote
1answer
16 views

Negation of a maximal element in a partially ordered set

Let $(P,\le )$ be a partially ordered set. We call a $m\in P$ a maximal element, if $$p\in P,m\le p\Rightarrow m=p$$ What is the negation of this property? So we assume $m\in P$ is not a maximal ...
1
vote
1answer
70 views

To show that a given graded function is the height function

My background in order theory is not very strong, and I'm confused about the following. The definition and theorems are from Lattices and ordered sets by Roman: Let $(P,\le)$ be a partially ordered ...
1
vote
1answer
37 views

Left-isolated points in totally ordered set

Let $X$ be a totally ordered set. I say that a point $x$ is "left-isolated" if there is some $\alpha < x$ such that there is only one point $y$ which satisfies $\alpha < y \leq x$, that is, ...
3
votes
1answer
235 views

A set that is transitive but not well-ordered by $\in$?

I am trying to find a transitive set which is not well-ordered by $\in$. This question raises when I read Jech's Set Theory, in which an ordinal number is defined as a transitive and ...
4
votes
2answers
380 views

Given an infinite poset, show that it contains either a infinite chain or an infinite totally unordered set. [duplicate]

Been thinking about this one for awhile and I'm still stuck... Thought about proving it by arriving at a contradiction but I haven't reached anything noteworthy. If you do a proof by contradiction, ...
2
votes
1answer
214 views

If $A$ is well ordered and $B$ is well ordered then $A\times B$ with the lexicographic order is well ordered

I am trying to prove that: Given that $A,B$ are well ordered sets, also $A \times B$ is a well ordered set. (A set $A$ is well ordered if a linear order is defined on it, and every non empty subset ...
0
votes
3answers
138 views

How to show that $ \succ acyclic \implies \succ asymmetric $

For a preference relation defined as $$ \succ := \{ (x,y) \in X\times X : x\ is\ better\ than\ y \}$$ one has to show that $$ \succ acyclic \implies \succ asymmetric $$ whereas $$ acyclic := ...
1
vote
1answer
38 views

Proving a function is order-isomorphic?

Let $A$ be a chain and $B$ be a partially ordered set. Let $f: A \rightarrow B$ be a 1-1 function for which $a \leq b$ implies $f(a) \leq f(b)$. Prove $f$ is order-isomorphic. Let $f: A ...
1
vote
1answer
161 views

Every countable lattice has a cofinal totally ordered subset?

If a lattice is countable, prove that it has a subset that is both totally ordered and cofinal in the lattice. Cofinal means that for each $l$ in the lattice, there is some $a$ in the subset such that ...
4
votes
1answer
112 views

Is a chain complete lattice complete?

If every chain in a lattice is complete (we take the empty set to be a chain), does that mean that the lattice is complete? If yes, why? My intuition says yes, and the reasoning is that we should ...
3
votes
0answers
28 views

Expect size of $k^{th}$ layer of a POSET

Is this known? What is the expected width of the $k^{th}$ layer (anti-chain layer) of a $d$-dimensional partially ordered set of $n$ elements formed by product of $d$ random liner orders chosen from ...
2
votes
1answer
216 views

Why is division on Z not a poset?

Why is division on natural number a poset but division on Z is not a poset? Is is because we get ordered pair such as (-1,1) and (1,-1) which is not antisymmetric?
0
votes
0answers
824 views

Is = (equality) a partial order relation?

We know that a partial order relation is a relation which is reflexive , antisymmetric and transitive. Example: (x,y) belongs to R iff x=y. For A={1,2,3}, we get R= {(1,1), (2,2), (3,3)}. Now R is ...
1
vote
1answer
86 views

Counting Self-dual posets

An exercise in Stanley's Enumerative Combinatorics (Chapter 3, ex. 8) asked for an example of a finite self-dual poset, (i.e. there is a bijection $f: P\to P$ such that $s\le t \Longleftrightarrow ...
0
votes
1answer
298 views

Non-isomorphic countable linear orders which embed into each other

Def: $(A,<) \hookrightarrow (B,\lhd)$ if $\exists f:A \to B$ such that $\forall a,b \in A[a<b \implies f(a) \lhd f(b)]$. May I seek your advice on how to construct two infinite, countable ...
0
votes
1answer
129 views

Prove that $R$ is a linear order on $A\times B$

Assume that $(A,\leq)$ and $(B,\leq)$ are linearly ordered sets. Define a relation $R$ on $A\times B$ by $(a,b)R(c,d)$ iff $a<c$ or both $a=c$ and $b\leq d$. Prove that $R$ is a linear order on ...
0
votes
1answer
71 views

unranking a sequence of all linear extensions of a partially ordered set

Let $P$ be a partially ordered set. Let $E$ be the set of all possible linear extensions of $P$. Let $S$ be the sequence formed by arranging elements of $E$ in lexicographic or graycode order. Does ...
3
votes
2answers
89 views

Why does sup-dense imply inf-continuous?

I am confused. The question is as follows: Let $(S, \preceq$), be a sup-dense subset of $(T, \preceq)$, both partially ordered sets. In other words, for every $t \in T$, there exists a subset $E ...
0
votes
1answer
64 views

A Proof of Posets, how to do it?

I am trying to do a exercise from my book, but I don't understand how to solve it (many statements!)... Here is the exercise: Let $P$ and $Q$ be ordered sets. Prove that $(a_1, b_1)\prec ...
9
votes
0answers
324 views

Proving equivalence of a tree-based version of Countable Choice for families of finite sets.

In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5: Each of the following statements imply those beneath it. The countable union of ...
3
votes
1answer
66 views

Given $A \subseteq X$ we can have $\sup A < \inf A$?

For some poset $(X,<)$ with a global max $\top$ and min $\bot$ with $\bot < \top$, and a subset $A = \varnothing$, we'd have $\sup \varnothing = \bot$ and $\inf \varnothing = \top$, right? So ...
0
votes
2answers
119 views

What is an order reversing bijection on $\Bbb R$?

What is an order reversing bijection on $\Bbb R$ and why must it be continuous? Thanks
2
votes
2answers
132 views

Universality of $(\mathbb Q,<)$

I have few questions to the proof on Universality of linearly ordered sets. Could anyone advise please? Thank you. Lemma: Suppose $(A,<_{1})$ is a linearly ordered set and $(B,<_{2})$ is a ...
2
votes
1answer
66 views

Two definitions of a monovalued morphism

Let fix some dagger category every of Hom-sets of which is a complete lattice, and the dagger functor agrees with the lattice order. I define a morphism $f$ to be monovalued when $f\circ f^{-1}\le ...
9
votes
2answers
243 views

When does a left adjoint between Heyting algebras preserve 1?

This is an exercise from Johnstone's book Stone Spaces: Let $f: A \to B$ and $g: B \to A$ be order-preserving maps between complete Heyting algebras with $f$ left adjoint of $g$. Show that $f$ ...
0
votes
1answer
42 views

lowering of a semilattice

In these Lecture Notes the notion of lowering a semilattice is introduced, there it is stated: Sometimes "broken" elements need to be looked at and computed with. Now any semilattice can have an ...
6
votes
2answers
8k views

Prove that $\sup(A+B) = \sup(A) + \sup(B)$ and why does $\sup(A+B)$ exist?

We want to show that $\sup(A)+\sup(B)$ is the least upper bound of the set $A + B$. First, we need to show that $\sup(A) + \sup(B)$ is an upper bound for the set $A + B$. Indeed, if $z\in A + B$, then ...
0
votes
1answer
38 views

Are ideals of an sup semilattice always non-empty?

I am trying to do an exercise from the book A Compendium of Continuous Lattices. Exercise: Let $L$ be a set with a transitive relation, and let $A,B$ be ideals of $L$. (i) $A\cap B$ is an ideal of ...
2
votes
1answer
553 views

Is convex set interval or ray? [duplicate]

Given an ordered set $X$, say a subset $Y$ of $X$ is convex in $X$ if for each pair of points $a<b$ of $Y$, the entire interval $(a,b)$ of points of $X$ lies in $Y$. An interval is of the form ...
2
votes
1answer
96 views

Equality and order in sets

Just started Baby Rudin and got struck in this. While defining order in sets, $<$ was introduced as a relation and for a set to be ordered the condition was: for all $x,y$ belonging to an ordered ...
0
votes
1answer
317 views

Partial order relation

Define the relation $\leq$ on a boolean algebra $B$ by for all $x,y\in B$, $x\leq y \iff x\lor y=y$, show that $\leq$ is a partial order relation. First of all what exactly does boolean ...
0
votes
2answers
291 views

Proving well ordering is total relation

Assuming R is well-ordered relation on a set A. Wikipedia claims that every well ordered relation is also a total one.Even tough in first sight it seems trivial, how can I prove it?
4
votes
1answer
441 views

In a complete lattice every monotone function has a fixpoint (Knaster–Tarski Theorem)

L is a complete lattice, so every subset has a supremum and infimum. In addition, there exists a function $f:L \rightarrow L$ such that $a \leq b$ implies $f(a) \leq f(b)$. Prove that there exists ...
0
votes
1answer
30 views

Order embedding and graph embedding of Hasse digraphs

If there is an order embedding from order A to order B, is there a graph embedding between their Hasse digraphs? What if we replace 'embedding' by 'order preserving' and 'homomorphism' etc?
3
votes
2answers
102 views

Finitely many minimal elements

I've been working on various exercises to get a better understanding of some topics for an upcoming course. I have a relation $R$ on $\mathbb{N} \times \mathbb{N}$ defined as follows: $(x_0, x_1) R ...
2
votes
2answers
76 views

Help with elementary question involving a partially ordered set.

Let N with divisibility be a partially ordered set. Show that any 2 element subset of N has a greatest lower bound and a least upper bound. I seem to keep going in circles, but I have the idea that ...
3
votes
1answer
123 views

Where can I learn more about order-reflecting functions? And is the following result well-known?

I stumbled across a cute result about order-reflecting functions. A couple of questions: Is the following result well-known? I know lots of place to learn about order-preserving functions, but is ...