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

44
votes
2answers
7k 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 ...
18
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
6answers
977 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 ...
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 ...
3
votes
4answers
2k 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.
5
votes
1answer
278 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 ...
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
2answers
580 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 ...
9
votes
3answers
491 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 ...
6
votes
3answers
556 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 ...
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. ...
11
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.
7
votes
3answers
739 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 ...
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, ...
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 ...
4
votes
1answer
173 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', ...
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
210 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 ...
2
votes
1answer
215 views

If $A$ is well ordered and $B$ is well ordered then $A\times B$ with the lexicographic order is well ordered

I am trying to prove that: Given that $A,B$ are well ordered sets, also $A \times B$ is a well ordered set. (A set $A$ is well ordered if a linear order is defined on it, and every non empty subset ...
1
vote
1answer
133 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
93 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 ...
0
votes
1answer
152 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
832 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 ...
7
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
4answers
968 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 ...
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 ...
3
votes
2answers
185 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 ...
8
votes
1answer
181 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 ...
3
votes
0answers
198 views

A construction on boolean lattices is itself a boolean lattice?

Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) boolean lattices (with lattice operations denoted $\sqcup$ and $\sqcap$, bottom element $\bot$ and top element $\top$). I call a boolean funcoid a ...
2
votes
2answers
400 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
300 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
398 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 ...
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
2answers
148 views

Well ordering agreeing with ordinal ordering on a cardinal

This is an exercise from Kunen book - Set theory, an introduction to independence proofs. Let $\kappa$ be an infinite cardinal and $\triangleleft$ any well-ordering of $\kappa$. Show that there is an ...
6
votes
1answer
201 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
617 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
217 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
610 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 ...
6
votes
2answers
826 views

What does a well ordering of $\mathbb{R}$ look like? [duplicate]

Possible Duplicate: Is there a known well ordering of the reals? I am having a hard time wrapping my head around what a well-ordering of $\mathbb{R}$ looks like. I have seen the ...
5
votes
1answer
352 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
1answer
56 views

Partial orders that can be realized by prime ideals of commutative rings

Is there a general criterion for which partial orders can be realized by the prime ideals of commutative rings (like we have for topological spaces - https://en.wikipedia.org/wiki/Spectral_space)? ...
2
votes
1answer
84 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
182 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
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
2answers
660 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 ...