Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [order-theory]

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. Order theory is not about the order of a group nor the order of an element of a group or other alegbraic structures.

1
vote
1answer
11 views

Does the frame of open sets in a topological space or locale really have all meets?

According to the nLab article on locales, a frame has all meets by the adjoint functor theorem: This seems a bit strange to me, since it's well-known that an infinite intersection of open subsets is ...
1
vote
0answers
18 views

Is a topological sorting of a poset a total ordering?

I have been taught by my professor that the topological sort gives a total ordering of a partial order. However, I do not see how this is the case. You are simply rearranging the elements in the ...
1
vote
0answers
19 views

Finite chain and finite antichain implies that the poset is finite [duplicate]

The problem with which I am struggling is the following, Let $(P,\le)$ be a poset. If every chain and antichain of $P$ are of finite then $P$ is also finite. My Attempt Notice that by Hausdorff ...
4
votes
3answers
306 views

Can we expand “induction principle” to a partial order $(X, \leq)$?

We know that every infinite can be made well-ordered with an unknown order. Also we can expand the induction principle on any infinite set in the sense that it can made well ordered. Now partially ...
1
vote
2answers
63 views

Necessary and sufficient condition for existence of a partial order

I'm trying to find a necessary and sufficient condition for the existence of a partial order such that an arbitrary relation on a set X is a subset of the partial order. So far all I have is that ...
0
votes
0answers
19 views

Name for a poset where incomparability is an equivalence relation

Say I have a partial order $\leq$ on a set $S$. Let me write $a \sim b$ if $a$ and $b$ are incomparable under this order. Is there a name for the following restriction on the partial order? $\sim$ ...
2
votes
0answers
29 views

Lattice definition and example

Guys I am struggling to understand the lattice concept: Could you help me with this silly example? Take the collection $\{\emptyset, \{0\}, \{1\}\}$ ordered by inclusion. This is a poset, but not a ...
1
vote
1answer
25 views

Ordered Set example. Why is partially ordered?

I am studying these concepts of order for the first time, and I am having a certain difficulty: I define an Order relation in $A=\mathbb{R_{+}^{2}}$ as : $x,y \in A$, $x\geq y \iff x_{1} \geq y_{1}$ ...
2
votes
0answers
25 views

Is it possible to have a single axiom that subsumes axioms 8-10 in this list?

Think of a totally ordered set as an “order-theoretic line”. Similarly, cyclic orders are “order-theoretic circles”. I want to find the right axioms for an “order-theoretic plane”. My ultimate goal ...
0
votes
1answer
45 views

Examples of non-orderable fields.

I wish to find examples of non-orderable fields. We know that fields with finite characteristics cannot be ordered, especially finite fields. Also $\mathbb{C}$ - the field of complex numbers cannot be ...
0
votes
1answer
30 views

Cayley digraphs of a group

I could not find an answer to the questions online. How many loopless Cayley digraphs of a group G there are? How many loopless Cayley graphs of a group G there are if |G| = n and G has i self-...
2
votes
1answer
18 views

Relationship between Archimedean and Divisible ordered groups

