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

0
votes
1answer
70 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
86 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 ...
8
votes
0answers
313 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
116 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
241 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
39 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
37 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 ...
1
vote
1answer
497 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
95 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
287 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
263 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
425 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
99 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
118 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 ...
5
votes
2answers
670 views

Ordering the field of real rational functions

Perusing the Wikipedia article on ordered fields, I encountered an interesting statement, a variation of which I am now trying to prove. Basically, I am trying to show that the set of real rational ...
1
vote
1answer
162 views

Order-reversing bijection on partially ordered sets

Let $(X, \preceq)$ and $(Y, \ll)$ be partially ordered sets. Suppose there are functions $f : X \to Y$ and $g : Y \to X$ such that $$x \preceq g(y) \iff y \ll f(x)$$ for all $x \in X$, $y \in Y$. ...
1
vote
1answer
77 views

Question about suprema/infima of partially ordered subsets

This is another clarifying question; alas, I find myself confused once again by a seemingly innocuous statement in my lecture notes. Let $S$ be a subset of a partially ordered set $(T, \preceq)$, and ...
7
votes
1answer
97 views

Are there any nontrivial doubly-well-ordered sets?

A set $A$ is well-ordered (by an ordering $R$) if there is an $R$-minimal element in every nonempty subset of $A$. Call $A$ doubly well-ordered (by $R$) if $R$ well-orders $A$ and $R^c$ (converse) ...
0
votes
1answer
85 views

Down-set closure of subsets

I am confused by the following statement in my lecture notes on down-set closure of subsets: "The family of down-sets containing a given subset $E \subseteq S$ is nonempty since $E \subseteq S$ and ...
3
votes
2answers
65 views

Question about the definition of the upper set

As I understand it, a subset $L$ of a partially ordered set ($S, \preceq$) is called a down-set or lower set if for any $s \in L$ and $s' \preceq s$, we have $s' \in L$. Now, my question is can we ...
1
vote
2answers
63 views

Notation for “incommensurate” elements?

Say that $x\wedge y\not=x,y$, that is neither $x\leq y$ nor $y\leq x$. Is there a way to denote this? I've been saying $x<>y$ but that's completely made up.
2
votes
1answer
108 views

Some (in)equalities about binary relations

Let $\Phi\subseteq (A\times A)\times(A\times A)$, $F_0,F_1\subseteq A\times A$ (for some set $A$) be binary relations. I will denote $\pi_0$ and $\pi_1$ the projections of a cartesian product of ...
7
votes
0answers
127 views

Reference request - the topology generated by upward and downward closures of antichains.

By definition, the order topology on a totally ordered set $T$ is the coarsest topology such that every subset of $T$ that can be expressed as the upward or downward closure of a singleton is closed. ...
0
votes
0answers
84 views

Direct products in a partially ordered category

