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

3
votes
1answer
128 views

Is every discrete topological space orderable?

I apologize for asking a question in topological terms when it's not really about topology, but here goes: If $S$ is a set, is it always possible to totally order $S$ so that every non-minimal ...
5
votes
3answers
262 views

Determine if the following is a partial order, and if so, is it a total order?

I'm having trouble figuring out how I can solve this... I've never been good with formal proofs. $$(\mathbb{R},\preceq), a\preceq b\iff a^{2}\leq b^{2}$$ I can easily see that it's Reflexive: ...
1
vote
2answers
111 views

inf and min in partial order

Assume $P$ is a partial order. Does it holds that $\inf (\inf(a,b), \inf(c,d)) = \inf(a,b,c,d) $? My guess is that it holds. But I don't know how to check it. Also what if instead of $\inf$ I use ...
2
votes
1answer
136 views

Constructing an order-preserving function between two strict p.o.s that is not one-to-one.

Out of Winfried Just and Martin Weese's Set theory book: Give an example of strict partial orders $\langle X,<_x\rangle$ and $\langle Y,<_y\rangle$ and of a function $\tau : X \to Y$ that is ...
0
votes
0answers
197 views

From point-wise to essential supremum of a set of real-valued measurable functions

I want to prove some property about essential suprema and I think I can show them for the pointwise supremum $\sup S$. The problem is, that the sets involved are uncountable and thus, the point-wise ...
6
votes
1answer
74 views

What are ideals in a complete lattice?

If I have a complete lattice $L$, what conditions do I need for $I\subseteq L$ to be an ideal? In a general lattice the conditions are: $I$ is a lower set; $I$ is closed under (finite) joins. For ...
0
votes
2answers
49 views

Why am I getting that minimal elements are equivalent to the minimum?