Let $(G,+,\leq)$ be a linearly ordered abelian group (i.e. the order is total and compatible with the sum) and $n\cdot x$ denote the classical action of $\mathbb{Z}$ over $G$ (i.e. $0$ for $n=0$, sum ...
2
votes
0answers
59 views
+50

Showing equality of 2 suprema in complete lattice

Let $(M,+,0)$ be a naturally ordered commutative monoid (i.e. such that the natural preorder is antisymmetric) such that $(M,\sqsubseteq)$ is a complete lattice. Then $(M,\sum^*)$ is a summation ...
1
vote
1answer
31 views

Show that $\left< \mathbb{Q}\left[\sqrt 2\right], < \right> \simeq \left<\mathbb{Q}, < \right>$

Show that $\left< \mathbb{Q}\left[\sqrt 2\right], < \right> \simeq \left<\mathbb{Q}, < \right>$, where $\mathbb Q$[$\sqrt 2$] is the smallest subfield of $\mathbb R$ containing $\...
4
votes
0answers
44 views

supremum of additive functions is additive

I need some help for one equality in the following proposition. It was a hint to conclude that $\sup\{f(\cdot):f\in\Phi\}$ is additive. I highlighted it blue. Ultimately I am interested in proving the ...
0
votes
1answer
22 views

Property of a totally ordered Field

One of the properties of a totally ordered Field $K$ is For all $ x , y , u , v \in ( K , > )$, then: $$x < y \wedge u < v \rightarrow x + u < y + v$$ I'm not sure what the above ...
0
votes
1answer
36 views

Distance of binary strings to produce the lexicographical order

Indexing objects like elements of a Cantor Set or nodes of a Binary Tree can result in a enconding system of binary strings like illustrated bellow: The illustrated indexes form a finite set, $$C_3=\...
1
vote
2answers
30 views

Commutative monoid with natural order is a poset

Let $(M,+,0)$ be a commutative monoid and write for $x,y\in M$, $x\leq y \iff \exists t\in M: x+t=y$. I want to show $(M,\leq)$ is a poset. I am stuck at showing antisymmetry. Obviously $x+0=x \...
1
vote
0answers
17 views

Proof that there are neither maximal elements nor minimal elements?

Let $X=\{2, 3, 4, \ldots\}$ and endow $X\times X$ with the order $$(x, y)\leq (z, t)\Leftrightarrow x|z\ \textrm{and}\ t|y.$$ I'm supposed to find the minimal and maximal elements of $X\times X$ with ...
0
votes
0answers
15 views

What's the characterization of injective objects in the category of posets?

According to https://en.wikipedia.org/wiki/Injective_object, the complete lattices form the injective objects for the class $\mathcal {H}$ of order-embeddings. However if we consider monic monotonic ...
0
votes
0answers
20 views

Strange problem about minimal and maximal elements?

I have the following problem: Let $X=\{2, 3, 4, 5, \ldots\}$ be ordered by division, that is: $$x\leq y\Leftrightarrow x\mid y,$$ and let $\mathcal{S}=\{(A, \leq_A): A\subset X\}$ where $\leq_A$ is ...
1
vote
0answers
20 views

Find the minimal and maximal elements of $P^*$?

Consider the set $\{1, 2, 3, 4\}$ and let $P^*:=P(\{1, 2, 3, 4\})-\emptyset$ be the set of all subsets of $\{1, 2, 3, 4\}$ excepting $\emptyset$. Then $P^*$ is ordered via inclusion as follows: $$A\...
1
vote
0answers
21 views

Hasse diagram: Reverse divisibility.

Consider the set $X=\{2, 3, 4, 5, 6, 7, 8, 9, 10\}$ endowed with the order $$x\leq y\Leftrightarrow y|x,$$ that is, $x$ precedes $y$ if and only if $y$ is a divisor of $x$. Can anyone check whether my ...
0
votes
1answer
28 views

If $f:X\rightarrow Y$ is an order isomorphism , then $f^{-1}:Y\rightarrow X$ is an order isomorphism .

Let $(X,\leq)$, $(Y,\leq ')$ be partially ordered sets. If $f:X\rightarrow Y$ is an order isomorphism between $X$ and $Y$, then the inverse function $f^{-1}:Y\rightarrow X$ is an order isomorphism ...
3
votes
2answers
56 views

Example of a preclosure that is not a closure

For a set $X$ we can define an operator $cl:\mathscr{P}(X)\rightarrow\mathscr{P}(X)$ satisfying for all $A,B\subseteq X$. $$cl(\emptyset)=\emptyset\tag{1}$$ $$A\subseteq cl(A)\tag{2}$$ $$cl(cl(A))=cl(...
2
votes
2answers
32 views

If $b$ is the largest member of $(X,\leq)$. how does $(a,b]$ become basic open set?

Let $(X,\leq)$ be a well-ordered set, Let $\mathscr T$ be the order topology on $X$. How do I prove that every interval of the form $(a,b]$ is open in $X$? Proof is given in the textbook: Case 1: ...
4
votes
2answers
79 views

Show that there is no other isomorphim

Recall: Let $(X,\leq)$, $(Y,\leq ')$ be two partially ordered sets. Let $f:X\rightarrow Y$ be a function such that $a\leq b \rightarrow f(a)\leq 'f(b)$ we say $f$ preserves order relation. If $f$ ...
1
vote
1answer
53 views

Morphism in posets.

I found an exercise which says: If $P$ is a partially ordered set and $\mathscr P$ the defining category, characterize monomorphism, epimorphism and isomorphism in $\mathscr P$. So, if there's at ...
4
votes
1answer
49 views

characterizing sets which are order-isomorphic to subsets of real numbers

Let $\Omega$ be an ordered set. We say that it is order-isomorphic to another totally-ordered set $E$ whenever there is a bijection $m:\Omega\to E$ satisfying $x<y$ in $\Omega$ if and only if $m(x)...
3
votes
2answers
63 views

Order Preserving Isomorphism from $(\mathbb{N},\leq)$ to $(\mathbb{N},\leq)$

Recall: Let $(X,\leq)$, $(Y,\leq ')$ be two well ordered sets. Let $f:X\rightarrow Y$ be a function such that $a\leq b \rightarrow f(a)\leq 'f(b)$ we say $f$ preserves order relation. If $f$ is a ...
1
vote
1answer
11 views

intersection of total orders

A graph $G$ with vertex set $V$ has $\dim(G) \leq d$ if and only if there exists a sequence $<_{1},<_{2}, \ldots , <_{d}$ of total orders on $V$ satisfying the following conditions: (1) the ...
0
votes
1answer
26 views

Let $(A,≤)$ and $(B,≤')$ be posets. Suppose the function $h:A→B$ satisfies $x≤y$ iff $h(x)≤'h(y)$ for all x and y in A. Prove that h is one-to-one.

Let $(A,≤)$ and $(B,≤')$ be posets. Suppose the function $h:A→B$ satisfies $x≤y$ iff $h(x)≤'h(y)$ for all $x$ and $y$ in $A$. Prove that $h$ is one-to-one. I attempted to prove by contradiction: ...
3
votes
1answer
39 views

A Maximal Order is a Total Order

A set $X$ together with a binary relation $\leq$ such that for all $x,y,z\in X$, O$1$. $x\leq x$ $O2$. $x\leq y$ and $y\leq x$ then $x=y$ $O3$. $x\leq y$ and $y\leq z$ then $x\leq z$ is called an ...
4
votes
1answer
116 views

Set or list compression

Apologies for poor use of terms, I do not understand enough of the problem to even ask the right questions. My main question is, what domain of mathematics is this problem and is it solved problem ...
5
votes
0answers
24 views

What is the smallest poset with automorphism group $C_n$?

I've recently been interested in finding small finite posets (and thereby finite $T_0$ topologies) with a given automorphism group. I came upon the paper of Barmak and Minian in which they provide an ...
2
votes
0answers
24 views

reference request: writing intervals of totally-ordered sets in a “nice” way

Let $\Omega$ be a totally-ordered set. We need to introduce some symbolism and terminology, which is all very natural and intuitive. If $A$ and $B$ are subsets of $\Omega$ we write $A<B$ whenever ...
1
vote
1answer
45 views

Show that total orders are maximal orders

A set $X$ together with a binary relation $\leq$ such that for all $x,y,z\in X$, $O1$. $x\leq x$ $O2$. $x\leq y$ and $y\leq x$ then $x=y$ $O3$. $x\leq y$ and $y\leq z$ then $x\leq z$ is called an ...
1
vote
0answers
38 views

Show the followed equality, mobius function

Suppose $P$ is a finite poset, and $f: P \to \mathbb{C}$. Is it true that $$\sum_{x_1<x_2<...<x_k}{(f(x_1)-1)(f(x_2)-1)(f(x_3)-1)...(f(x_k)-1)} = \sum_{x_1<x_2<...<x_k}(-1)^k \mu(0,...
1
vote
0answers
29 views

Order preserving injection $f$ from countably totally ordered set $S$ into $R$ with discrete image.

If $A$ is countable, totally ordered set, then there exists an order-preserving injection $f:S\rightarrow R$ , such that the image of $f$ is discrete subspace of $R$ (set of reals). I have no idea ...
0
votes
0answers
17 views

antisymmetry of partial order

Question: A is the set of all English words; (a,b)∈R if and only if a is no longer than b. Is it a partial order? When (a,b)∈R and (b,a)∈R, we only know the length of a is equal to the length of b. ...
1
vote
1answer
54 views

Decomposition in three of one part of a bipartite graph of a particular kind.

I think about one combinatorial problem and can not crack it yet. I introduce the statement in way of question about a bipartite Graph of BOYs and GIRLs. Suppose $n\in \mathbb{N}$, let $P_n$ be the ...
0
votes
1answer
29 views

In a partial order does every finite subset have a maximum?

If $≤$ is a total ordering on A, then every non-empty finite subset S of A has a least element and a greatest element. I was wondering whether this result is true if we replace "total ordering" by ...
1
vote
0answers
68 views

How to prove that a filter intersects all the dense sets?

Let $(\mathbb{P},\le)$ be a partial order and consider the following definitions $G\subseteq\mathbb{P}$ is filter iff $\forall p,q\in G\exists r\in G(r\le p\wedge r\le q)$ and $\forall p\in\mathbb{P}\...
1
vote
2answers
43 views

Whether partially ordered sets $(Z,\subseteq )$ and $(Q ,\subseteq )$ are isomorphic?

Let $Z= \left\{[k,l]:k,l \in \mathbb Z \wedge k \le l\right\}$ and $Q= \left\{[p,q]:p,q \in \mathbb Q \wedge p \le q\right\}$. Whether partially ordered sets $(Z,\subseteq )$ and $(Q ,\subseteq )$...
1
vote
1answer
42 views

Each ordered semigroup is cancellative: reference?

It is easy enough to show that $a+b < a+c\Rightarrow b < c$ holds in totally ordered semigroups. Indeed this must be very well known. Can anyone please provide a reference for this result? A ...
1
vote
1answer
57 views

Extend order on $\mathbb{Q}$ to $\mathbb Q(X)$

I struggle to show that there exists a unique order on $\mathbb Q(X)$ that extends the order on $\mathbb Q$ such that $\forall q \in \mathbb Q, ~X>q$.
1
vote
1answer
19 views

On chain conditions and Zorn's Lemma, again

I'm doing a introductory course on commutative algebra, and have just been introduced to the chain conditions. I know there's a lot of questions probably similar, but I haven't really understood this. ...
1
vote
1answer
28 views

Set of various order types of a set

Starting from the cardinal $|\Bbb N| = \aleph_0 = \beth_0$, we can generate a larger cardinal in two ways: Take the set of all subsets, generating the cardinal $\beth_1$ Take the set of all well-...
0
votes
1answer
43 views

How can I show every uncountable partial order is equal to the intersection of all its linear extensions?

Given an arbitrary partial order $P=(X,R)$ if for any $a,b\in X$ with $(a,b)\not\in R$ and $(b,a)\not\in R$ we define $R'=R\cup\{x\in X:(x,a)\in R\}\times \{x\in X:(b,x)\in R\}$ then I can show that $...
2
votes
1answer
34 views

Is there a word for a “connected component” of a partially ordered set?

When working with posets $(P, \leq)$, I often thought it would be useful to define a notion of “connected component” as follows: Def. Let $x,y\in P$. Define a “connectedness” relation $x\sim y$ if ...