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

Inverse of order preserving transformation

Suppose $\left(A,\leq_{A}\right)$ and $\left(B,\leq_{B}\right)$ are Posets and $f:A\to B$ is an order preserving bijection. I'm trying to show that $f^{-1}:B\to A$ is also order preserving. ...
1
vote
0answers
62 views

Order relation with reversed order definition

I am trying to solve this exercise, but it is kind of confusing to me because the order relation involved "reverses" the standard order. Let $\tau$ a binary relation over $\mathbb N$ defined as ...
3
votes
1answer
130 views

New attempt to prove Dilworth Theorem

Moving from that question to this new one due to space reasons, here there is a new attempt to prove the theorem that (I hope) take into account the feedbacks of Thomas Andrews. Theorem (Dilworth, ...
3
votes
1answer
243 views

Special Galois connections

Let $(f;g)$ is a Galois connection between two posets. Consider the special case $g\circ f = \operatorname{id}_{\operatorname{dom} f}$. What can be said about this special case of Galois ...
-1
votes
1answer
23 views

Does consistency of a test imply continuity of a preorder?

Let $F$ and $G$ be two real-valued probability distributions, considered as cadlag functions with the uniform norm [not the Skorohod metric], and let $\mathbb{F}_n$ and $\mathbb{G}_m$ be empirical ...
0
votes
1answer
138 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
567 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
226 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
1k 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} ...
6
votes
1answer
202 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
342 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
99 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
115 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
376 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
189 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
303 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 ...
5
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 ...
1
vote
2answers
434 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
394 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
141 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
392 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
236 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
280 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 ...
5
votes
1answer
197 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
290 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
189 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
237 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
222 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
181 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
540 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
341 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
195 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
218 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
573 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
76 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
225 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
342 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
156 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
347 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 ...