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

6
votes
1answer
103 views

A new(?) partial order on the set of continuous maps

Let $X,Y$ be topological spaces. Define a partial order on $\hom(Y,X)$ as follows: $f \leq g$ if $f^{-1}(U) \subseteq g^{-1}(U)$ for all open subsets $U \subseteq X$. Equivalently, $f(y)$ is a ...
9
votes
2answers
244 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
2
votes
3answers
114 views

Confused about preservation of well-quasi-orders

I don't understand preservation of well quasi-orders, here is what I have thought about: Definition A binary relation $R$ on $X$ is a quasi-order when it is reflexive and transitive. Definition A ...
3
votes
1answer
98 views

Existence of a minimal set of linear order that is equivalent to the given partial order

Let $\{(P, \leq_{\alpha})\}_{\alpha \in A}$ be a set of linear order on set $P$, $(P,R)$ be a partial order on the same set $P$. We say that the former is equivalent to the later, iff: $$\forall a, b ...
8
votes
3answers
410 views

Ordinal exponentiation - $2^{\omega}=\omega$

This is my understanding of ordinal arithmetic - two ordinals are the same as one another if there is an order-preserving bijection between them. So for instance $$1+\omega = \omega$$ because if ...
1
vote
2answers
795 views

How is GLB and LUB different than the maximum and minimum of a poset?

As the subject asks, how is the greatest lower bound different than the minimum element in a poset, and subsequently, how is the least upper bound different than the minimum? How does a set having no ...
2
votes
1answer
46 views

Can infinite joins/meets be viewed as special cases of a limit with respect to some topology?

Let $L$ denote a complete lattice. Is there a topology on $L$ such that infinite joins and meets can be viewed as a special kind of "limit"?
1
vote
1answer
68 views

Two topologies generated by a partially ordered set - are they equal? Are they $T_0$?

Let $P$ denote a partially ordered set, and consider two topological spaces with carrier $P$. The topological space whose closed sets are generated by the upsets and downsets of $P$. The ...
3
votes
1answer
126 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
258 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
133 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
192 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
73 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
103 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
190 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
399 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
125 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
133 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
112 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
57 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
118 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
260 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
166 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
387 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
444 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
172 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
68 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
543 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
373 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
119 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
244 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
89 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
369 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
165 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
71 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
275 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
145 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
303 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
182 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
132 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
257 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
23 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 ...