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
3answers
264 views

Is there a name encompassing both limit inferior and limit superior

Is there a mathematical term which would include both liminf and limsup? (In a similar way we talk about extrema to describe both maxima and minima?) The only thing I was able to find was that some ...
1
vote
1answer
111 views

What elements of the pentagon lattice $N_5$ do not satisfy the distributive law?

I heard that the "pentagon lattice" $N_5 = (\{0,a,b,c,1\},\le)$ is not distributive, where $\le$ is the reflexive transitive closure of $\{(0,a),(a,b),(b,1),(0,c),(c,1)\}$. What elements of $N_5$ do ...
3
votes
4answers
205 views

A certain family of complex functions

Are there an uncountable linear order $(P, \leq)$ and a family of continuous complex-valued functions $\{f_p\colon p\in P\}$ defined on the interval $[0,1]$ such that for any $p<q$, $p,q\in ...
2
votes
1answer
144 views

Connected subsets of lines

For me every connected set has at least two elements. Connected subsets of the real line have non-empty interiors. I am curious if the same is true for connected subsets of any connected linearly ...
4
votes
2answers
262 views

Two order related questions for subgroups of infinite groups

For finite groups what I am asking is really trivial. In finite groups if we pick a non trivial subgroup $H$ of $G$ we can always find (there could be multiple choices) a subgroup that is an immediate ...
2
votes
1answer
171 views

How to show the ascending chain condition

Let $(A,\le)$ be a poset. Suppose that for any $a < b \in A$ and for any chain $Q$ of $A$ whose maximum and minimum are $a$ and $b$ respectively, $Q$ is finite. Let $C$ be the set of all chains of ...
1
vote
2answers
61 views

Minimum size of a subset to know a complete total order

Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered. $<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$ Given that $<$ is transitive, it ...
2
votes
1answer
108 views

What is a binary relation like whose reflexive transitive closure is a partial order?

Let $R$ be a reflexive binary relation and $R^*$ be its reflexive transitive closure. The question is what is the equivalent condition in terms of $R$ to $R^*$ being a partial order. Intuitively, a ...
2
votes
4answers
129 views

“Down-Closed”, “Down Ideal”, Something Else?

Let $X$ be an a set and let $\mathcal{C}$ be a collection of subsets of $X$ satisfying the following property: If $A$ and $A^\prime$ are subsets of $X$ with $A \in \mathcal{C}$ and $A^\prime ...
2
votes
1answer
175 views

How different are inductively ordered set from posets that satisfy the ascending chain condition?

I'd like to show that posets that satisfy the ascending chain condition (ACC) have maximal elements. I noticed this statement looks much like Zorn's lemma which holds for inductively ordered sets. ...
7
votes
1answer
605 views

Totally ordering the power set of a well ordered set.

Let's say I take a set $S$, where $S$ can be well ordered. From what I understand, one can use that well ordering to totally order $\mathscr{P}(S)$. How does a body actually use the well ordering of ...
4
votes
1answer
300 views

The “canonical” representative of an order type

An ordinal (in von Neumann sense) can be thought as the "canonical" representative of the order type (i.e. of the class of all order-isomorphic sets) of a well-ordered set. This is very convenient, ...
2
votes
1answer
122 views

Questions about power sets and their ordering

Okay, so I'm stuck on a question and I'm not sure how to solve it, so here it is: In the following questions, $B_n = \mathcal{P}(\{1, ... , n\})$ is ordered by containment, the set $\{0,1\}$ is ...
12
votes
2answers
214 views

Is it possible to construct an ordered field which is also algebraically closed?

It is well known that while the real numbers are totally ordered, they are not algebraically closed, and while the complex numbers are algebraically closed, they are not totally ordered. Is it ...
1
vote
0answers
196 views

How to understand $\limsup$/$\liminf$ of a subset of a complete lattice with a topology

From Wikipedia: Let $Y$ be a partially ordered set which is also a topological space and a complete lattice so that the suprema and infima always exist. For a set $X ⊆ Y$, define $$ ...
12
votes
2answers
280 views

Is every suborder of $\mathbb{R}$ homeomorphic to some subspace of $\mathbb{R}$?

Let $X \subset \mathbb{R}$ and give $X$ its order topology. (When) is it true that $X$ is homeomorphic to some subspace of $Y \subset \mathbb{R}$? Example: Let $X = [0,1) \cup \{2\} \cup (3,4]$, ...
2
votes
1answer
77 views

