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

25
votes
6answers
1k 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 \...
44
votes
2answers
8k views

Is there a known well ordering of the reals?

So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $R$ , if every subset has a least element. My ...
19
votes
2answers
3k 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.
25
votes
7answers
10k 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 ...
13
votes
3answers
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$, ...
3
votes
4answers
3k views

Infimum and supremum of the empty set

Let $E$ be an empty set. Then, $\sup(E) = -\infty$ and $\inf(E)=+\infty$. I thought it is only meaningful to talk about $\inf(E)$ and $\sup(E)$ if $E$ is non-empty and bounded? Thank you.
6
votes
3answers
570 views

Countable ordinals are embeddable in the rationals $\Bbb Q$ — proofs and their use of AC

Yesterday, Asaf Karagila's answer to my question sparked an extensive discussion on ways of proving that all countable ordinals are embeddable in $\Bbb Q$, and whether particular solutions to this use ...
3
votes
2answers
582 views

Infinum & Supremum: An Analysis on Relatedness

$\require{color}$ Question: I need some help in proving that $\color{green}{\text{if $k\geq 0$, then $\sup (kS) = k\sup(S)$ and $\inf (kS) = k\inf (S)$}}$, and also that $\color{red}{\text{if $k<...
5
votes
1answer
281 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 ...
19
votes
4answers
7k views

What does “curly (curved) less than” sign $\succcurlyeq$ mean?

I am reading "Convex Optimization" by Stephen Boyd. He is using a curved greater than and curved less than equal to signs. $f(x^*) \succcurlyeq \alpha$ or $f(x*) \preccurlyeq \alpha$ Can someone ...
12
votes
2answers
494 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. ...
12
votes
3answers
6k views

A finite set always has a maximum and a minimum.

I am pretty confident that this statement is true. However, I am not sure how to prove it. Any hints/ideas/answers would be appreciated.
12
votes
3answers
1k 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 ...
9
votes
3answers
497 views

Without appealing to choice, can we prove that if $X$ is well-orderable, then so too is $2^X$?

Without appealing to the axiom of choice, it can be shown that (Proposition:) if $X$ is well-orderable, then $2^X$ is totally-orderable. Question: can we show the stronger result that if $X$ is well-...
4
votes
1answer
174 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
4answers
1k views

Prove that for any infinite poset there is an infinite subset which is either linearly ordered or antichain.

Let $(X, \leq)$ be an infinite poset. Prove that there is an infinite $X' \subset X$ for which holds one of the following: 1) Induced order on $X'$ is linear. 2) $(X', \leq_\mathrm{ind})$...
8
votes
2answers
3k 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 ...
4
votes
1answer
230 views

Finding an uncountable chain of subsets the integers

How to find an uncountable subset of $P(\mathbb{N})$ such that every two elements of it can be compared. In fact, give an uncountable subset of $P(\mathbb{N})$ such that has totality property. We mean ...
1
vote
2answers
94 views

Proving that Order for N is Anti-symmetric

I'm having trouble deriving the following fact from the basic properties of $+_{\mathbb{N}}$ and the definition: Definition. $\forall n, m \in \mathbb{N}: (n \geq m) \leftrightarrow (\exists a \in ...
1
vote
1answer
134 views

Let G be an abelian group, and let a∈G. For n≥1,let G[n;a] := {x∈G:x^n =a}. Show that G[n; a] is either empty or equal to αG[n] := {αg : g ∈ G[n]}… [closed]

We were given questions to study for our exam coming up. We have not covered much of this topic, so any help would be greatly appreciated! Let $G$ be an abelian group, and let $a\in G$. For $n≥1$, ...
1
vote
2answers
1k 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, ...
0
votes
1answer
155 views

Construction of uncountably many non-isomorphic linear (total) orderings of natural numbers

I would like to find a way to construct uncountably many non-isomorphic linear (total) orderings of natural numbers (as stated in the title). I've already constructed two non-isomorphic total ...
10
votes
2answers
837 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 ...
14
votes
3answers
1k views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
8
votes
1answer
1k 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 $...
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 here....
4
votes
1answer
72 views

How many chains are there in a finite power set?

Let $A$ be a finite set with $n$ elements. How many chains are there in $\mathcal P(A)$ -- that is, how many different subsets of $\mathcal P(A)$ are totally ordered by inclusion? It's easy enough to ...
3
votes
2answers
187 views

On Tarski-Knaster theorem

Let $P(X)$ denote the power set of $X$ (the set of all subsets of $X$) with a partial order given by inclusion. If $F: P(X) \to P(X)$ is monotone (order preserving), then $F$ has a fixed point. How ...
2
votes
2answers
405 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
votes
2answers
302 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
6
votes
3answers
3k views

Isomorphisms: preserve structure, operation, or order?

Everyone always says that isomorphisms preserve structure... but given the (multiple) definitions of isomorphism, I fail to see how the definitions equate with the intuitive meaning, which is that two ...
10
votes
2answers
402 views

How many ordinals can we cram into $\mathbb{R}_+$, respecting order?

I've been pondering the following question. How can we measure the amount of "space" above an element $p$ in a partially ordered set $P$? One way would be to try to cram the elements of ...
5
votes
4answers
987 views

How long does a sequence need to be to be guaranteed to have a monotonic subsequence length k?

The sequence 7, 2, 4, 1, 4, 8 has an increasing subsequence length four (2, 4, 4, 8) and a decreasing subsequence length three (7, 4, 1). It has other monotonic (increasing or decreasing) subsequences ...
8
votes
5answers
5k 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 ...
7
votes
3answers
746 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 ...
6
votes
1answer
202 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 ...
4
votes
2answers
623 views

Why does every countable limit ordinal have cofinality $\omega$?

According to Wikipedia, if $\alpha$ is a countable limit ordinal, then $\mathrm{cf}(\alpha)=\omega$. It is intuitively clear to me that it should be so. Certainly the cofinality of such an ordinal ...
3
votes
1answer
220 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
88 views

Introductions to posets on algerbaic structures (Everything I need to know about them)

I need a good and complete introduction to Tree-like orders and partial orders on algebraic structures with one operations. I accept basic texts too. I'm looking for free online texts mostly because ...
8
votes
3answers
634 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 $...
5
votes
1answer
355 views

Question of an isomorphism of $\epsilon_ 0$ and a subset of the rationals.

I don't know if this question is appropriated for this site. Anyway, I'm searching for an isomorphism of order $f:K \longrightarrow \epsilon_o $, such that $(K, \leq)$ is a subset(proper or not) of $(\...
2
votes
2answers
676 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 $\...
2
votes
1answer
85 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
162 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 ...
2
votes
1answer
184 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 $...
1
vote
1answer
5k 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). (...
0
votes
1answer
471 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 (L2;≤...
8
votes
1answer
182 views

Do there exist totally ordered sets with the 'distinct order type' property that are not well-ordered?

Define that the order type of an element $x$ in a totally ordered set $X$ is the order type of $\{w \in X\mid w < x\}$. Under this definition, distinct elements of a well-ordered set have distinct ...
4
votes
1answer
458 views

In a complete lattice every monotone function has a fixpoint (Knaster–Tarski Theorem)

L is a complete lattice, so every subset has a supremum and infimum. In addition, there exists a function $f:L \rightarrow L$ such that $a \leq b$ implies $f(a) \leq f(b)$. Prove that there exists ...
4
votes
1answer
904 views

Question related with partial order - finite set - minimal element

Prove by induction. Every partial order on a nonempty finite set has at least one minimal element. How can I solve that question ?