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
1answer
365 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 ...
3
votes
4answers
135 views

$\sup(S)$ does not belong to $S$?

Problem: can anyone come up with an ordering of $\mathbb{N}$ different than the standard one we know, where we can find a subset $S\subset \mathbb{N}$ in a way such that $\sup(S)$ exists in ...
11
votes
0answers
541 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 ...
5
votes
2answers
568 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 ...
4
votes
1answer
70 views

Is the semigroup generated by wellordered positive set wellordered?

Let $(A,\leq)$ be a totally ordered abelian group, and $\Gamma\subseteq A$ be a set of nonnegative elements, such that it is wellordered by $\leq$. Is it true then that the semigroup $S$ generated by ...
0
votes
1answer
133 views

Equality on Partial and Total Orders

If I have a partial order, is the following conclusion valid? $$a \geq c$$ $$b \geq c$$ Then, $$a = b $$ Does the result change if the partial order were to become a total order? Any and all ...
2
votes
1answer
138 views

How to define subtraction in lattice and how to define complementation of an element in a lattice?

The story is that in a lattice, there are some elements incomparable, and there exits some elements have overlapping elements. for example, suppose the partial order is defined on inclusion, then ...
1
vote
1answer
45 views

How to prove that the infimum of the sum of two sequences is at most the sum of their infima?

I'm trying to show: $\inf(x_k+y_k) \leq \inf(x_k)+\inf(y_k)$. So I did: Let $r>0$, there is a $k_1$ such that $x_{k_1}\leq \inf(x_k)+r/2$ and there is a $k_2$ such that $y_{k_2}\leq ...
3
votes
1answer
756 views

Poset Infimum and Supremum

I was asked to show that if every subset of a poset has an infimum then every such subset has a supremum. I did my proof and now I realize that what I was calling "infimum" was actually "a smallest ...
2
votes
2answers
71 views

Sorting $i$ amongst integers

In the game Wits & Wagers, players each answer a numerical question and the answers are then sorted in ascending order for scoring, details of which being irrelevant for this question. In this ...
2
votes
1answer
86 views

Conditional merge of a sequence of DAGs / partial orders

I have a sequence of directed acyclic graphs, $G_i$. The union of their edge sets may not be a DAG. I want to find an edge set that is maximal in some sense but still acyclic. Alternatively I have a ...
5
votes
1answer
133 views

Generalization of ordinals to well-founded sets?

In set theory, the ordinal numbers are objects that represent the order types of well-ordered sets. Is there a similar class of objects that represent the order types of well-founded sets? If so, ...
1
vote
1answer
342 views

Number of linear extensions of a finite partially ordered set

Let $N$ be a finite set and $\le$ be a partial order. Can you express the number of linear extensions $L(\le,N)$ of this partial order in terms of $b(k) := \#\{l \in N\ :\ k \le l\}$? My intuition ...
6
votes
2answers
123 views

Continuation of strictly monotone functions on $\mathbb{R}$

While studying the properties of ordinal utility functions, I came across the following question. Given a strictly increasing function $f : D \rightarrow \mathbb{R}$, where $D$ is an arbitrary ...
9
votes
1answer
204 views

Atoms necessary for the existence of a generic filter?

I'm reading Some applications of the method of forcing by Todorchevich and Farah and one of the exercises seems to be wrong to me. Definitions We fix some partially ordered set $(P,\preceq)$. A ...
3
votes
1answer
135 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
252 views

Infinite linear (non-well) orderings

I can rather easily imagine the infinite linear (non-well) orderings $(\mathbb{Z},\leq)$, $(\mathbb{Q},\leq)$, $(\mathbb{R},\leq)$, each one of its own order type. Are there "essentially" other ...
3
votes
1answer
227 views

How to derive distributivity from Boolean algebra laws

Let $(L,\le,\bot,\top)$ be a bounded lattice and $\neg: L \rightarrow L$ be a map that satisfies the following laws: $a \wedge b = \bot \Leftrightarrow a \le \neg b$ $\neg\neg a =a$ I'd like to ...
3
votes
2answers
105 views

If $\sim$ is an equivalence relation on $X$, and there is a strict total order on $X/\sim$, what kind of ordering does $X$ have?

I would like to know if there's a special name for this kind of ordering. When I say there is a strict total order on $X/\sim$, what I mean is that two distinct elements in the same equivalence ...
2
votes
3answers
1k views

What is the difference between the supremum (least upper bound) and the minimal upper bound

I understand the difference between the supremum and the greatest element and between the supremum and the maximal elements. But I'm not sure about the difference between the supremum (least upper ...
2
votes
2answers
216 views

Why is 'Antisymmetry' named so?

So when we talk about order relations for the familiar number systems, we are always introduced to the antisymmetry property which is $x \le y, x \ge y \implies x=y$. When I think of the word ...
1
vote
1answer
282 views

Totally ordered set with greater cardinality than the continuum

Does there exist a totally ordered set $S$ with cardinality greater than that of the real numbers? Sequences are continuous functions with domain $\mathbb{N}$ and paths are continuous functions with ...
1
vote
1answer
55 views

Congruence for embeddings of a poset into semilattices

Let $\mathfrak{A}$ be a poset, $\mathfrak{B}$ and $\mathfrak{C}$ be meet-semilattices with least elements. Let $f:\mathfrak{A}\rightarrow\mathfrak{B}$ and $g:\mathfrak{A}\rightarrow\mathfrak{C}$ are ...
7
votes
2answers
195 views

Every poset is embedded into a meet-semilattice

