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
141 views

Is this a sound proof of Dilworth Theorem?

This is my first attempt to prove something a bit more serious than the usual trivial stuff. But I am not sure I actually proved the result. Does the following work? Theorem (Dilworth, 1950): Every ...
0
votes
2answers
582 views

Dedekind Cuts - Additive and Multiplicative Identities

I wanted to receive some help regarding some homework questions; I appreciate any sort of feedback possible. I am certain that any Dedekind Cut $A$ has the following properties: 1) $A$ is not the ...
2
votes
2answers
228 views

Well-Ordered Sets and Functions

I need some assistance with the following problems. I've come up with some ideas but may need some clarification. 1) Let $S$ be a well-ordered set. a) Need to show $S$ has a first element. ...
15
votes
6answers
2k views

Is the set of real numbers the largest possible totally ordered set?

Because I find any totally ordered set can be "lined up" in a straight line, I'm guessing that the set of all the real numbers is the biggest totally ordered set possible. In the sense that any other ...
1
vote
1answer
54 views

Is any set that has a preorder is a directed set?

In the definition of directed set, they emphasized that aside from it having a preorder, "every pair of elements has an upper bound." My question is that isn't the latter property implied by the ...
2
votes
2answers
100 views

What kind of POSET whose chain can be unbounded?

On Page 32, Set Theory, Jech(2006): Let $\kappa$ be a limit ordinal. A subset $X \subset \kappa $ is bounded if $\operatorname{sup}{X} < \kappa$, and unbounded if $\operatorname{sup}{X} ...
5
votes
1answer
158 views

Chain of length $2^{\aleph_0}$in $ (P(\mathbb{N}),\subseteq)$

How can I find a chain of length $2^{\aleph_0}$ in $ (P(\mathbb{N}), \subseteq )$. The only chain I have in mind is $$\{\{0 \},\{0,1 \},\{0,1,2 \},\{ 0,1,2,3\},...,\{\mathbb{N} \} \}$$ But the ...
6
votes
1answer
206 views

Extending a partial order to antichains

Let $(S, \leq)$ be a partial order. Let $T$ be the set of antichains of $S$ (i.e., subsets of $S$ whose elements are pairwise incomparable). Define a relation $\leq'$ on $T$ as follows: for all $A$, ...
7
votes
1answer
343 views

Order topology and partial order

Let $(X,\leq)$ be an ordered space and define on $X$ the order topology form the subbasis $\{(x,y), (x,\to), (\leftarrow,x) : x,y \in X \}$. Can you read the fact that $\leq$ is a total order on the ...
5
votes
1answer
100 views

Lower Bound of countable order-types of linearly ordered sets

On Page 44, Set theory, Jech(2006) (Show that) there are at least $\mathfrak{c}$ countable order-types of linearly ordered sets. [For every sequence $a = \{ a_n : n \in N\}$ of natural numbers ...
1
vote
1answer
121 views

The cardinality of finite Boolean lattice

A book (Introduction to Lattices and Order) says that we can prove that the cardinality of any finite Boolean lattice $B$ is a power of 2 by induction on $|B|$ with the following lemma: If a lattice ...
0
votes
1answer
414 views

Maximal and maximum (matchings)

Maximal and maximum matchings seem to be with respect to different partial orders, do they? In the set of all matchings in a graph, a maximal matching is with respect to a partial order defined by ...
2
votes
2answers
191 views

isomorphism $\Bbb Q$ to $\Bbb Q \cap (0,1)$

I've got a question in my homework: Prove that $\langle \mathbb{Q},< \rangle$ and $\langle \mathbb{Q}\cap (0,1),< \rangle$ are isomorphic. I have tried to find a bijective function without any ...
3
votes
3answers
309 views

Counting directed acyclic graphs with the same partial ordering

We are given a partially ordered set $P$. Let $L$ denote the set of all linear extensions of $P$ (or equivalently, the set of all topological sortings of the nodes). We want to count the number of ...
7
votes
2answers
3k views

Given the Hasse diagram tell if the structure is a lattice

Let's consider the following Hasse diagram: I need to tell whether this is a lattice. By lattice definition I can prove the above shown structure $M_5$ to be a lattice if and only if $\forall x,y ...
2
votes
2answers
457 views

Maximal vs upper bound in a POSET

I am studying the concept of a partially ordered set(POSET) and one author says that a "a maximal element need not be an upper bound". I tried browsing the net to find an example of the preceding ...
1
vote
4answers
2k views

what is total order - explanation please

sorry for the dumbest question ever, but i want to understand total order in an intuitive way, this is the defition of total order: i) If $a ≤ b$ and $b ≤ a$ then $a = b$ (antisymmetry); ii) If $a ...
0
votes
2answers
395 views

