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

1
vote
2answers
2k views

least-upper-bound and greatest-lower-bound properties

For a partial-ordered set, I was wondering if the least-upper-bound/greatest-lower-bound property means that any nonempty subset that has an upper/lower bound has a least-upper/greatest-lower bound, ...
1
vote
1answer
208 views

Ordinals with the same cardinality

I was wondering how a bijection between two ordinal numbers with the same cardinality is constructed generally? if there is no general solution, some examples please? Since any well-ordered set is ...
4
votes
1answer
165 views

Ideals and filters

The notions of a filter and an ideal on a poset make intuitive sense to me, and I can understand why they are dual: A subset $I\subset P$ of a poset $P$ is an ideal if: for all $x\in I$, $y\leq x$ ...
3
votes
2answers
310 views

Totally ordered abelian group

Let $\Gamma$ be a totally ordered abelian group (written additively), and let $K$ be a field. A valuation of $K$ with values in $\Gamma$ is a mapping $v:K^* \to \Gamma$ such that $1)$ ...
3
votes
3answers
391 views

Number of strict total orders on $N$ objects

Suppose you are given a set of $N$ objects and a strict total ordering relation $<$ satisfying the standard properties (from wikipedia): transitivity: $a < b$ and $b < c$ implies $a < c$ ...
11
votes
2answers
413 views

Any good decomposition theorems for total orders?

I'm learning about set theory and partial orders, well orders, total orders, etc. I'm curious to know of any good decomposition theorems that apply to all (or very general types of) total orders. ...
2
votes
1answer
146 views

What's the name of this function property?

While playing around with least-fixed-point constructions on a powerset lattice, I've found this property to be useful. Let's say that $F : \mathcal{P(U)} \to \mathcal{P(U)}$, and that $A \subseteq ...
9
votes
2answers
2k views

Showing any countable, dense, linear ordering is isomorphic to a subset of $\mathbb{Q}$

I'm trying to knock out a few of the later exercises from Enderton's Elements of Set Theory. This problem is #17, found on page 227. A partial ordering $R$ is said to be dense iff whenever $xRz$, ...
6
votes
1answer
125 views

When do boundedness wrt metric and wrt order agree?

In Wikipedia: A subset $S$ of $\mathbb{R}^n$ is bounded with respect to the Euclidean distance if and only if it bounded as subset of $\mathbb{R}^n$ with the product order. More generally, ...
3
votes
1answer
418 views

topological sort of partial order into sorted sets

Given a partial order of elements, one can use topological sorting to produce a sorted list of elements. For example, if we have the partial order A->B and A->C, then the possible topological sort ...
8
votes
3answers
300 views

With Choice, is any linearly ordered set well-ordered if no subset has order type $\omega^*$?

I've been fumbling around with order types and ordinals these past few days. I read about partial, total, and well-ordered structures, and I'm curious to see if a linearly ordered set has no subset ...
3
votes
1answer
145 views

Alternating permutations with a specified descent set

say that we have two chains of length n, call them $C_1$ and $C_2$.Let us say that the smallest value in $C_1$ is $a_1$, and the smallest one in $C_2$ is b_1. Further, for each element in these ...
5
votes
1answer
730 views

(Extended) Hall's Marriage Theorem from Dilworth's Theorem

This question comes from Exercises III.4.5 and III.4.6 of Bourbaki's Set Theory. They are about using Dilworth's Theorem to prove Hall's Marriage Theorem (did it) and a mild extension of it (can't do ...
1
vote
3answers
545 views

Exchangeability between inf/min and sup/max?

Given any $f: X \times Y \rightarrow \mathbb{R} \cup \{ \infty, -\infty\}$, I was wondering if it is true that $\inf_{x \in X} \sup_{y \in Y} f(x,y) \geq \sup_{y \in Y} \inf_{x \in X} ...
1
vote
1answer
84 views

Is there a general method to order an arbitrary field extension?

Here is something I've been wondering about recently. Suppose you have an arbitrary ordered field $F$, and let $F(\sqrt{a})$ be a field extension with $a>0$ in $F$. Is there then some way to order ...
4
votes
2answers
192 views

Counting and Ordering of Numbers

Are there differences between 'counting' and 'ordering'? As such, the whole of rational number is countable, or they order-able too? In what cases counting and ordering are same or not?
1
vote
1answer
193 views

Möbius inversion formula

Let $X$ be non-empty set and $S$ be the set of all subsets of $X$, which will be a poset, under subset relation. Let $\phi \colon S\rightarrow \mathbb{Z}$ be any function and for each $H\in S$, ...
8
votes
2answers
241 views

Bourbaki exercise about “ramified” ordered sets