Consider a category, whose set of objects is a poset. Let $f=(f_0,f_1)$ is an indexed family of objects of this category. (Thus $f$ is a 2-indexed family, we can extend it to any index set in an ...
0
votes
1answer
62 views

Question about posets and maxima/minima

A thought just occurred to me, thinking about posets and maxima/minima... This is a "little" question just to make sure I am really grasping the definitions here: if $E$ is partially ordered by a ...
0
votes
1answer
91 views

Linear order, Löwenheim-Skolem

LO is the theory of linear ordering. Suppose T a theory, which contains at least the symbol {<} in her language and T $\vDash$ LO. Suppose T has an infinite model. Prove that there's a model M for ...
1
vote
1answer
167 views

A problem with Order-Dense set Definition

I have a problem with the following definition of a order-dense set. Definition: Suppose $\succ$ is a binary relation on an uncountable set $X$. A subset $Z$ of $X$ is called $\succ$-order dense if ...
1
vote
2answers
512 views

equivalence relations and partial ordering

Let $A$ be a set with $6$ elements, $R$ be a relation on $A$ and $n = |\{(x, y) \in A \times A : xRy\}|$. (a) If $R$ is an equivalence relation on $A$, then what is the maximum value of $n$? (b) If ...
3
votes
2answers
571 views

Infinum & Supremum: An Analysis on Relatedness

$\require{color}$ Question: I need some help in proving that $\color{green}{\text{if $k\geq 0$, then $\sup (kS) = k\sup(S)$ and $\inf (kS) = k\inf (S)$}}$, and also that $\color{red}{\text{if ...
2
votes
1answer
236 views

Hausdorff theorem for any linear orders

I read this question: Any good decomposition theorems for total orders? and the answers. I like very much the Hausdorff theorem for scattered linear order. I repeat it here : Theorem (Hausdorff). A ...
3
votes
1answer
72 views

Turning preorders into partial orders

Given a preorder $\preceq$ we can define a partial order $\leq$ as: $x<y$ iff $x\preceq y$ and not $y\preceq x$ $x\leq y$ iff $x<y$ or $x=y$ Transitivity is inherited from $\preceq$, ...
0
votes
2answers
182 views

Definition of dense set

Is this definition is correct?: Let $\preceq$ an order in $A$, $B \subset A$, with $B \neq \emptyset $. Then $B$ is a dense set in $A$ if $$\forall x,y \in A ( x \prec y \to \exists b \in B( x ...
2
votes
3answers
109 views

When we talk of e.g. the natural numbers equipped with a non-standard order , what does “equipped” mean?

A question for "real" mathematicians who have become better acculturated to math-speak than this philosopher! If you read a phrase like ... the natural numbers equipped with the ...
1
vote
1answer
112 views

Show that $X$ is separable.

I'm working through Kunen's Set Theory and I'm not sure how to proceed on part of one exercise. Let $X$ be compact Hausdorff and $\mathbb{O}_X$ be the poset of nonempty open sets of $X$ ordered by ...
2
votes
2answers
141 views

detecting cofinality in ordinals

Suppose K is an unbounded well ordered set, and suppose K is minimal in the sense that each proper initial segment of K has strictly smaller cardinality. Suppose J is an unbounded well ordered set of ...
5
votes
1answer
201 views

Terminology for metric space with “anti-symmetric” distance

I'm interested in spaces that have a two-place function $d$ with non-negative real values, satisfying the following three conditions (for all $x$, $y$, $z$): $d(x, x) = 0$ $d(x, y) + d(y, z) \geq ...
2
votes
2answers
84 views

“intertwined” subset in linearly ordered set

I am trying to solve an exercise in utility representation theory which leads me to the following question. Take any (nonempty) linearly ordered set $(X,\succeq)$. Can we construct a set $Y\subset ...
1
vote
1answer
59 views

Are these two total orders or one partial order?

Please forgive my ignorance here.. I have the following pairs $cd \succ c\bar{d}$ and $\bar{c}\bar{d} \succ \bar{c}d$ defined over the cartesian product of two variables $C=\{c,\bar{c}\}$ and ...
1
vote
1answer
203 views

The classification of order types

In response to a previous question which I asked concerning the order type of the Rationals, a reference was made (by MDJ) to a theorem of Cantor stating that any two countable, dense, linearly ...
0
votes
1answer
89 views

Definition of Dedekind cut as initial segment

the definition of Dedekind cut by initial segment is correct: "let $\preceq$ be a linear ordering of a set $A$, and $B \subsetneqq A$, $B \neq \emptyset$, $B$ is Dedekind cut of $A$ under $\preceq$ ...
1
vote
1answer
377 views

Definition of initial segment

the definition of initial segment is correct: "let $\preceq$ be a linear ordering of a set $A$, and $B \subsetneqq A$, $B$ is initial segment of $A$ under $\preceq$ if $\forall a \in A, \forall b \in ...
0
votes
1answer
48 views

A choice of an ultrafilter in a Rudin-Keisler equivalence class

Given a Rudin-Keisler equivalence class of ultrafilters, is it possible to construct a member of this class without using axiom of choice?
4
votes
1answer
112 views

Is the class of countable posets well-quasi-ordered by embeddability?

The question is in the title. Here "$P$ embeds into $Q$" means there is a function $f : P\to Q$ such that for all $p,p'\in P$, $p \le_P p'$ if and only if $f(p) \le_Q f(p')$. A well quasi order $W$ ...