how to show equivalence relation and its classes

i am stumbling again in proving things in maths. the task is to prove that this statement $A \sim B : \Longleftrightarrow \sum_{a\in A} a = \sum_{b\in B} b $ is an Equivalence Relation on Power Set ...
1
vote
0answers
61 views

Lexicographical Ordering versus Prioritized versus Pareto Composition

I am not sure if I understood it correctly. Lexicographical ordering is the same as prioritized composition principle (they all use the first order and then use others to break the ties). If that's ...
7
votes
0answers
150 views

Monoids with positive and negative elements

By a pointed monoid I mean a monoid $M$ together with an absorbing element $0 \in M$ (i.e. $0x=x0=0$). Equivalently, this is a monoid in the monoidal category $(\mathsf{Set}_*,\wedge)$. By a ...
0
votes
1answer
402 views

Maximal Elements - Ordered Sets

Problem 1: Let $S$ be an ordered set with a unique maximal element $x$. Again, I've worked some thoughts to these problems and would like to confirm their validity. I appreciate any feedback. (1) ...
2
votes
1answer
237 views

properties of the poset of self adjoint elements in a $C^*$ algebra

It is well known that the set of self-adjoint elements in a $C^*$ algebra naturally forms a poset. I assume that the general properties of this poset are known. Can anybody point me to a reference ...
2
votes
2answers
74 views

Reaching elements with finite applications of the successor relation in well-ordered sets

Given an well-ordered class $(A,\leq)$ we want to proof that every element $a \in A$ can be reached by applying the successor relation on a the smallest element of $A$ or on an limes element of $A$ ...
18
votes
4answers
286 views

Is there a name for this kind of “betweenness structure”?

A homeomorphism $\mathbb R\to\mathbb R$ is almost the same thing as an order isomorphism, except that a homeophorphism can also be an order anti-isomorphism. I'm wondering whether there is a natural ...
0
votes
1answer
59 views

About the existence of a partition to a partially ordered set $A$.

Let $A$ be a countable set equipped with a partial order $\prec$. We all know that there are subsets $C\subset A$ with the property that the order $\prec$ in $C$ is total. In other words, any two ...
6
votes
1answer
202 views

Exercise on partially ordered sets from Kunen's *Set Theory*

This problem is Exercise (F4) from Chapter VII of Kunen's text. Apparently, it is a result of Tarski. It goes as follows: Let $ \mathbb{P} $ be a partial order. Define $ \text{c.c.}(\mathbb{P}) $ ...
1
vote
3answers
298 views

correct English pronunciation of the word poset

What is the correct English pronunciation of the word poset (Partially Ordered SET)? paazit or pow-set?
0
votes
1answer
194 views

Any countable set $A$ with a dense total ordering, with neither a maximum nor a minimum, is isomorphic to the rationals.

I think I can do this first: index all elements of $A$ by the natural numbers, make a map $f$, first send $a_0$ to any rational number, call it $q_0$. Then inductively, depending on the ordering of ...
0
votes
3answers
106 views

$\forall{a\in A,\, b\in B} \mid a\le b$ Prove that: $\sup A \le \inf B$

Let A and B be two non-empty bounded subsets of $\mathbb{R}$. $\forall{a\in A,\, b\in B} \mid a\le b$ Prove that: $\sup A \le \inf B$ My solution goes as follows: Suppose $\sup A \gt \inf B$: ...
3
votes
3answers
240 views

Ways Of Ordering A Set

Perhaps this is a strange question. But it made me think and I have no idea how to answer it. Or if it actually makes sense. I've come across "Well-Ordered Sets" a few times now, and it's well known ...
2
votes
1answer
228 views

The relation between order isomorphism and homeomorphism

Let $X$ be a set and let $<_1,<_2$ be order relations on $X$. Let $T_1,T_2$ be the topologies induced on $X$ respectively. If $(X,T_1)$ is homeomorphic to $(X,T_2)$, does that imply that ...
1
vote
1answer
58 views

Different orderings for highest weights of a representation

Recall that given a representation $\pi$ of $\mathfrak{sl}_n$, a weight $\mu$ is said to be of highest weight if its corresponding weight vector is annihilated by all the positive root spaces (1). ...
1
vote
1answer
187 views