I "discovered" a few minutes ago that every poset can be embedded into a meet-semilattice. Let $\mathfrak{A}$ be a poset. Then it is embedded into the meet-semilattice generated by sets $\{ x \in ...
2
votes
1answer
142 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
198 views

Archimedean ordered fields and valuations (exercise)

Definitions: Let $(K,\leq)$ be a totally ordered field and $(G,\leq)$ a totally ordered abelian group (written additively). If we denote $\mathbb{Z}a\!=\!\{na;\, n\!\in\!\mathbb{Z}\}$, then $G$ is ...
1
vote
2answers
352 views

Draw Hasse diagram as two elements have same image

Let $S=\{1,2,3,4,5,6,7,8,9,10\}$, $P=\{y \in \mathbb N : y \text { is a prime number}\}$, consider the map $f$ defined as follows: $$\begin{aligned} f:x\in S \rightarrow f(x) \in \wp (P) ...
0
votes
1answer
149 views

What is a valuation associated to an ordering on a field?

If $(K,\leq)$ is a totally ordered field with $P\!=\!\{\alpha\!\in\!K;\, 0\!\leq\!\alpha\}$, how is the valuation associated to $P$ defined? I was searching through Prestel & Delzell's Positive ...
1
vote
0answers
36 views

Names of certain morphisms in Pos

Pos is the category of small posets and monotone maps. I call a morphism $f:\mathfrak{A}\rightarrow\mathfrak{B}$ of Pos monovalued iff it maps every atom of $\mathfrak{A}$ either into an atom of ...
2
votes
1answer
231 views

Pointwise order of the Cartesian product of two preordered chains

Definitions: (From Categories for Types by Roy L. Crole.) A preorder on a set $X$ is a binary relation $\leq$ on $X$ which is reflexive and transitive. A preordered set $(X, \leq)$ is a set equipped ...
4
votes
1answer
112 views

Are there larger than countable chains in the join-semilattice of Turing degrees?

Recall that Turing degrees are equivalence classes of subsets of $\mathbb{N}$ under Turing equivalence (mutual Turing reducibility). They are partially ordered by Turing reducibility and form a ...
10
votes
3answers
481 views

An order type $\tau$ equal to its power $\tau^n, n>2$

In this question we are concerned only with linear (aka total) order types. By a cardinality of an order type we understand a cardinality of an instance of this type, which obviously does not depend ...
0
votes
1answer
154 views

$<$ on a preorder is a strict partial order

Definition: Suppose $X$ is a preorder. Define $x < y$ as $x \le y$ and $y \not\le x$ for each $x, y \in X$. Question: Show that this gives a strict partial order on $X$.
2
votes
1answer
185 views

Uniqueness of meets and joins in posets

Exercise 1.2.8 (Part 2), 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 ...
4
votes
1answer
240 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 ...
10
votes
1answer
373 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 ...
16
votes
2answers
344 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. ...
10
votes
1answer
170 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. ...
6
votes
1answer
138 views

Poset of idempotents

Let $A$ be an associative algebra and consider the poset $I$ of idempotents in $A$, where as usual if $e,f \in A$ we say $e \leq f$ provided that $e = fef$. Clearly $0 \in I$ is minimal, but in ...
-2
votes
1answer
133 views

Does an isomorphism induce an order isomorphism?

Let $\mathfrak{A}$ is a poset. For $a, b \in \mathfrak{A}$ we will denote $a \curlyvee b$ if only if there is a non-least element $c$ such that $c \leqslant a \wedge c \leqslant b$. Let ...
4
votes
2answers
159 views

Is every order isomorphism of sets induced by a bijection?

Let $f$ is an order isomorphism $\mathscr{P}A \rightarrow \mathscr{P}B$ (where $A$ and $B$ are some sets, the order is set-inclusion $\subseteq$). Is it true that it always exist a bijection $F: A ...
1
vote
1answer
120 views

Are homeomorphisms order-isomorphisms?

Is every homeomorphism between topological spaces an order isomorphism (for orders of inclusion $\subseteq$ of sets)?
7
votes
2answers
223 views

Set of maximal chains in $\langle\mathcal{P}(\mathbb{N}),\subseteq\rangle$

Let $S$ be the set of all maximal chains in the poset $\langle$$\mathcal{P}$$($$\mathbb{N}$$),$$\subseteq$$\rangle$ partitioned into equivalence classes by their order types. How many different order ...
3
votes
1answer
190 views

Down-sets in posets and directed sets

Let P be a poset and let us say that a subset A of P is a down-set if: $$x \in A, y < x \implies y \in A.$$ A directed set is a poset P such that for every two elements, $a,b \in P$ we can find ...
2
votes
1answer
229 views

Preorders, chains, cartesian products, and lexicographical order

Definitions: A preorder on a set $X$ is a binary relation $\leq$ on $X$ which is reflexive and transitive. A preordered set $(X, \leq)$ is a set equipped with a preorder.... Where confusion cannot ...
4
votes
2answers
143 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
1answer
370 views

Does every set have a well ordering with greatest element?

Does every non-empty set have a well ordering with greatest element? It is well known that every set has a well ordering. But can we also assume that this well ordering has greatest element? [Edited ...
3
votes
1answer
128 views

Is the Kleene/Brouwer ordering dense?

This question was motivated by a statement in Simpson's Subsystems of Second Order Arithmetic (second edition), p. 168. It is straightforward to verify (in $\mathsf{RCA}_0$ for instance) that ...
2
votes
3answers
112 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
0answers
86 views

Ordering of multisets in “Paramodulation based theorem proving”

I'm reading this paper: http://www.lsi.upc.edu/~albert/papers/handbook.ps.gz and I can't understand a part of it. it defines an ordering on multisets (it defines a multiset over $A$ as a function $A ...