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

0
votes
6answers
67 views

How can I prove that if $a^7 = b^7$ then $a=b$, with $ a,b \in \mathbb{Z} $

I've tried with divisibility, meaning that since $a$ divides $a^7$, then $a$ divides $b^7$ and in the same way b divides $a^7$, but I can't seem to go further than this. What properties of the ...
0
votes
0answers
39 views

Is there standard terminology for any or all of these concepts designed to help with thinking about Riemann integrability?

When trying to determine whether a function $f$ is Riemann integrable or not, we're typically in the following situation: Write $U_f(P)$ and $L_f(P)$ for the corresponding "upper Riemann sum" and ...
3
votes
0answers
54 views

Generalized ordering on simplicial complex

The vertices of simplicial complexes are usually totally ordered so that face maps of each simplex can be defined easily for the purposes of homology. That gives an "oriented" simplicial complex. But ...
0
votes
1answer
66 views

Order-Preserving Adjunction?

Let there be two categories PrO (category of preordered sets) and ProM (category of preordered monoids). If we know that there exists an adjunction $F\dashv G$ for functors ...
0
votes
3answers
77 views

Why does $a≤b{\implies}a=b∧a<b$?

Let $≤$ be a relation on set $A$ such that $≤$ is reflexive, transitive and antisymmetric. Let $<$ be a relation on set $A$ such that $<$ is asymmetric, antireflexive and transitive. Let $a$ ...
1
vote
2answers
53 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
57 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
41 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
94 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
72 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
198 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
75 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
101 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
30 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
60 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
118 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
54 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
110 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
53 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
35 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
76 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
50 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
224 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
43 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
12 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
58 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
24 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
49 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
64 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
37 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
37 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), ...
0
votes
2answers
205 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
53 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
80 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 ...
0
votes
0answers
17 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 ...