Discrete Math “Well Order”

the definition of a well order is that if $R$ is a linear (order) and every non-empty subset of $A$ has a least element. I understand that $(\mathbb N,\le)$ is a well-order but how come $(I,\le)$ ...
2
votes
1answer
162 views

Is the set $S$ of functions $S = \{ f : \mathbb R \to \mathbb R \}$ from the reals to the reals a totally ordered set?

Is the set $S = \{ f : \mathbb R \to \mathbb R \}$ of functions $f$ from the reals to the reals a totally ordered set ? I think the question is clear. Note that there is a bijection to $g(x)$ gives ...
2
votes
2answers
563 views

Orders on the Cartesian product of partially ordered sets

The wikipedia article about partially ordered set describes three of the possible partial orders on the Cartesian product of two partially ordered sets, and mentions that similar constructions can be ...
1
vote
1answer
348 views

Determining minimal and maximal elements in products of partial orders

$\newcommand{\angles}[1]{\langle { #1 } \rangle}$ I did the following exercise, can you tell me if I got it right? Thanks: EXERCISE 31(G): Consider $\angles{ [0,1) , \leq } \otimes^s \angles{ ...
3
votes
4answers
197 views

Showing that the equivalence class of partial orders order isomorphic to $(X, \leq)$ is not a set

I'm trying to do the following (original image): EXERCISE 25(R):(a) Argue on the grounds of the architect's view of set theory (which was outlined in the Introduction) that $\mathbf{PO}$ cannot be ...
4
votes
3answers
224 views

Proof of every binary relation with a rank function is well-founded

I proved the following claim (source image), can you tell me if my proof is correct? Thanks: Claim 4: Let $R$ be a binary relation on a set $X$, and suppose $\langle Y, \prec \rangle$ is a strict ...
6
votes
3answers
583 views

How to define a well-order on $\mathbb R$?

I would like to define a well-order on $\mathbb R$. My first thought was, of course, to use $\leq$. Unfortunately, the result isn't well-founded, since $(-\infty,0)$ is an example of a subset that ...
2
votes
1answer
78 views

Disjointifying sets if indexed by set that doesn't admit a well-order?

I have a question about the following: I think this should say "... if $I$ finite or if there exists a well-order ..." because if $I$ is a set like this also lets one disjointify $A_i$ with $i ...
1
vote
2answers
236 views

Proof of “well-founded iff there is no sequence $x_n$ s.t. $(x_{n+1}, x_n) \in R$”

I tried to do the following exercise from a book I'm reading, can you tell me if my solution is correct? Thanks! Theorem 2: Let $R$ be a binary relation on a set $X$. Then $R$ is strictly ...
2
votes
1answer
52 views

A question about infinite utility streams

At the end of Diamond's Evaluation of Infinite Utility Streams he proves a theorem (which he doesn't give a name to, but it's at the very end of the article). There is a step in which he jumps from ...
2
votes
0answers
69 views

Relationships between zero morphisms and least morphisms

Zero morphism $0_{XY}$ is defined by the formulas $a\circ 0_{XY}=b\circ 0_{XY}$ and $0_{XY}\circ c= 0_{XY}\circ d$ for every morphisms $a$, $b$, $c$, $d$ of suitable sources and destinations. I ...
2
votes
1answer
351 views

Relation between lattice theory and semilattice theory

When studying inverse-semigroups, idempotent elements play an important role, and semilattices occur naturally as sets of idempotent elements that commute with each other. I have the impression that ...
0
votes
1answer
159 views

Shortest proof of Kuratowski's lemma

I want a short proof of Kuratowski's lemma (about maximal chains). Does proving Kuratowski's lemma need first prove Zorn lemma? I am writing a book in which I claim that the reader needs to know ...
0
votes
1answer
356 views

Is this a partial order and draw the Hasse diagram.

$A=\{2,3,4,6,8,12\},\ x,y \in A, x\le y \leftrightarrow x^2 \mid y$ Is this a partial order and draw the Hasse diagram. I know to be a partial order it needs to be reflexive, anti symmetric ...
0
votes
1answer
35 views

Isomorphism of preferences

Suppose we have a denumerable set $S$ with a total order $\preceq$. Is there necessarily an isomorphism $\phi:S\to\mathbb{N}$ such that $x\preceq y \Leftrightarrow \phi(x)\leq\phi(y)$? Specifically ...
0
votes
1answer
372 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
138 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 ...
12
votes
0answers
553 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 ...