I have these two definitions, about minimals and minimums in an order relation: $b$ is minimal in $B<=>¬\exists:(x \in B \land x \prec b)$ and also equivalent to $ \forall x,[(x \in B \land x ...
2
votes
1answer
120 views

Total Ordering and relation

Consider the relation $<$ on $\mathbb{Q}$ defined by: $(m, n) < (j, k) \iff jn-mk \in \mathbb{N}.$ Where $m, j \in \mathbb{N}$ and $n, k\in\mathbb{Z}$ I want to show that $<$ is a total ...
0
votes
1answer
104 views

Theorem unique bijection between two well-ordered sets satisfying certain conditions

I have some problems understanding the proof of the following theorem. Given two well-ordered sets $(X, \le _X), \ (Y, \le _Y)$ there exists exactly one partial function $f(X, Y)$ such that: 1)$f: \ ...
1
vote
1answer
200 views

Width of a product of chains

Write $E_k = (\{0, \ldots, k-1\}, \leq)$ the total order on $k$ elements. If $(A, \leq_A)$ and $(B, \leq_B)$ are two posets, the product poset is $(A \times B, \leq_{A \times B})$ with the order ...
1
vote
2answers
418 views

Infimum/Supremum of an intersection of subsets of a vector space.

Consider a collection of subsets $A_i$ of an ordnered vector space or field. I am trying to find out, under what (minimal) conditions the following holds. $\inf \bigcap_{i\in I}A_i \le \sup_{i\in ...
2
votes
2answers
128 views

Embedding ordered number fields into $\Bbb R$

Consider a number field $K$ equipped with a total order $\le$. Is there always a field homomorphism $\phi:K \rightarrow \Bbb R$ which respects the total order, i. e. with $\phi(x)>\phi(y)$ for ...
3
votes
1answer
134 views

Robertson-Seymour fails for topological minor ordering? (I.e., subgraphs and subdivision)

The Robertson-Seymour theorem says that the set of isomorphism classes of finite graphs, with the minor ordering ($G \le H$ if $G$ is a minor of $H$) is a well partial ordering (it is well-founded and ...
1
vote
1answer
118 views

Atomic Boolean lattice is weakly atomic

The book "Introduction to Lattices and Order" says at Exercise 10.12 that an atomic Boolean lattice is weakly atomic. Could you tell me why it holds?
2
votes
1answer
58 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
1
vote
2answers
180 views

Is the topology generated by the open intervals of a partially ordered set necessarily T_0?

Let $X$ denote a set and consider a collection $C \subseteq \mathcal{P}X$. Let $\mathcal{T}$ denote the set of all topologies $T$ on $X$ such that $C \subseteq T$. Then $\bigcap \mathcal{T}$ is a ...
2
votes
1answer
120 views

Standard notation for the the collection of all *minimal* elements of the set of all upper bounds?

Let $(P,\leq)$ denote a poset and suppose $X \subseteq P$. Then the minimum element of the set of all upper bounds of $X$ can be denoted $\operatorname{sup} X$, or $\bigvee X$. Is there a similar ...
5
votes
2answers
267 views

Motivation for a new definition of the derivative using the concept of average velocity

As everyone knows, for a function $ f: \mathbb{R} \to \mathbb{R} $ and a point $ a \in \mathbb{R} $, we say that the derivative of $ f $ at $ a $ equals $ L $ if and only if $$ \lim_{x \to a} ...
6
votes
3answers
172 views

Incomparable subsets of real numbers with usual order relation

Consider linear order $(R,<)$, would there be two sub-orders $(X,<), (Y,<)$ of it such that $X,Y$ are uncountable, which are incomparable in the following sense: There does not exist order ...
1
vote
1answer
396 views

How to understand the duality between Dilworth's theorem and Mirsky's theorem?

Dilworth's theorem states that for any partial order, the size of the largest antichains is the size of the smallest chain partitions. Mirsky's theorem states that for any partial order, the size of ...
3
votes
1answer
460 views

Isomorphism from $\mathbb{R}$ to $(-1,1)$

There are many bijective functions that map $\mathbb{R}$ to $(-1,1)$, in particular: $$f\left(x\right)=\frac{e^{2x}-1}{e^{2x}+1}$$ (Of course there are others, such as ...
2
votes
2answers
174 views

Is $L$ order isomorphic to $\mathbf{R}$?

Let $L$ be a linearly ordered set which is equinumerous to $\mathbf{R}$, and $L$ is order dense,which means that for every $x,y\in L$,if $x<y$ ,then there is a $z$ such that $x< z < y$. And ...
0
votes
1answer
69 views

On the alphabetical order of monomial

I found this definition of alphabetical order for monomials in $k[x_1,\ldots,x_n]$. We say that $x_1^{a_1}\cdots x_n^{a_n}>x_1^{b_1}\cdots x_n^{b_n}$ if for the least $i$ such that $a_i\neq b_i$ we ...
0
votes
1answer
558 views

Every finite partially ordered set has a maximum length chain.

Every finite partially ordered set, $(A, \leq)$, has a maximum length chain. A chain is a sequence of distinct elements $a_1 \leq a_2 \leq .......\leq a_n$ with relation $"\leq"$ where $a_i \in A$ ...
5
votes
2answers
391 views

If every nonempty subset of a set $S$ has a least and greatest element, is $S$ finite?

Some sets are well-ordered; all of their nonempty subsets have least elements. You can also have sets where all of their nonempty subsets have greatest elements. Some sets have both of these ...
1
vote
3answers
122 views

Question regarding well-ordering theorem

The well-ordering theorem states that every set can be well-ordered. That is, there is a total order on the set in which every non-empty subset has a least element. I was wondering whether it's also ...
5
votes
2answers
251 views

Showing there is only one isomorphism between well ordered sets using transfinite induction

I need to show specifically using transfinite induction that given two well-ordered sets $\left(A,<_{1}\right)$ and $\left(B,<_{2}\right)$ there is only one isomorphism between them. To do ...
3
votes
2answers
90 views

Class of structures isomorphic to $(\mathbb{Z},<)$ in infinitary logic $L_{\omega_1 \omega}$

We want to define the class of all structures isomorphic to $(\mathbb{Z},<)$ in the infinitary logic $L_{\omega_1 \omega}$. Therefor we define strict order as usual: $\forall x,y,z ~~ (x<y ...
3
votes
1answer
395 views

Question about Hausdorff Maximal principle and antichain

I have this prob and still haven't figured about Let (A, $\leq$) be a partially ordered set. A subset B of A is called an antichain if and only if for any two distinct elements x and y in B, ...
0
votes
1answer
167 views

Proving of existence of limit ordinal

How to prove that for every ordinal $\alpha$ there exist limit ordinal $\beta$ ,such that$\alpha\in\beta$ ? Thank you.
0
votes
1answer
72 views

Different definitions of (anti-)exchange for a closure operator

Wikipedia article for matroids says For all elements $a$, and $b$ of $E$ and all subsets $Y$ of $E$, if $a\in\operatorname{cl}(Y\cup b) \setminus Y$ then $b\in\operatorname{cl}(Y\cup a) ...
7
votes
3answers
276 views

Help me get hyped about lattices

I own a small book on Lattice theory published by Dover. Unfortunately, since I bought it almost a year ago, I have gotten nowhere in its study. What I am asking for are freely available papers that ...
13
votes
2answers
2k views

Every partial order can be extended to a linear ordering

How do I show that every partial order can be extended to a linear ordering? I think that I manage to prove that claim for finite set, how can I prove it for infinite set? Thank you.
2
votes
1answer
44 views

breadth of join-semilattice

On page 16, Lattice Theory: Foundation, George Grätze(2011), 1.19 Show that a join-semilattice $(L; \lor)$ has breadth at most $n$, for a positive integer n, iff for every nonempty finite subset ...
6
votes
1answer
85 views

Are these two subsets of a poset already named?

In a partially ordered set $(X,≤)$, an upper set of a partially ordered set $(X,≤)$ is a subset $U$ with the property that, if $x \in U$ and $x≤y$, then $y \in U$. The dual notion is lower set, ...
7
votes
1answer
146 views

Least common fixed-point

I have been reading a book, "Introduction to Lattices and Order", and I'm trying to solve exercise 8.29 as the following in it: Suppose that $P$ is a complete lattice and let $F$ and $G$ be ...
6
votes
1answer
313 views

Order embedding from a poset into a complete lattice

Let $\mathfrak{A}$ is an arbitrary poset. Does it necessarily exist an order embedding from $\mathfrak{A}$ into some complete lattice $\mathfrak{B}$, which preserves all suprema and infima defined in ...
1
vote
2answers
185 views

Inverse of order preserving transformation

Suppose $\left(A,\leq_{A}\right)$ and $\left(B,\leq_{B}\right)$ are Posets and $f:A\to B$ is an order preserving bijection. I'm trying to show that $f^{-1}:B\to A$ is also order preserving. ...
1
vote
0answers
62 views

Order relation with reversed order definition

I am trying to solve this exercise, but it is kind of confusing to me because the order relation involved "reverses" the standard order. Let $\tau$ a binary relation over $\mathbb N$ defined as ...
3
votes
1answer
134 views

New attempt to prove Dilworth Theorem

Moving from that question to this new one due to space reasons, here there is a new attempt to prove the theorem that (I hope) take into account the feedbacks of Thomas Andrews. Theorem (Dilworth, ...
3
votes
1answer
268 views

Special Galois connections

Let $(f;g)$ is a Galois connection between two posets. Consider the special case $g\circ f = \operatorname{id}_{\operatorname{dom} f}$. What can be said about this special case of Galois ...
-1
votes
1answer
24 views

Does consistency of a test imply continuity of a preorder?

Let $F$ and $G$ be two real-valued probability distributions, considered as cadlag functions with the uniform norm [not the Skorohod metric], and let $\mathbb{F}_n$ and $\mathbb{G}_m$ be empirical ...
0
votes
1answer
142 views

Is this a sound proof of Dilworth Theorem?

This is my first attempt to prove something a bit more serious than the usual trivial stuff. But I am not sure I actually proved the result. Does the following work? Theorem (Dilworth, 1950): Every ...
0
votes
2answers
617 views

Dedekind Cuts - Additive and Multiplicative Identities

I wanted to receive some help regarding some homework questions; I appreciate any sort of feedback possible. I am certain that any Dedekind Cut $A$ has the following properties: 1) $A$ is not the ...
2
votes
2answers
229 views

Well-Ordered Sets and Functions

I need some assistance with the following problems. I've come up with some ideas but may need some clarification. 1) Let $S$ be a well-ordered set. a) Need to show $S$ has a first element. ...
16
votes
6answers
2k views

Is the set of real numbers the largest possible totally ordered set?

Because I find any totally ordered set can be "lined up" in a straight line, I'm guessing that the set of all the real numbers is the biggest totally ordered set possible. In the sense that any other ...
1
vote
1answer
54 views

Is any set that has a preorder is a directed set?

In the definition of directed set, they emphasized that aside from it having a preorder, "every pair of elements has an upper bound." My question is that isn't the latter property implied by the ...
2
votes
2answers
110 views

What kind of POSET whose chain can be unbounded?

On Page 32, Set Theory, Jech(2006): Let $\kappa$ be a limit ordinal. A subset $X \subset \kappa $ is bounded if $\operatorname{sup}{X} < \kappa$, and unbounded if $\operatorname{sup}{X} ...
5
votes
1answer
239 views

Chain of length $2^{\aleph_0}$in $ (P(\mathbb{N}),\subseteq)$

How can I find a chain of length $2^{\aleph_0}$ in $ (P(\mathbb{N}), \subseteq )$. The only chain I have in mind is $$\{\{0 \},\{0,1 \},\{0,1,2 \},\{ 0,1,2,3\},...,\{\mathbb{N} \} \}$$ But the ...
6
votes
1answer
208 views

Extending a partial order to antichains

Let $(S, \leq)$ be a partial order. Let $T$ be the set of antichains of $S$ (i.e., subsets of $S$ whose elements are pairwise incomparable). Define a relation $\leq'$ on $T$ as follows: for all $A$, ...