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
1answer
40 views

Does irreflexivity guarantee acyclicity?

Assume $R$ to be an irreflexive, transitive relation over a set $X$. Let $G=(X,E)$ be its directed graph where $(x,\hat{x})\in E$ if $xR\hat{x}$ is true. I know irreflexivity means $xRx$ cannot ...
2
votes
1answer
55 views

Bernstein- Schroeder thm for ordered sets

Hi everyone the I know that the Bernstein- Schroeder Thm says that if we have two sets $A,B$, and there exists an injection $f: A\rightarrow B$ and $g: B\rightarrow A$, then there exists a bijection ...
2
votes
1answer
303 views

non-prime maximal ideal in a complemented lattice

Is there a complemented lattice, which has a non-prime maximal ideal?
1
vote
2answers
177 views

Exercise in well-ordered sets

Definitions: Given a subset $A$ of a non-empty well-ordered set $X$ we define the supremum as follows: $\text{sup(A)}:=\text{min}\bigg(\big\{\,y\in X \oplus\{ +\infty\}: \forall x\in A \;(x\le y)\, ...
1
vote
2answers
40 views

Example for $\mathbb{N} ^ \mathbb{N}$ linear order

I'm not really sure if something like $ \{1,2,3,...\} < \{2,2,3,...\} < \{3,2,3,...\}$ works. I don't ask about solution with transitive, antisymmetric and total proof, just for working ...
1
vote
2answers
161 views

How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
3
votes
2answers
116 views

The set of all the partial ordering of $X$ is a partially ordered set.

I have trouble with the following exercise. I don't understand it. Also I think that $x,y\in P$ should be $x,y\in X$. Could someone give an insight of the exercise and also some hint of how to solve ...
1
vote
0answers
49 views

Recovering Ordered Monoid Operation from the Order

I have a partially ordered set $(X, \preceq)$ with the following properties: $X$ has a minimum. I'll name it $1$. For every $x \in X$, the principal filter ${\uparrow} x$ is order isomorphic to $X$. ...
0
votes
2answers
109 views

What is the maximum number of comparisons needed to define a total order

Given a set of values $X=\{x_1,x_2,…,x_m\}$. I want to construct an irreflexive, transitive total order relation $>$ by doing pairwise comparisons among the values of $X$. From trail and error I ...
3
votes
2answers
40 views

disconnected ordered set

Is there a totaly ordered infinite set $A$ with the least element $a$ and the greatest element $b$ such that for any sequence $\{\alpha_n\}$ and $\{\beta_n\}$ in $A$ which satisfies ...
7
votes
1answer
251 views

Intuition behind proof and verification partially ordered sets

Hi everyone in the book that I read I have trouble to understand the argument of the proof at the below proposition. There is a lot of point which are left as exercises, which is great. One of these ...
2
votes
1answer
567 views

Exercise: Every non-empty subset of $X$ contains a minimum and maximum element and the converse

Hi everyone is my second exercise of posets. And find the following, the first part I think is not difficult at all. But for the converse I have some serious troubles to prove it. I have two ...
2
votes
1answer
87 views

What conditions on a totally ordered set imply that the closed intervals are connected?

It is well known that $[a,b]_\mathbb{R}$ is connected, while $[a,b]_\mathbb{Q}$ is not. I'm wondering, what conditions on a totally ordered set $T$ imply that for all $a,b \in T$, it holds that ...
2
votes
0answers
158 views

Partially ordered set exercise

Hi everyone is my first time working with posets and I'd like to know if the solution of the next exercise is really correct or maybe there is some errors that I cannot see. Thank in advance. ...
1
vote
2answers
152 views

Either two sets have the same cardinality, or one has cardinality greater than the other

This is a problem (10.11) from Munkres, Topology, 2 ed. Problem: Let $A$ and $B$ be two sets. Using the well-ordering theorem, prove that either they have the same cardinality, or one has cardinality ...
0
votes
1answer
150 views

Relation between concept lattice and Dedekind–MacNeille completion

While trying to unify the (mostly linearly) ordered attributes from Statistical classification with the binary attributes from formal concept analysis, I came across an interesting section in the ...
3
votes
1answer
119 views

Does model theory extend to partial functions?

I have been reading a bit about effect algebras and d-posets recently, sets $M$ on which you have a single partial binary operation (partial here meaning partially defined, i.e. the domain of this ...
0
votes
1answer
34 views

Ordering tuples over (0,1)

To understand the natural ordering of $\{0,1\}^N$ I first thought about $\{0,1\}^3$ which has this Hasse diagram: There's something interesting going on in the second and third rows. In 3-D it ...
2
votes
0answers
70 views

Set Theory - Well Order (Lexiographical combination)

Question: Prove constructively that if $(A_{1},\prec_{1})$ and $(A_{2},\prec_{2})$ are two well-ordered sets then their lexicographical combination $(A_{1} \times A_{2},<_{1,2})$ is also well ...
2
votes
1answer
89 views

Are there any known uncountable transfinite increasing sequences of real numbers?

The real numbers are uncountable, so assuming the axiom of choice there is at least transfinite sequence of real numbers $r_0, r_1, r_2, ..., r_\omega, r_{\omega + 1}, ..., $ up to (and possibly ...
2
votes
1answer
99 views

Help to understand a proof (about filters)

Niels Diepeveen claims that he has proved the following theorem: Theorem Consider the cofinite filter $F$ on an infinite set. Let $K$ be a collection of ultrafilters such that $\bigcap K=F$. Then for ...
6
votes
2answers
98 views

Existence of totally ordered ring with zero divisors

Does there exist a totally ordered ring with zero divisors? I can't think of an example right now.
0
votes
1answer
218 views

Could the empty set be complete partial order?

According to the definition, $(S,\leq)$ is cpo when each totally ordered subset of $S$ has supremum. I'm sure $(\emptyset,\emptyset)$ is a total order, but I don't know whether $(\emptyset,\emptyset)$ ...
5
votes
1answer
95 views

Existence of non-commutative ordered ring

Does there exist a totally ordered ring which is non-commutative? I have searched the web, but I have not found any examples.
5
votes
2answers
73 views

Countability of a certain set

Suppose $S$ is a totally ordered set such that for any $x,y\in S$ there are finitely many elements between them. Does it follow that $S$ is (at most) countable? It seems like the answer should be ...
5
votes
4answers
966 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 ...
0
votes
2answers
142 views

Is a Lattice just a linearly ordered set?

The definition of Lattice I was introduced to recently was a poset for which every two elements had a supremum and infimum. Doesn't this just mean that the poset is a chain and tus a linearly ordered ...
1
vote
1answer
67 views

How many complete theory extend theory T are there?

$Т$ - theory of signature $\{\le\}$, defined by the axioms А1-А5: А1: $\forall x(x=x)$ А2: $\forall x,y\big((x\le y\land y\le x)\to x=y\big)$ A3: $\forall x,y,z\big((x\le y\land y\le z)\to x\le ...
1
vote
1answer
28 views

Does the closure of the set of all irreducible elements always equal the whole set?

Let $X$ denote a set and $\mathrm{cl}$ denote a finitary closure operator on its powerset. Call $x \in X$ irreducible iff for all $A \subseteq X$ we have that if $x \in \mathrm{cl}(A)$, then $x \in ...
2
votes
2answers
163 views

structure of the hypernaturals

I want to understand the structure of the hypernaturals a little better. Let me recall the ultraproduct construction of the hypernaturals. On the set of all sequences of $\mathbb{N}$, we define an ...
-1
votes
1answer
27 views

partially order

$( A,\le)$ and $(A',\le')$ are partially ordered sets. A map $\phi : A \to A'$ is called order preserving from $(A, \le)$ to $(A', \le')$ if for all $x, y \in A : x \le y \implies \phi(x) \le' ...
1
vote
1answer
59 views

Cardinality of a linear continuum

A linear continuum is a totally ordered set with more than one element, which is both dense and satisfies the least upper bound property. Is it true that every linear continuum has the same ...
1
vote
1answer
74 views

Proof that there is an order relation

For an arbitrary set M there is a relation $R \subseteq 2^M \times 2^M$ about $$ A \mathrel R B \Leftrightarrow A \cup \{x\} = B$$ The join is a disjoint join. There are not more details what is $x$. ...
2
votes
3answers
90 views

Non-trivial order on a set with infinitely many minimals/maximals

I am looking for an example of each: 1) A non-trivial order on a set A such that there are infinitely many minimal elements and 2) A non-trivial order on a set A such that there are infinitely many ...
0
votes
2answers
17 views

How would I show that this is a subset?

Let R1 and R2 be relations on N defined by xR1y if and only if y=a+x for some a ∈ N0. xR2y if and only if y=xa for some a ∈ N. for all x,y ∈ N. Also N0 denotes all integers x>=0, while N denotes all ...
4
votes
1answer
62 views

Does every orthocomplemented lattice satisfy the shuffle laws?

Let $L=(X,\wedge,\vee,^\bot)$ denote a non-empty lattice having a unary operation $x \mapsto x^\bot$ that satisfies both "shuffle" laws: $$x \wedge y \leq z \iff x \leq y^\bot \vee z.$$ $$x \leq y ...
1
vote
1answer
89 views

Effectively describing all elements of the Borel $\sigma$-algebra

Consider, for simplicity, the Borel $\sigma$-algebra of the unit interval $[0,1]$. Let $\{A_i\}$ be a family of Borel subsets which generate the sigma algebra (can be either countable or ...
2
votes
1answer
129 views

How to rigorously prove that these two sets have different order types?

Let $A$ and $B$ be two given ordered sets with the linear (or total) order relations $<_A$ and $<_B$, respectively. Then $(A,<_A)$ and $(B,<_B)$ are said to be of the same type if there ...
1
vote
1answer
92 views

Adjoint of forgetful functor

I want to solve an exercise about adjoints (but I am not sure about the steps). Let $U:\textbf{CL}\rightarrow\textbf{Posets}$ be the forgetful functor. Here we have a functor from the complete ...
0
votes
1answer
49 views

I want to be able to write proof's for each of these but I don't know where to start.

Let $\mathrel{R_1}$ and $\mathrel{R_2}$ be relations on $\mathbb N$ defined by $x\mathrel{R_1}y$ if and only if $y = a + x$ for some $a \in\mathbb N_0$. $x\mathrel{R_2}y$ if and only if ...
0
votes
1answer
77 views

Expected value of round robin scores and ranks

Suppose you have $n$ players play a round robin tournament. A win adds 1 to the winning score of a player while a loss adds nothing. After the round robin tournament is finished the players are ...
2
votes
2answers
642 views

Total Order Relation

Given $X = \{ a , b , c \}$ and $R = \{ (a,a) , (b,b) , (c,c) , (a,b) , (a,c)\}$ Is $R$ a total order on $X$? I know that total order requires the relation to be comparable on all elements, ...
1
vote
1answer
66 views

I want to show that $\mathrel{R_1}$ and $\mathrel{R_2}$ are a partial order on $\mathbb N$, how would I do this?

Let $\mathrel{R_1}$ and $\mathrel{R_2}$ be relations on $\mathbb N$ defined by $x\mathrel{R_1}y$ if and only if $y = a + x$ for some $a \in\mathbb N_0$. $x\mathrel{R_2}y$ if and only if ...
2
votes
1answer
40 views

Is this complete partial order?

Is $(\mathbb{N} , \#)$ complete partial order, where $m\#n$ iff $(\exists k \in \mathbb{N})m=kn$. I proved it's partial order. For completeness I take directed subset and I know there is upper bond ...
0
votes
1answer
57 views

Let $A$ denote a closed subset of $\mathbb{R}.$ Is it true that for all $B \subseteq A,$ if $B$ has a supremum, then $\mathrm{sup}(B) \in A$?

Let $A$ denote a closed subset of $\mathbb{R}.$ It seems obvious that for all $B \subseteq A$ we have that if $B$ has a supremum, then $\mathrm{sup}(B) \in A$. Perhaps this is trivial, but I cannot ...
2
votes
1answer
70 views

Can the obvious “product” of complete atomistic Boolean algebras be realized as a categorial product?

Let $X$ and $Y$ denote sets, and $\eta_X,\eta_Y : X,Y \rightarrow X+Y$ denote the natural injections to the disjoint union. Then intuitively, the "product" of the Boolean algebras $2^X$ and $2^Y$ ...
6
votes
1answer
162 views

Reference Request on Order Theory topics

I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
2
votes
1answer
30 views

When can complete dense linear orders be made into topological fields?

By a "complete dense linear order," I mean a dense linear order in which every nonempty subset with an upper bound has a least upper bound. The canonical example, $\mathbb{R}$, is a topological field ...
1
vote
1answer
56 views

Is this a partially ordered set?

I was wondering if partially ordered sets could have loops in their diagrams. For example isn't the $S=\{1,2,3\}$ and relation $R=\{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\}$ a partially ordered set that ...
1
vote
1answer
492 views

If a partial order has just one unique maximal element, must that element be a greatest element of x?

I believe that it does not have to be a greatest element, because to be a greatest element it must be comparable to all the x in X. I just don't know how to go about proving this.