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.
8
votes
3answers
381 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 ...
7
votes
7answers
1k 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 ...
10
votes
2answers
266 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.
...
1
vote
1answer
84 views
Problem with “tree” definitions
In my studies of choice principles, I've encountered the concept of a tree several times. Frustratingly, no two of the sources I've been working with define it in quite the same way!
Notation: Given ...
6
votes
2answers
1k 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 ...
2
votes
2answers
153 views
Bourbaki-Witt fixed point theorem: two questions
Consider the following theorem:
Let $f\colon E \to E$ have the propery that $f(x)\geq x$, where $(E,\leq)$ is a non-void partially ordered set with the property that every totally ordered subset of ...
1
vote
2answers
117 views
Discrete Math - Hasse Diagrams
This is one of many questions of similar type I have to do for an assignment and im troubled with what to do. The question is as follows:
Consider a relation R defined on the set A = {−7, −6, −5, ...
16
votes
6answers
373 views
Embedding ordinals in $\mathbb{Q}$
All countable ordinals are embeddable in $\mathbb{Q}$.
For "small" countable ordinals, it is simple to do this explicitly.
$\omega$ is trivial, $\omega+1$ can be e.g. done as $\{\frac{n}{n+1}:n\in ...
5
votes
4answers
841 views
Simplest Example of a Poset that is not a Lattice
A partially ordered set $(X, \leq)$ is called a lattice if for every pair of elements $x,y \in X$ both the infimum and suprememum of the set $\{x,y\}$ exists. I'm trying to get an intuition for how a ...
4
votes
1answer
803 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 ...
0
votes
1answer
127 views
Cross Product of Partial Orders
im going to have a similar questions on my test tomorrow. I am really stuck on this problem. I don't know how to start. Any sort of help will be appreciated. Thank you
Suppose that (L1;≤_1) and ...
4
votes
2answers
111 views
$<$ in a preorder
The author of the book I am studying defines $<$ for a poset as
If $x, y \in X$, where $X$ is a poset, then we shall write $x < y$ to mean that $x \le y$ and $x \ne y$.
From this, I can ...
2
votes
3answers
94 views
Equal elements vs isomorphic elements in a preoder
While introducing preorders, Roy L. Crole in Cateories for Types states
If $x \leq y$ and $y \leq x$ then we shall write $x \cong y$ and say that $x$ and $y$ are isomorphic elements.
I'm trying ...
2
votes
2answers
333 views
A question regarding the Continuum Hypothesis (Revised)
Given that the order type of the reals $(\mathbb R,<)$ has no definable points, can it be proven that $|\mathbb R|= \aleph_1$ by virtue of the fact that every uncountable proper subset $S$ of ...
1
vote
1answer
79 views
preorders induced by continuous functions to the reals
Any function to a (total) order induces a (total) preorder on its domain. What can be said about the total preorders induced by a continuous function from a "nice" topological space (for instance, a ...
1
vote
3answers
254 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 ...
10
votes
1answer
299 views
Linearly ordered sets “somewhat similar” to $\mathbb{Q}$
$\pmb{\eta}$ - order type of $\mathbb{Q}$.
$\pmb{\eta} + \pmb{1}$ - order type of $\mathbb{Q}\cap(0, 1]$.
$\pmb{\omega_1}$ - order type of the first uncountable ordinal.
Let's say that a linear ...
14
votes
2answers
276 views
Is $(\pmb{1} + \pmb{\eta})\cdot\pmb{\omega_1} = \pmb{1} + \pmb{\eta}\cdot\pmb{\omega_1}$?
$\pmb{\eta}$ - order type of $\mathbb{Q}$.
$\pmb{1}$ - order type of a singleton set.
$\pmb{\omega_0}$ - order type of $\mathbb{N}$.
$\pmb{\omega_1}$ - order type of the first uncountable ordinal.
...
8
votes
2answers
557 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 ...
8
votes
1answer
134 views
Is $\pmb{\eta}\cdot\pmb{\omega_1} = (\pmb{\eta} + \pmb{1})\cdot\pmb{\omega_1}$?
$\pmb{\eta}$ - order type of $\mathbb{Q}$.
$\pmb{1}$ - order type of a singleton set.
$\pmb{\omega_0}$ - order type of $\mathbb{N}$.
$\pmb{\omega_1}$ - order type of the first uncountable ordinal.
...
4
votes
1answer
149 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 ...
2
votes
3answers
213 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$
...
9
votes
0answers
305 views
How to find a total order with constrained comparisons
There are 25 horses with different speeds. My goal is to rank all of them, by using only runs with 5 horses, and taking partial rankings. How many runs do I need, at minumum, to complete my task?
As ...
7
votes
2answers
223 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.
5
votes
1answer
445 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
...
4
votes
3answers
294 views
How to define a well-order on $\mathbb R$?
I would like to define a well-order on $\mathbb R$. My first thought was, of course, to use $\leq$. Unfortunately, the result isn't well-founded, since $(-\infty,0)$ is an example of a subset that ...
4
votes
1answer
99 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
39 views
Looking for example of an order homomorphism that doesn't preserve joins.
I know that not every order homomorphism preserves joins. But, I can't think of an example!
Both minimal examples and 'natural' examples welcome.
2
votes
1answer
128 views
Is the set $S$ of functions $S = \{ f : \mathbb R \to \mathbb R \}$ from the reals to the reals a totally ordered set?
Is the set $S = \{ f : \mathbb R \to \mathbb R \}$ of functions $f$ from the reals to the reals a totally ordered set ?
I think the question is clear. Note that there is a bijection to $g(x)$ gives ...
2
votes
3answers
167 views
Getting a Distributive-Lattice from Poset or, equivalently, a Greedoid from a Poset
Theoretic background
Lets just set some background to be sure what I am talking about
Posets
A Poset is defined to be a couple $(S,\leq)$ where a set $S$ and its elements $s \in S$ are connected ...
0
votes
1answer
50 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 ...
6
votes
2answers
164 views
A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets
If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ?
5
votes
1answer
325 views
Quickest way to understand Kruskal's Tree Theorem
I came across the Kruskal Tree Theorem the other day and thought it looked pretty interesting (especially the stronger finite form due to Friedman). I'm currently a first year mathematics ...
4
votes
1answer
169 views
Lexicographical order - posets vs preorders
I found the following definition for lexicographical ordering on Wikipedia (and similar definitions in other places):
Given two partially ordered sets $A$ and $B$, the lexicographical order on the ...
3
votes
1answer
65 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
160 views
Cardinality of the set of ultrafilters on an infinite Boolean algebra
Let $\mathfrak B$ be a Boolean algebra with an infinite power $\kappa$. My question is how many ultrafilters does it have? $\kappa$ or $2^\kappa$? Or even smaller?
3
votes
4answers
188 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
24 views
Do the pth powers of $p$-norms define the same partial ordering on the set of all probability distributions for all $p>1$?
Consider the $p$-th power of the Schatten $p$-norm $||q||_p$ of a probability distribution $q$ , ie, the function $\sum_j q_j^p$, where $\sum_j q_j = 1$ and $q_j \geq 0$. For fixed $q$ and $p>1$ ...
2
votes
2answers
34 views
Finding the number of $2$-element chains of $B_n$
I'm trying to calculate the number of $2$-element chains and anti-chains of $B_n$, where $B_n$ is the boolean algebra partially ordered set of degree $n$.
I understand that I want to take all of the ...
2
votes
2answers
135 views
isomorphism $\Bbb Q$ to $\Bbb Q \cap (0,1)$
I've got a question in my homework:
Prove that $\langle \mathbb{Q},< \rangle$ and $\langle \mathbb{Q}\cap (0,1),< \rangle$ are isomorphic.
I have tried to find a bijective function without any ...
2
votes
1answer
194 views
Examples of preorders in which meets and joins do not exist
Exercise 1.2.8 (Part 1), p.8, from Categories for Types by Roy L. Crole
Definition: Let $X$ be a preordered set and $A \subseteq X$. A join of $A$, if such exists, is a least element in the set of ...
2
votes
1answer
78 views
$M_3$ is a simple lattice
I'd like to prove (exercise 9.5 in Roman's Lattices and Ordered Sets, p.203) that the lattice $M_3$
is simple, meaning that the only congruences on $M_3$ are the trivial ones (the 'equality' ...
2
votes
2answers
158 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
2answers
196 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.
...
1
vote
1answer
49 views
how to combine different partial orders (Poset)
Given two posets $\prec_A$ and $\prec_B$ where $A\neq B$ and $A\cap B\neq \emptyset$, is there any way to combine them while preserving the exact information they exhibit - namely dominance relation ( ...
1
vote
1answer
237 views
Rudin Theorem 1.11
After spending a few hours trying to understand Theorem 1.11 in Rudin's Principles of Mathematical Analysis, I still don't follow the proof.
1.11 Theorem Suppose $S$ is an ordered set with the ...
1
vote
0answers
167 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 $$
...
1
vote
2answers
125 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 ...
0
votes
2answers
68 views
Help on total ordering and partial ordering
Hi guys my final exam is coming up, and I am given a few practice problems and I don't get how to do these questions on total ordering and partial ordering. Here are the question and here is how I did ...
0
votes
1answer
40 views
Showing that $\mathbb{C}$ under the lexicographic order does not satisfy $x,y>0\implies xy>0$
Identifying $\mathbb{C}$ with $\mathbb{R} \times \mathbb{R}$, we can consider the lexicographic order: we define $x_1 + iy_1 < x_2 +iy_2$ if either
A) $x_1 < x_2$ or B) $x_1 = x_2$ and $y_1 ...