A question about lattices and their being partially-ordered sets, rather than total-ordered sets

Am I correct in saying that, given a and b are elements of S, the join(a, b) and meet(a, b) won't be either a or b, if there is no order between a and b?
1
vote
1answer
125 views

Are all subspaces of the rationals order topologies (with respect to some linear order)? All closed subspaces?

This is a follow-up to this question. Let $Y \subset \mathbb{Q}$, and give $Y$ the subspace topology. Is there necessarily a linear ordering $<$ of $Y$ (possibly different from the order inherited ...
5
votes
1answer
143 views

If $X$ is an order topology and $Y \subset X$ is closed, do the subspace topology and order topology on $Y$ coincide?

Let $(X,<)$ be a linearly ordered set and give $X$ its order topology. Suppose that $Y \subset X$. There are 2 sensible ways to topologise $Y$: View $Y$ as a subspace of $X$ and give it the ...
2
votes
1answer
248 views

Create an order relation over the field of p-adic numbers

I've come to know that you can't define an order relation over the field of p-adic numbers that is compatible with the addition and multiplication according to the ordered field axioms. I was ...
5
votes
2answers
267 views

Is $\mathbb R$ terminal among Archimedean fields?

I was wondering why metrics and norms are always defined to be real, rather than generalized to some other fields (or whatever). The best guess I have so far is: Because every Archimedean ordered ...
0
votes
1answer
1k views

Identifying maximal, greatest elements on a Hasse/lattice diagram?

So, while I understand the difference between maximal elements and greatest elements, I'm having trouble understanding how to identify them on a lattice diagram (just as an example, the lattice ...
1
vote
2answers
170 views

How does this statement on posets follow from Zorn's lemma?

Let $P$ be a poset with a maximal element $r$, i.e. an element $r\in P$ such that $r\geq x$ for all $x\in P$. One can think of the poset as a tree with root $r$. I want to show that there exists a ...
1
vote
1answer
66 views

Question about chains and lattices

Are there lattices in which not every chain has an upper bound? I think not but I think I'm wrong wrong because I read the sentence "Let $L$ be a lattice in which every chain has an upper bound...." ...
2
votes
2answers
2k views

Supremum/infimum and unions/intersections

I took some notes in class that I have trouble understanding. There's a chance my notes are incorrect: The union of a family of sets is the supremum. The intersection is the infimum. The ...
1
vote
3answers
346 views

How many infima and suprema can there be?

The Wikipedia definitions of infimum and supremum include the words "greatest" and "lowest", implying that there's at most one infimum and one supremum for any given subset. But in the empty set ...
1
vote
1answer
81 views

Strict part of a relation

What do you mean by the term strict part of a binary relation? How can it be used to define minimal element for any set with relation?
1
vote
1answer
4k views

Greatest lower bound property and least upper bound property

A Completeness principle in mathematical analysis is a principle by the help of which we can establish (prove) the completeness of an ordered field( About whom I am going to post one question later). ...
2
votes
1answer
519 views

On Dilworth's theorem

Dilworth's Theorem on Posets states that if $P$ is a poset and $w(P)$ is the maximum cardinality of antichains in $P$ then there exist a decomposition of P of size $w(P)$. The question is, why this ...
11
votes
4answers
261 views

Given an infinite poset of a certain cardinality, does it contains always a chain or antichain of the same cardinality?

It is known that given an infinite poset, it always contains an infinite chain or antichain; moreover, there is a constructive proof that we can find a continuous chain in $P(\mathbb{N})$; so, in ...
5
votes
4answers
428 views

Existence of a well-ordered set with a special element

One of the most mind boggling results in my opinion is, with the axiom of choice/well-ordering principle, there exist such things as uncountable well-ordered sets $(A,\leq)$. With this is mind, does ...
5
votes
1answer
901 views

Least upper bound property iff convergence of Cauchy sequences

From http://en.wikipedia.org/wiki/Non-Archimedean_ordered_field: The field of rational functions over $\mathbb{R}$ can be used to construct an ordered field which is complete (in the sense of ...
1
vote
2answers
584 views

Prove König's theorem using Dilworth's theorem

I am trying to derive König's theorem from Dilworth's theorem, but it seems like I'm stuck. I know that I have to define some kind of binary relation on the set of a bipartite graph's vertices, then ...
11
votes
3answers
652 views

Examples of rings with ideal lattice isomorphic to $M_3$, $N_5$

In thinking about this recent question, I was reading about distributive lattices, and the Wikipedia article includes a very interesting characterization: A lattice is distributive if and only if ...
2
votes
1answer
94 views

Does a basis of a directed-complete partial order contain all compact elements?

I am currently reading an introduction to domain theory. In the discussion of bases of dcpos it is stated that every basis contains the compact elements of said dcpo. Both these notions depend on the ...
2
votes
1answer
92 views

Looking for “average” of two permutations

I am a computer programmer and I am building a search engine for a client. Right now I am puzzling myself about the order in which I should return search results. There are two obvious orderings: ...
4
votes
1answer
404 views

Best known bounds for the number of linear extensions of a poset

Let $(P, \le)$ be a poset on $n$ elements $x_1\dots x_n$. A total order $<$ on the same set is said to be a linear extension of $\le$ if $(\forall i,j)\quad x_i \le x_j \rightarrow x_i < x_j$. ...
2
votes
2answers
186 views

Separate a total order in a “countable manner”

Related to my answer on this question : set of values of finite measure, exhaustion method I would like to know if for an arbitrary total order $K$, there exists a sequence $\{k_n\}$ such that for ...
2
votes
1answer
101 views

Probabilistic ordering

I want to characterize the probabilistic ordering of some (random) variables without going into a parametric from of the variables themselves. I couldn't easily find any theory for this and I am not ...
1
vote
2answers
169 views

Cofusing partial order “implies”, on logic and that on sets

I feel confused comparing partial order on sets and that on logic. $$x\ge 1 \implies x\ge 0$$ Here we see a smaller set "implies" a bigger set But, if we know three facts, fact1,fact2,fact3, we ...
3
votes
1answer
99 views

Can the cofinality of a $\operatorname{cf}(A)$-directed partially ordered set $A$ be singular?

The cofinality of a totally ordered set is always a regular cardinal. On the other hand for any cardinal (regular or singular) $\kappa$ there is a partially ordered set $(A,\leq)$ with ...
7
votes
5answers
4k views

What is the difference between max and sup?

I am studying KS (Kolmogorov-Sinai) entropy of order q and it can be defined as $$ h_q = \sup_P \left(\lim_{m\to\infty}\left(\frac 1 m H_q(m,ε)\right)\right) $$ Why is it defined as supremum over ...
1
vote
3answers
180 views

Order type of uncountable set and order ordering

Question: If $\Theta$ is the order type of an uncountable set, then show that for $\alpha < \omega_1$, $\alpha \preceq \Theta$ or $\alpha^* \preceq \Theta.$ Where $\preceq$ is an ordering of order ...
1
vote
1answer
107 views

Existence of the $P$ closure of binary relation $R$

From wikipedia, for an arbitrary binary relation $R\subseteq S×S,$ and an arbitrary property $P$, the $P$ closure of $R$ is defined as: The least relation $Q\subseteq S×S$ that contains ...
2
votes
1answer
87 views

Two posets and a function

Are there any interesting applications of the structures $(A;B;f)$ consisting two posets $A$ and $B$ and a function $f:A\rightarrow B$? (consider also it special cases such as $A$ and/or $B$ being ...
9
votes
2answers
689 views

The p-adic numbers as an ordered group

So I understand that there is no order on the field of p-adic numbers $\mathbb{Q_p}$ that makes it into an ordered field (i.e.) compatible with both addition and multiplication. Now, from the ...
7
votes
4answers
304 views

Supremum and ordinals

Question: Show that sup{$ \xi \dotplus 1 : \xi \in A $} is the least ordinal that is greater than each element of $A$. I tried to get a better feel for this by letting $A=3=${$0,1,2$}. Then I know ...
3
votes
2answers
288 views

Order type and its reverse

I am given the following definition: For an arbitrary order type $\Theta$, denote by $\Theta$* (the reverse of $\Theta$) the order type $type\Theta$*$=typeA(\succ)$, where $\langle A,\prec \rangle$ ...
20
votes
2answers
781 views

Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?

I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago. Reading the wikipedia article linked above, I ...
8
votes
7answers
4k views

difference between maximal element and greatest element

I know that it's very elementary question but I still don't fully understand difference between maximal element and greatest element. If it's possible, please explain to me this difference with some ...