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

1
vote
2answers
58 views

Sets which are order-isomorphic to the (extended) rationals

Let $(S,<)$ be a totaly ordered set under the strict order relation $<$. Suppose that, for any $a,b\in S$, if $a<b$, then there exists $c\in S$ such that $a<c<b$. We also assume that $...
1
vote
1answer
65 views

The set of rational numbers has continuum many subsets that are order-wise inequivalent

How to show that there are continuum many subsets of $\mathbb Q$, no two of which are similar? Two sets are called similar if there is an order-preserving bijection between them.
0
votes
2answers
42 views

Why is the infimum of the following relation 1?

The question was: What is the infimum from $K=\{x ~ |~0 \leq x \lt 1\}$ for the partial order $\{ (x,y) ~ | ~ ( \exists z \in \mathbb{R}_{\geq 0})[x-z=y] \}$ on set $\mathbb{R}$. This was a question ...
4
votes
1answer
97 views

Why does the Möbius function take its values so often in $\{0,+1,-1\}$?

The Möbius function of a locally finite poset $P$ is defined on its intervals $[x,y] \subseteq P$ recursively by $$\mu([x,x])=1$$ $$\forall x < y : \mu([x,y])=-\sum_{x \leq z < y} \mu([x,z])$$ ...
0
votes
3answers
84 views

Ordering on the reals for which every element has a successor and a predecessor

I'm going through Problem and Theorems in Classical Set Theory by Komjath and Totik, and the answer to this question is: Let $[x]$ (resp. $\{x\}$) denote the integral (resp. fractional) part of $x$, ...
0
votes
1answer
16 views

Suborderable space, orderable characterization proof doubt

In Orderability in the presence of local compactness, Valentin Gutev states and proves the following proposition: A suborderable space $X$ is orderable with respect to a linear order $\prec$ on it if ...
3
votes
1answer
206 views

What is so special about Higman's Lemma?

Is there a motivational example of an application of Higman's Lemma that brings out the true beauty and importance of Higman's Lemma? What is the thing that made so many people care about it? For an ...
4
votes
0answers
34 views

Can we associate values to elements in a poset? [duplicate]

My question comes from personal investigation. Suppose you have a poset $(X, \le_X)$. I would like to associate to all elements $x \in X$ a value $v(x) \in V$, where $(V, \le_V)$ is a totally ordered ...
3
votes
2answers
83 views

subobject classifier for partial orders