This is Exercise III.2.8 of Bourbaki's Theory of Sets. An ordered set $E$ is said to be ramified if, for each pair of elements $x,y$ of $E$ such that $x<y$, there exists $z>x$ such that $y$ and ...
3
votes
1answer
234 views

Rudin–Keisler equivalence

Wikipedia says that if $a\le b$ and $b\le a$ in Rudin–Keisler order for ultrafilters $a$ and $b$, then $a$ and $b$ are Rudin–Keisler equivalent. How to prove this?
5
votes
1answer
1k views

limsup and liminf of a sequence of points in a set

My ways to define/write limsup and liminf of a sequence of points in a set $X$: They come from what I have understood. If you have other ways of understanding, really appreciate if you can reply ...
7
votes
2answers
2k views

limsup and liminf of a sequence of subsets of a set

I am confused when reading Wikipedia's article on limsup and liminf of a sequence of subsets of a set $X$. It says there are two different ways to define them, but first gives what is common for ...
7
votes
2answers
578 views

Is the Knaster-Tarski Fixed Point Theorem constructive?

According to Tarski's Fixed Point Theorem, for a complete lattice $L$, and monotone function $f:L \rightarrow L$, the set of fixed points of $f$ forms complete lattice. Definition of $lfp(f)$ and ...
4
votes
3answers
356 views

questions about well-order

In Wikipedia, well-order is defined as a strict total order on a set S with the property that every non-empty subset of S has a least element in this ordering. But then later, well-order is defined ...
2
votes
1answer
734 views

order and binary relation

Are order and binary relation the same thing, or order is just some special binary relation? If it is the latter, what kinds of properties distinguish an order from a general binary relation? Thanks ...
0
votes
1answer
66 views

In a lattice, ( x ∧ z ) ∧ ( y ∧ z ) = z ∧ ( y ∧ x )

Let ( L, ≤ ) be a lattice, x, y, z ∈ L I am unable to understand why ( x ∧ z ) ∧ ( y ∧ z ) = z ∧ ( y ∧ x ) is mentioned as fact in Y.N. Singh's "Mathematical Foundation of Computer Science" - Pg ...
0
votes
1answer
186 views

In a lattice, $x \leq y$ and $x \leq z \iff x \leq y ∧ z$

Added later: Proof now in progress. Let $(L, \leq)$ be a lattice, $x, y, z \in L$. Prove that $x ≤ y$ and $x ≤ z \iff x ≤ y ∧ z$. I proceed to prove as follows: The statement can be split into ...
0
votes
1answer
154 views

In a Lattice, x ∧ y ≤ x and x ∧ y ≤ y

Let ( L, ≤ ) be a lattice, x, y, z ∈ L. Prove that : $x ∧ y ≤ x$ and $x ∧ y ≤ y$ Here is how I proceeded to solve it: Approach 1 : Proceeding by definition: $x ∧ y ∈$ { x, y } Therefore, x ∧ y ...
6
votes
0answers
113 views

Does order isomorphism of linear extensions of two partially ordered sets imply order isomorphism of themselves?

This question was firstly posted on Mathoverflow. Two answers are pretty interesting. The potential counter-example given in the second answer is really interesting, but it is not surely a ...
4
votes
2answers
287 views

Showing that well-ordered subsets of $P(\omega)$ are countable

I have the following problem: Show that no uncountable subset of $P(\omega)$ is well-ordered by the inclusion relation. I think they want me to do by embedding it in a separable complete dense ...
2
votes
2answers
255 views

Separative Quotients, and the Induced Order

Let $P$ be some partial order. We say that $x$ and $y$ are compatible if $\exists r\in P (r\le x \wedge r\le y)$, we denote this by $x \perp y$. Otherwise, we say that $x$ and $y$ are incompatible. ...
3
votes
1answer
166 views

Showing the Inclusion is sup-continuous

I fear I over simplified the following problem: For any partially ordered set $(A,\leq)$, let $A^* = A- \{\max A,\min A\}$ if $\max A$ and $\min A$ exist. Show the inclusion ...
3
votes
1answer
74 views

For some sets $S\subseteq T\subseteq U$, when is $\inf_T S=\inf_U S$?

I've been struggling with the following problem I found for a while now: Suppose $(T,\preceq)$ is a partially ordered subset of $(U,\preceq)$ and $S\subseteq T$. If $\inf_T S$ and $u=\inf_U S$ both ...
2
votes
1answer
467 views

when inf and sup of a subset achievable in itself?

I was wondering if the following is true: In a topological space with partial order, the inf and sup for a closed subset are achievable inside the subset so that they become minimum and maximum. Is ...