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

On the alphabetical order of monomial

I found this definition of alphabetical order for monomials in $k[x_1,\ldots,x_n]$. We say that $x_1^{a_1}\cdots x_n^{a_n}>x_1^{b_1}\cdots x_n^{b_n}$ if for the least $i$ such that $a_i\neq b_i$ we ...
0
votes
1answer
552 views

Every finite partially ordered set has a maximum length chain.

Every finite partially ordered set, $(A, \leq)$, has a maximum length chain. A chain is a sequence of distinct elements $a_1 \leq a_2 \leq .......\leq a_n$ with relation $"\leq"$ where $a_i \in A$ ...
5
votes
2answers
382 views

If every nonempty subset of a set $S$ has a least and greatest element, is $S$ finite?

Some sets are well-ordered; all of their nonempty subsets have least elements. You can also have sets where all of their nonempty subsets have greatest elements. Some sets have both of these ...
1
vote
3answers
121 views

Question regarding well-ordering theorem

The well-ordering theorem states that every set can be well-ordered. That is, there is a total order on the set in which every non-empty subset has a least element. I was wondering whether it's also ...
5
votes
2answers
249 views

Showing there is only one isomorphism between well ordered sets using transfinite induction

I need to show specifically using transfinite induction that given two well-ordered sets $\left(A,<_{1}\right)$ and $\left(B,<_{2}\right)$ there is only one isomorphism between them. To do ...
3
votes
2answers
90 views

Class of structures isomorphic to $(\mathbb{Z},<)$ in infinitary logic $L_{\omega_1 \omega}$

We want to define the class of all structures isomorphic to $(\mathbb{Z},<)$ in the infinitary logic $L_{\omega_1 \omega}$. Therefor we define strict order as usual: $\forall x,y,z ~~ (x<y ...
3
votes
1answer
378 views

Question about Hausdorff Maximal principle and antichain

I have this prob and still haven't figured about Let (A, $\leq$) be a partially ordered set. A subset B of A is called an antichain if and only if for any two distinct elements x and y in B, ...
0
votes
1answer
167 views

Proving of existence of limit ordinal

How to prove that for every ordinal $\alpha$ there exist limit ordinal $\beta$ ,such that$\alpha\in\beta$ ? Thank you.
0
votes
1answer
71 views

Different definitions of (anti-)exchange for a closure operator

Wikipedia article for matroids says For all elements $a$, and $b$ of $E$ and all subsets $Y$ of $E$, if $a\in\operatorname{cl}(Y\cup b) \setminus Y$ then $b\in\operatorname{cl}(Y\cup a) ...
7
votes
3answers
276 views

Help me get hyped about lattices

I own a small book on Lattice theory published by Dover. Unfortunately, since I bought it almost a year ago, I have gotten nowhere in its study. What I am asking for are freely available papers that ...
13
votes
2answers
2k views

Every partial order can be extended to a linear ordering

How do I show that every partial order can be extended to a linear ordering? I think that I manage to prove that claim for finite set, how can I prove it for infinite set? Thank you.
2
votes
1answer
44 views

breadth of join-semilattice

On page 16, Lattice Theory: Foundation, George Grätze(2011), 1.19 Show that a join-semilattice $(L; \lor)$ has breadth at most $n$, for a positive integer n, iff for every nonempty finite subset ...
6
votes
1answer
85 views

Are these two subsets of a poset already named?

In a partially ordered set $(X,≤)$, an upper set of a partially ordered set $(X,≤)$ is a subset $U$ with the property that, if $x \in U$ and $x≤y$, then $y \in U$. The dual notion is lower set, ...
7
votes
1answer
145 views

Least common fixed-point

I have been reading a book, "Introduction to Lattices and Order", and I'm trying to solve exercise 8.29 as the following in it: Suppose that $P$ is a complete lattice and let $F$ and $G$ be ...
6
votes
1answer
307 views

Order embedding from a poset into a complete lattice

Let $\mathfrak{A}$ is an arbitrary poset. Does it necessarily exist an order embedding from $\mathfrak{A}$ into some complete lattice $\mathfrak{B}$, which preserves all suprema and infima defined in ...
1
vote
2answers
184 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
133 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
264 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
142 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
604 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
229 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
109 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
238 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
207 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
347 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
421 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
195 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
313 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
474 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 ...
2
votes
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
397 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
62 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
153 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
409 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
287 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
208 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
300 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
196 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
108 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
243 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 ...