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

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
100 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
227 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
96 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 yes,...
5
votes
4answers
987 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
144 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
68 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 z\...
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 A$....
2
votes
2answers
165 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
75 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
92 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
64 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 uncountable)...
2
votes
1answer
131 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 $y = ...
0
votes
1answer
80 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
649 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, anti-...
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 $y = ...
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 $1$...
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
59 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
504 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.
3
votes
1answer
110 views

Is there anything wrong with this use of the axiom of choice?

I have a proof of the following theorem: Let A be a finite set and X be a perfectly normal topological space, and let $\{(A,\succsim_x): x\in X\}$ be a family of binary relations on $A$ satisfying ...
1
vote
2answers
929 views

How to prove a total order has a unique minimal element

Let $R$ be a total order on set $S$. Prove that if $S$ has a minimal element, than the minimum element is unique. I have difficulties with proofs. I know any graph of a total order is a straight line,...
1
vote
1answer
133 views

How to tell if relation on set is a partial order when relation is defined as a set of ordered pairs?

Determine whether $R$ is a partial order on set the $S$ and justify your answer. $S=\{1,2,3\}$ and $R=\{(1,1),(2,3),(1,3)\}$. So the job is to consider if $R$ is reflexive, antisymmetric and ...
1
vote
2answers
126 views

$\mathbb R\times\mathbb R$ not order isomorphic to $\mathbb R$

I am trying to show that if you use the lexicographic ordering induced by $\mathbb R$ on $\mathbb R\times\mathbb R$ they are not isomorphic. Is it enough to use the counter-example that whilst $(1,0) ...
2
votes
1answer
69 views

A representation of well-orderings?

Is there a well-ordering $P$ of the set of real numbers $\mathbb{R}$ such that there is NO function $f: \mathbb{R}->\mathbb{R}$ satisfying the property: for all $x,y \in \mathbb{R}$, $xPy$ iff $...
1
vote
1answer
81 views

Contractibility of topological spaces associated to posets

Suppose $\mathcal{P}$ is a partially ordered set. To $\mathcal{P}$ we can associate a simplicial complex $K(\mathcal{P})$ whose $n$-simplices are the chains of length $n+1$ in $\mathcal{P}$. Since ...
0
votes
1answer
189 views

union of cyclic groups

Let $p$ be a prime integer. Let $C(p^n)$ be the cyclic group of order $p^n$ ($C(p^n)=\{z \in C\mid z^{p^n}=1\}$ and let $C(p^\infty)$ be the union of the groups $C(p^n)$, i.e., $C(p^\infty)=\{z\in C\...
1
vote
1answer
72 views

Prove anti-symmetric-ness of partial ordered set in lattice.

Prove anti-symmetric-ness of partial ordered set in lattice. Definition: If $(A, \le_{A})$ is a lattice and $C$ is a set, $([C \rightarrow A], \le)$ is also a lattice. And $\rightarrow$ is defined ...
0
votes
1answer
146 views

Prove transitivity of partial ordered set in lattice.

Prove transitivity of partial ordered set in lattice. I am given this If $(A, \le_{A})$ is a lattice and C is a set, $([C \rightarrow A], \le)$ is also a lattice. And $\rightarrow$ is defined as ...
4
votes
1answer
102 views

order preserving implies isomorphism

Let $M = (M, <)$ and $N = (N, <)$ be two dense totally ordered sets without endpoints. Let $F$ be the collection of order preserving maps between finite subsets of $M,N$ respectively. ...
2
votes
1answer
35 views

Finding order properties in the relation $aSb \iff \exists k \in \mathbb{N} : b = ak$

An order relations exercise I just did. I think it's fine, but the second proof felt a bit too wordy or discursive, instead of going straight to the point with brief and accurate statements. How could ...
0
votes
0answers
232 views

Finding the first, last, minimal and maximal elements in these relations.

I'm now learning about relations of order. This is what I gather: First element: Precedes all elements Minimal elements: Have no predecessors. The first element is always a minimal. Last element: ...
2
votes
1answer
330 views

How many possible DAGs are there with $n$ vertices

I am have $n$ vertices and trying to enumerate all possible DAGs $\theta$ over $n$. How many DAGs are there? For example when $n=2$, there are 3 possible DAGs and when $n=3$ I tried the following: $|...
3
votes
0answers
258 views

Power-set in Hypercube: historical background of indexing each term like Hasse Diagram?

My instructor wants references about the indexation over the hypercube, related question here, he does not believe that I was the first who used it -- [update] thanks to a comment, the name is Hasse ...
2
votes
1answer
189 views

Counting certain partitions of integers

[Recall that] Young's lattice is a partially ordered set in which all partitions of integers are ordered thus: The elements just one step below any partition are those that you can get by subtracting $...
0
votes
1answer
37 views

Does every tree have an upper portion that is a non-empty chain?

Given a poset $P$, call $A \subseteq P$ an upper portion iff $A^c < A$, by which I just mean that for all $a \in A^c$ and all $b \in A$ we have that $a < b$. Then every upper portion is upward ...
12
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.
18
votes
2answers
1k views

Order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$

Do you have a simple example of order preserving bijection from $\mathbb Q\times \mathbb Q$ to $\mathbb Q$? On $\mathbb Q$, I use the usual order and on $\mathbb Q\times\mathbb Q$, I define the ...
0
votes
1answer
125 views

Is this poset a lattice?

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation $$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
0
votes
1answer
63 views

What is the terminology for this type of order-preserving function?

As I roughly know, a function $f$ in $\mathbb{R}$ is called order-preserving if $f(x)>f(y)$ for $x>y$, $x,y \in \mathbb{R}$. May I ask, if anybody knows the terminology for two functions $f$ ...