Does the category of partial orders have a subobject classifier? (Edit: No, see Eric's answer.) If not, what is a category which is "close" to the category of partial orders (e.g. it should consists ...
2
votes
2answers
104 views

Isomorphisms of well ordered sets

Let $A$, $B$ be well ordered sets. If there exist order-preserving functions $f : A \to B$ and $g : B \to A$ (do not need to preserve initial segments), are $A$ and $B$ isomorphic? I know this is not ...
-4
votes
4answers
78 views

Find $A$ and $B$ such that $A⊈B$ and $B⊈A$? [closed]

I need to prove that the subset relation “$⊆$” on all subsets of $\mathbb Z$ is not a total order and I'm going to do this by finding $A$ and $B$ such that $A⊈B$ and $B⊈A$? Is there a simple solution ...
1
vote
2answers
31 views

Formally real field with two different orders

If $F$ is a formally real field, then there exists a total order relation on $F$ which is compatible with its sum and product, but it needs not be unique. a) How different can be two (compatible with ...
4
votes
0answers
45 views

Group orderable iff all its finitely-generated subgroups are orderable

I want to proof this specifically using the Compactness Theorem from propositional logic (this is an exercise from Model Theory, Hodges). $G$ orderable means there is a total ordering s. t. $g\leq h$ ...
0
votes
1answer
65 views

Subset relation ⊆ on all subsets of ℤ is a partial order, not a total order.

I need to prove that the subset relation “⊆” on all subsets of ℤ is a partial order but not a total order. I'm not experienced in these kind of proofs and was hoping to see an example of an easier one ...
0
votes
1answer
35 views

Proving that divisibility in an integral domain is a partial ordering

Given that R is an integral domain. I'm trying to prove that divisibility on this set constitutes a partial ordering. In particular, I have defined the relation $y \leq_{\,d} x$ on R by $y|x$. ...
6
votes
0answers
121 views

Why is the symbol for the exterior product a meet rather than a join?

I've moved this over to HSM. It seems odd that something that looks so much like a join [see below] would get given "the wrong symbol". It's even worse when you dualise it and get something called (...
2
votes
1answer
56 views

Turning Preordered Sets into Preordered Monoids (Constructing Preordered Monoids from Preordered Sets)

Question: Referring to the Wikipedia article on Adjoint Functors in Section 2 (Motivation), they talk about "turning rngs into rings" (can be rephrased as "constructing rings from rngs"). I do not ...
0
votes
2answers
116 views

uncountable well-ordered chain in $(\mathcal{P}(\mathbb{N}),\subseteq)$ without $AC$

If we assume $AC$ we can construct an uncountable well-ordered chain of subsets of $\mathbb{N}$ by well-ordering the reals and then using the same Dedekind's cut construction as in this question. ...
1
vote
0answers
54 views

Estimates for the Dedekind number $M(9)$

The Dedekind number $M(n)$ is the number of antichains in the partial order of subsets of $\{1,\dotsc,n\}$. It is only known for $0 \leq n \leq 8$. Question. What are some known upper and lower ...
0
votes
1answer
36 views

Translate this problem to graph theory

Say I have a size $k$ set called $S_k$ with elements that are natural numbers (repetitions are allowed). For instance $\{2, 8, 6, 6, 1, 3\}$ is a valid set for $k = 6.$ I am trying to find the least ...
0
votes
0answers
77 views

Order-Preserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...
0
votes
1answer
53 views

Example of discrete set [closed]

Please I need examples of discrete set and non discrete set... am a little confused over this expression. I am thinking of discrete as a finite set but found from another article that, its not ...
0
votes
1answer
229 views

Prove 1 is not the largest integer? [duplicate]

This proof looks extremely flawed, but I'm new to proofs so I'm not completely sure what is allowed and what isn't. Here it is: Let $n$ be the largest positive integer. Then $n$ must be $\geq 1$. ...
3
votes
1answer
44 views

Is there a sequence of with every other sequence as a subsequence?

Let's say we have a set $S$. Is there a sequence $u:\mathbb N \to S$ such that every other sequence $v$ is a subsequence of $u$? Here is what I have so far: If $S=\emptyset$, then no (there are no ...
0
votes
0answers
14 views

History and motivation for Continuous Posets.

Can anyone point to me resources that motivates discusses the history and development of continuous posets? I would really like to know what 'concrete' objects that were studied that gives rise to ...
0
votes
1answer
36 views

Embedding tuples of natural numbers into real numbers

I'm looking for a pointer to common techniques to map tuples of natural numbers into real or rational numbers such that the ordering is preserved (I assume tuples are ordered lexicographically). I'm ...
0
votes
0answers
23 views

Interpreting N vector function

For $\mathcal{N} = \mathcal{N} \bigcup\{ \bot_{\mathcal{N}} , \top_{\mathcal{N}} \} $ and $\mathcal{N}^\vec{} = \mathcal{N} \vec{} \mathcal{N} $ (monotonic function over $ \mathcal{N} $), how ...
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)? ...
1
vote
1answer
32 views

Does there exist a poset whose “quasiwidth” strictly exceeds its width?

Let $P$ denote a poset. Then the width of $P$ is defined as the supremum of the set of all cardinal numbers $\kappa$ such that $P$ has an antichain of cardinality $\kappa$. By the quasiwidth of $P$, ...
1
vote
0answers
39 views

Are ($Q$, $\leq$) and ($Q \times Q$, $\leq _e$) isomorphic? [duplicate]

I can't really tell if ($Q$, $\leq$)$\cong$($Q \times Q$, $\leq _e$), where $\leq_e$ denotes the left lexicographic order. Neither have a last/first element, both are dense and have the same ...
3
votes
1answer
73 views

Find a poset with no infinite antichains and that can only be covered by infinitely many chains.

So far I'm struggling to find such a poset. I first considered $(\mathbb{Z}, \leq )$ because it doesn't have any antichains so there aren't any infinite ones. The problem is that whilst the chain ...
1
vote
1answer
37 views

Can every countable Boolean algebra be embedded into $\mathcal{P}(\mathbb{N})$?

Can every countable Boolean algebra be embedded into $\mathcal{P}(\mathbb{N})$? And if so, is the same true for countable semi-lattices?
0
votes
1answer
59 views

Interpreting functions for poset

I'm stuck at a question with the following expression of poset $(\mathcal{N}, \sqsubseteq)$: $$\forall x, y \in \mathcal{N}: x \sqsubseteq y \mbox{ iff } (x = y \vee x = \bot_{\mathcal{N}} \vee y = \...
1
vote
1answer
28 views

The lattice of partial partitions

In perusing A kind of Eulerian numbers connected to Whitney numbers of Dowling lattices I have gotten confused over what seems a very elementary point. The beginning of section 2 of the paper is ...
1
vote
0answers
25 views

Interesting orderings open sets of a topology

Let X be a set of points an $\mathcal{Q}$ be a partition on X. The intuition I want to model is that X is a set of worlds considered possible by an agent and $\mathcal{Q}$ is a question whose ...
2
votes
1answer
50 views

Different Zorn's lemma statements

Given a chain-complete poset $P$, every $x\in P$ lies below some maximal element. Every inductive poset has enough maximal elements a maximal element. Chain-complete means every chain has a least ...
1
vote
1answer
49 views

Proving a total-order is a well-order if and only if every initial segment is determined by an element

I managed to prove the $\longrightarrow$ part, but I'm not entirely sure how to prove the second part. I can assume by contradiction that the total order $(X, \leq)$ is not a well-order, which means ...
0
votes
1answer
65 views

Algebraic lattices and distributivity over joins of upward directed sets

I am reading Burris & Sankappanavar, Chapter 1 on lattices, and I am doing Exercise 6 in Section §4: If $L$ is an algebraic lattice and $D$ a subset of $L$ such that for each $d_1$, $d_2 \in D$ ...
2
votes
1answer
38 views

Alternate definitions of width (of a partial order) without Choice?

Say an antichain of a poset $P$ is a set of pairwise incomparable elements of $P.$ Typically, the width of a partial order is defined to be the supremum of the cardinalities of antichains of $P.$ When ...
4
votes
3answers
38 views

Ordered sets $\langle \mathbb{N} \times \mathbb{Q}, \le_{lex} \rangle$ and $\langle \mathbb{Q} \times \mathbb{N}, \le_{lex} \rangle$ not isomorphic

I'm doing this exercise: Prove that ordered sets $\langle \mathbb{N} \times \mathbb{Q}, \le_{lex} \rangle$ and $\langle \mathbb{Q} \times \mathbb{N}, \le_{lex} \rangle$ are not isomorphic ($\le_{lex}$ ...
0
votes
0answers
16 views

Question about partially ordered sets and how to order them?

If I had a partially ordered set (E, ≤) where E = {1,2,3}, how would I order it? In other words, if I wanted to show the set, would I need to conform to the definition of ≤? So would it be {(1,2), (1,...
0
votes
2answers
265 views

what does ≼ or ≺ mean?

I was reading a paper about well-orderings and this came up: Suppose (E, ≤) and (F, ≼) are isomorphic well-orderings. Then there exists a unique isomorphism for (E, ≤) to (F, ≼). I've been scouring ...
0
votes
0answers
54 views

Difficulty with exercise 24.12 in Jech

Exercise 24.12 in Jech's Set Theory (3d Millenium Edition): The lexicographical ordering $\omega \times {\omega}_1$ does not have true cofinality. True cofinality is defined (p.461) as the least ...
1
vote
1answer
90 views

“Minimal upper bounds” in a categorical setting

It is well-known that partial orders can be seen as very simple categories (those where there is at most one morphism between every two objects). Then, the notion of "(binary) join of two elements (i....
0
votes
0answers
18 views

Is there a common notation for $x \sqcap Yy\neq \bot$

Is there a commonly used shorthand to express the following relation: $x R y \iff X \sqcap Y \neq \bot$? That is, the greatest lower bound of the two elements is not bottom. In terms of sets, the ...
-1
votes
3answers
54 views

Define well-order on finite subsets of $\mathbb{N}$ [closed]

Define a well-order $\le$ in $P_\text{fin}(\mathbb{N})$ - (it's the set of all finite subsets of $\mathbb{N}$, the natural numbers) that: $ A, B \in P_\text{fin}(N) (A \subseteq B \rightarrow A \le B ...
0
votes
0answers
25 views

Examples of adjoint order morphisms

Given posets $(X, \leq)$, and $(Y, \leq)$, an order morphism is a map $f : X \to Y$ such that $x \leq y$ implies $f(x) \leq f(y)$. Given two order morphism $f: X \to Y$ and $g: Y \to X$, we say that $...
1
vote
3answers
58 views

Well ordering of order types

Notice: in this problem I shouldn't use any properties of the ordinals, and order types are not defined as ordinals. Let $A,B$ be well ordered sets. We say that $otp(A) = otp(B)$, if $A,B$ are ...
2
votes
2answers
47 views

Fundamental question concerning Partial/Total Orders

Often when reading various texts involving total/partial orders, I come across statements like: "...thus $\leq$ is a total order on $\mathbb{Z}$ when $a \leq b$ is given its usual meaning." Is there ...
1
vote
1answer
48 views

A property of product order

Let $\mathfrak{A}$ be a poset, let $a\in\mathfrak{A}$. By definition $$\star a = \{ x\in\mathfrak{A} \mid \text{there exists non-least } y\in\mathfrak{A} \text{ such that } y\le a \text{ and } y\le x\}...