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
902 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 ...
1
vote
1answer
131 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
123 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
77 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
184 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 ...
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
142 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
101 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
34 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
226 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
322 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
255 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
188 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 ...
11
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
124 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
62 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$ ...
3
votes
2answers
237 views

Dense and complete totally ordered sets

The totally ordered set $\mathbb{R}$ has the following properties. [Density]. Given any two $x,y \in \mathbb{R}$, we can find $\eta \in \mathbb{R}$ such that $x < \eta < y$. [Dedekind ...
-1
votes
1answer
22 views

partial order and truth value

please,give a formula Q with free variables such that for any partial order ( A ; ≤ ; -) we have that [Q]=1 iff [z] is a join of [x] and [y]
0
votes
2answers
712 views

Example of a strict total order

A strict total order is a set $A$ with a binary relation $<$ on it, satisfying irreflexivity, transitivity and totality. Could you give an example of a strict total order, please?
1
vote
1answer
60 views

Proof of Jordan-Dedekind Chain property for graded posets

I have a question about the following proof. Suppose a partially ordered set $(P,\le)$ is graded by its height function $h$. All chains are finite and there is a smallest element $0$. Then the poset ...
1
vote
1answer
79 views

Question about primitive group actions

In Glass' Partially Ordered Groups Corollary 7.4.4 says: If $G$ is an ordered group and $(G,G)$ is the right regular representation, then $(G,G)$ is primitive if and only if $G$ is ...
0
votes
1answer
119 views

Isomorphism between partially ordered sets - What is wrong with my argument?

I'm trying to show Isomorphism between two partially ordered sets is an equivalence relation. Suppose $M$ and $M^{\prime}$ are two partially ordered set and $f:M\to M^{\prime}$ is isomorphism ...
2
votes
3answers
82 views

A notation for a morphism in a thin category

Consider a thin category with objects $A\leq B$. There exists a unique morphism $A\rightarrow B$. Is there a standard notation for this morphism (given $A$ and $B$)?
1
vote
1answer
16 views

Negation of a maximal element in a partially ordered set

Let $(P,\le )$ be a partially ordered set. We call a $m\in P$ a maximal element, if $$p\in P,m\le p\Rightarrow m=p$$ What is the negation of this property? So we assume $m\in P$ is not a maximal ...
1
vote
1answer
70 views

To show that a given graded function is the height function

My background in order theory is not very strong, and I'm confused about the following. The definition and theorems are from Lattices and ordered sets by Roman: Let $(P,\le)$ be a partially ordered ...
1
vote
1answer
37 views

Left-isolated points in totally ordered set

Let $X$ be a totally ordered set. I say that a point $x$ is "left-isolated" if there is some $\alpha < x$ such that there is only one point $y$ which satisfies $\alpha < y \leq x$, that is, ...
3
votes
1answer
243 views

A set that is transitive but not well-ordered by $\in$?

I am trying to find a transitive set which is not well-ordered by $\in$. This question raises when I read Jech's Set Theory, in which an ordinal number is defined as a transitive and ...
4
votes
2answers
399 views

Given an infinite poset, show that it contains either a infinite chain or an infinite totally unordered set. [duplicate]

Been thinking about this one for awhile and I'm still stuck... Thought about proving it by arriving at a contradiction but I haven't reached anything noteworthy. If you do a proof by contradiction, ...
2
votes
1answer
215 views

If $A$ is well ordered and $B$ is well ordered then $A\times B$ with the lexicographic order is well ordered

I am trying to prove that: Given that $A,B$ are well ordered sets, also $A \times B$ is a well ordered set. (A set $A$ is well ordered if a linear order is defined on it, and every non empty subset ...
0
votes
3answers
139 views

How to show that $ \succ acyclic \implies \succ asymmetric $

For a preference relation defined as $$ \succ := \{ (x,y) \in X\times X : x\ is\ better\ than\ y \}$$ one has to show that $$ \succ acyclic \implies \succ asymmetric $$ whereas $$ acyclic := ...
1
vote
1answer
38 views

Proving a function is order-isomorphic?

Let $A$ be a chain and $B$ be a partially ordered set. Let $f: A \rightarrow B$ be a 1-1 function for which $a \leq b$ implies $f(a) \leq f(b)$. Prove $f$ is order-isomorphic. Let $f: A ...
1
vote
1answer
162 views

Every countable lattice has a cofinal totally ordered subset?

If a lattice is countable, prove that it has a subset that is both totally ordered and cofinal in the lattice. Cofinal means that for each $l$ in the lattice, there is some $a$ in the subset such that ...
4
votes
1answer
113 views

Is a chain complete lattice complete?

If every chain in a lattice is complete (we take the empty set to be a chain), does that mean that the lattice is complete? If yes, why? My intuition says yes, and the reasoning is that we should ...
3
votes
0answers
28 views

Expect size of $k^{th}$ layer of a POSET

Is this known? What is the expected width of the $k^{th}$ layer (anti-chain layer) of a $d$-dimensional partially ordered set of $n$ elements formed by product of $d$ random liner orders chosen from ...
2
votes
1answer
220 views

Why is division on Z not a poset?

Why is division on natural number a poset but division on Z is not a poset? Is is because we get ordered pair such as (-1,1) and (1,-1) which is not antisymmetric?
0
votes
0answers
834 views

Is = (equality) a partial order relation?

We know that a partial order relation is a relation which is reflexive , antisymmetric and transitive. Example: (x,y) belongs to R iff x=y. For A={1,2,3}, we get R= {(1,1), (2,2), (3,3)}. Now R is ...
1
vote
1answer
87 views

Counting Self-dual posets

An exercise in Stanley's Enumerative Combinatorics (Chapter 3, ex. 8) asked for an example of a finite self-dual poset, (i.e. there is a bijection $f: P\to P$ such that $s\le t \Longleftrightarrow ...
0
votes
1answer
300 views

Non-isomorphic countable linear orders which embed into each other

Def: $(A,<) \hookrightarrow (B,\lhd)$ if $\exists f:A \to B$ such that $\forall a,b \in A[a<b \implies f(a) \lhd f(b)]$. May I seek your advice on how to construct two infinite, countable ...
0
votes
1answer
130 views

Prove that $R$ is a linear order on $A\times B$

Assume that $(A,\leq)$ and $(B,\leq)$ are linearly ordered sets. Define a relation $R$ on $A\times B$ by $(a,b)R(c,d)$ iff $a<c$ or both $a=c$ and $b\leq d$. Prove that $R$ is a linear order on ...
0
votes
1answer
71 views

unranking a sequence of all linear extensions of a partially ordered set

Let $P$ be a partially ordered set. Let $E$ be the set of all possible linear extensions of $P$. Let $S$ be the sequence formed by arranging elements of $E$ in lexicographic or graycode order. Does ...
3
votes
2answers
91 views

Why does sup-dense imply inf-continuous?

I am confused. The question is as follows: Let $(S, \preceq$), be a sup-dense subset of $(T, \preceq)$, both partially ordered sets. In other words, for every $t \in T$, there exists a subset $E ...
0
votes
1answer
64 views

A Proof of Posets, how to do it?

I am trying to do a exercise from my book, but I don't understand how to solve it (many statements!)... Here is the exercise: Let $P$ and $Q$ be ordered sets. Prove that $(a_1, b_1)\prec ...
9
votes
0answers
324 views

Proving equivalence of a tree-based version of Countable Choice for families of finite sets.

In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5: Each of the following statements imply those beneath it. The countable union of ...
3
votes
1answer
67 views

Given $A \subseteq X$ we can have $\sup A < \inf A$?

For some poset $(X,<)$ with a global max $\top$ and min $\bot$ with $\bot < \top$, and a subset $A = \varnothing$, we'd have $\sup \varnothing = \bot$ and $\inf \varnothing = \top$, right? So ...
0
votes
2answers
119 views

What is an order reversing bijection on $\Bbb R$?

What is an order reversing bijection on $\Bbb R$ and why must it be continuous? Thanks
2
votes
2answers
133 views

Universality of $(\mathbb Q,<)$

I have few questions to the proof on Universality of linearly ordered sets. Could anyone advise please? Thank you. Lemma: Suppose $(A,<_{1})$ is a linearly ordered set and $(B,<_{2})$ is a ...
2
votes
1answer
66 views

Two definitions of a monovalued morphism

Let fix some dagger category every of Hom-sets of which is a complete lattice, and the dagger functor agrees with the lattice order. I define a morphism $f$ to be monovalued when $f\circ f^{-1}\le ...