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
2answers
123 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
1
vote
1answer
29 views

Total function vs Partial function

I'm reading a lecture note in which the following functions ($fact_i : \mathbb{Z}_\perp → \mathbb{Z}_\perp$) for $i \in \mathbb{N}$ are NOT considered total: \begin{equation} fact_0(x) = \perp ...
1
vote
0answers
26 views

Prove/disprove questions on equivalence relations and ordered sets

If $R$ is an equivalence relation and a partial order over $A \neq \emptyset$ then every equivalence class contain at least one element. If $(A,\le)$ an ordered set, and $a\in A$ is a single ...
2
votes
1answer
45 views

If a net is too big, convergence tells us very little?

I'm just learning about nets. It occurs to me that sometimes $x_{\alpha} \to x$ doesn't tell us much at all. Consider the directed set $J:= \{(U,x)\in \mathcal{P}(X) \times X: x \in U \}$, $(U,x) ...
2
votes
2answers
98 views

Is every continuous function measurable?

In non-Hausdorff topology it is standard to define the Borel algebra of a topological space $X$ as the $\sigma$-algebra generated by the open subsets and the compact saturated subsets. Recall that a ...
1
vote
1answer
41 views

Describing orders on sets $\{1,2,3,4\}$ and $\mathbb N$ with minimal/maximal/maximum/minimum elements

Describe all the partial orders on $\{1,2,3,4\}$ where the set of minimal elements are $\{2,4\}$ and the set of maximal elements is $\{1,3\}$ Describe all the partial orders on $\{1,2,3,4\}$ ...
0
votes
0answers
28 views

Has anyone used the isomorphism with $\Bbb{N}_{\gt 0}$ as a monomial ordering?

Let $R[x_1, x_2, \dots]$ be a ring of formal polynomials in a countably $\infty$ number of indeterminates $x_i$, over a commutative ring $R$. The commutative monoid $X = \{ x^e = x_1^{e_1} x_2^{e_2} ...
2
votes
1answer
31 views

What is the meaning of $<$ in a preorder?

Let $(P,\le)$ be a preorder, i.e. $P$ is a set and $\le$ is a relation on it that is reflexive and transitive. In this context for myself I can find two interpretations for the symbol $<$ 1) ...
6
votes
1answer
82 views

Terminology in forcing

In the context of forcing one reads the relation $p \leq q$ in a poset $P$ as "$p$ extends $q$". A typical example is the poset $P$ of finite partial functions, where one defines $p \leq q$ when $q ...
1
vote
0answers
23 views

Has an order with this property a special name?

If $a$ is an element in a preorder then you can eventually go 'a step back' (and repeat this) in the sense of finding an element with $b\leq a$ and not $a\leq b$. Is there a special name for ...
0
votes
1answer
14 views

Every admissible ordering on a countably infinite monoid is induced by an isomorphism onto $(\Bbb{N}, \cdot)$.

Let $fg$ mean the functional composition of functions $f, g$. Let $M$ be a countably infinite, commutative, multiplicative monoid and let $f : M \to (\Bbb{N}_{\gt 0}, \cdot)$ be an isomorphism. ...
2
votes
1answer
27 views

Continuity and Leximin

Consider a relation $\geq$ over the set of real-valued vectors. We say that $\geq$ is continuous if for any positive integer $n$, and any $\pi\in\mathbb Z^n,u\in\mathbb R ^n$ we have that the sets ...
3
votes
2answers
30 views

All tree orders are lattice orders?

Say that a set is tree ordered if the downset $\downarrow a =\{b:b\leq a\}$ is linearly ordered for each $a$. In a comment, Keinstein says that such sets are also semi-lattices, provided they are ...
0
votes
0answers
27 views

Addition on well ordered sets not-commutative by showing $[0,1) +_o \mathbb{N} =_o \mathbb{N} \neq_o \mathbb{N} +_o [0,1)$

My goal is to show that addition on well ordered sets are non-commutative by showing that, $[0,1) +_o \mathbb{N} =_o \mathbb{N} \neq_o \mathbb{N} +_o [0,1)$ Some definitions (let A and B be ...
4
votes
4answers
68 views

Number of join-irreducible elements of a lattice: is it monotonic?

Let $\mathcal L$ be a sub-lattice of $\mathcal P(X)$, where $X$ is a finite set. Denote by $\mathcal I(\mathcal L)$ the set of union-irriducible elements of $\mathcal L$ (i.e. $A\in \mathcal ...
2
votes
0answers
33 views

Is every sub-lattice of $\mathcal P(X)$ isomorphic to a sub-lattice of $\mathcal P(X')$ containing a singleton set? [duplicate]

Let $X$ be a finite set. $\mathcal{P}(X)$ denotes the set of all subsets of $X$. Let $\Gamma$ be a sub-lattice of $\mathcal{P}(X)$, i.e. $\Gamma$ is a collection of subsets of $X$ closed under union ...
1
vote
1answer
53 views

What is $|Aut(D_n,|)|$?

Let $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ with the $p_i$ distinct primes and $ \alpha_i\in \Bbb N$. Just to check if I'm correct, is it true that $k!$ is the number of order-isomorphisms of the form ...
0
votes
1answer
109 views

Is every sub-lattice of $\mathcal P(X)$ isomorphic to a sub-lattice of $\mathcal P(X')$ containing singleton sets?

Let $X$ be a finite set. $\mathcal{P}(X)$ denotes the set of all subsets of $X$. Let $\Gamma$ be a sub-lattice of $\mathcal{P}(X)$, i.e. $\Gamma$ is a collection of subsets of $X$ closed under union ...
1
vote
0answers
17 views

Proving isomorphism in lattices

The question is as follows: Let f be a monomorphism from a lattice $L$ to a lattice $M$.Show that $L$ is isomorphic to a sublattice of $M$. My attempt: Since $f$ is a monomorphism from a lattice ...
2
votes
1answer
27 views

A problem concerning a partially ordered in $\omega$ and two chains.

Assume that $P=\left\langle\omega, \preceq\right\rangle$ is a partially ordered set such that for each $n \in \omega$ there are two chains $A_n$ an $B_n$ in $P$ such that $n \subset A_n \cup B_n$. ...
1
vote
1answer
12 views

extension of an increasing function over a lattice

Let $X$ be a finite set. $\mathcal{P}(X)$ denotes the set of all subsets of $X$. Let $\Gamma$ be a sub-lattice of $\mathcal{P}(X)$, i.e. $\Gamma$ is a collection of subsets of $X$ closed under union ...
2
votes
1answer
71 views

what kind of relationship is “is prefix of”?

Consider the "is prefix of" relationship on a set that corresponds to the words of some alphabet. E.g. "ab" is prefix of "abc". This relationship is: antisymmetric transitive reflexive ("ab" is a ...
0
votes
3answers
57 views

Finite set with $\sup\{S\} \notin S $

Just a quick question about sets. Can anyone here think of an example of a finite set $S$ where the $\sup\{S\} \notin S $ ? I found this on a past exam paper for college, and am unsure if there ...
1
vote
0answers
15 views

Hasse Diagrams - Relations

I have the following question: Draw the Hasse diagram for the following partially-ordered set: The relation $X$ is a subset of $Y$, on the set $\{ \{0\}, \{2\}, \{0,1\}, \{0,2\}, \{2,4\}, ...
1
vote
1answer
33 views

Existence of net of positive real numbers

Does for every totally ordered infinite set $T$ with no greatest element, there exist a net $(a_t )_{t\in T}$ of positive real numbers which is convergent to $0.$ ?
3
votes
0answers
24 views

(Almost) co-free objects?

another naming question from me, which comes up because I try to use category theory as a compass in developing some (new or not?) order-theoretic notions. According to my book (The Joy of Cats, ...
1
vote
0answers
16 views

Small posets with prescribed number of linear extensions

Given a natural number $n$, I want to construct a (finite) poset $P_n$ such that $P_n$ has exactly $n$ linear extensions. This can always be done, for instance taking $P_n$ to be a chain of length ...
1
vote
2answers
63 views

Introductions to posets on algerbaic structures (Everything I need to know about them)

I need a good and complete introduction to Tree-like orders and partial orders on algebraic structures with one operations. I accept basic texts too. I'm looking for free online texts mostly because ...
3
votes
2answers
58 views

total order on finite dimensional vector space over $\mathbb{R}$

We know that, If we start with a basis of a finite dimensional vector space $V$ over $\mathbb{R}$ by using lexicographic ordering with respect to that basis, we have a total ordering $\lt$ on $V$ ...
0
votes
2answers
31 views

Order of the subgroup <g>H of G

This is an old exam question I'm trying to solve: Having a group $G$ and $H$ a normal subgroup of $G$ with order $n$ and taking $g$ in $G$ to be such that $gH$ has order $m$ in $G/H$, I wish to prove ...
0
votes
1answer
37 views

Something interesting about partial orders to show to my students

I'm looking for some interesting examples or theorems about partial orders to show to my students, can be also some fundamental theorem such as an analogue of this theorem on equivalence relations. ...
0
votes
0answers
46 views

Exercise 1.17 from Bell & Slomson's Models and Ultraproducts

I'm attempting to prove the following theorem left as an exercise from Bell & Slomson's Models & Ultraproducts (1969). I'd like to know whether my attempted proof is correct, and if not, I'd ...
6
votes
1answer
68 views

$\mathbb{R}$ and $\mathbb{R}\setminus \{0\}$ are not isomorphic as linear orders.

Informal argument So, we know that $\mathbb{R}$ with its usual topology is connected, and of course $\mathbb{R}\setminus\{0\}$ is not. Any $``$supposed" isomorphism should grant us a homeomorphism ...
2
votes
1answer
40 views

The number of partial orders of finite set.

My question is about the number of partial orders of finite set. For example, if $S=\{a, b\}$, then there are 4 partial orders $\{ (a, a), (b, b) \}$, $\{ (a, a), (a, b), (b, b) \}$, $\{ (a, a), (b, ...
1
vote
1answer
29 views

Showing another result on distributive, complemented lattice

Currently reading Bell & Slomson's Models & Ultraproducts. Looking for clues, tips hints for showing the following: Let $L$ be a distributive, complemented lattice. Then for any $x$ $\in$ ...
1
vote
1answer
58 views

Given a collection of ordered sets, find minimal order-preserving superset

Say I have some collection of ordered sets $C = \{S_i\}$. Is there an efficient way to determine the minimal ordered set $S^*$ such that each of the original $S_i \subseteq S^*$, with order ...
1
vote
0answers
48 views

How many different proper subfields does $K$ have, where $K$ is a field of order$p^n$?

If $p$ is a prime, and $d$ is an integer greater than or equal to 1. Let $n= p^d$, then there exists $K$ being a field of order $p^n$. But how many different proper subfields does $K$ have? The ...
0
votes
0answers
18 views

Theorem on complemented lattices

I'm looking through the book Models and Ultraproducts by Bell & Slomson, and I'm checking that my proof is correct (exercise 1.13). I'm pretty sure it is, but I thought I'd post it anyway. It is ...
0
votes
0answers
21 views

Operation table of Hasse diagram

Consider the following Hasse diagram: My book gives the following join and meet operation tables for this diagram: $$\begin{array}{|c || c | c|} \hline Subset & x \wedge y & x \vee y \\ ...
4
votes
1answer
74 views

Do any familiar adjunctions arise from this construction?

I was pondering an answer that user Andreas Blass provided to an old question of mine and wondered if the following construction cropped up anywhere other than the example I will provide. For any set ...
2
votes
2answers
51 views

The length of a poset

Let $(X,\le)$ be a (nonempty) poset. The length of $(X,\le)$ is defined by $$\operatorname{len}(X)=\sup\{|C|-1\mid C\subseteq X \text{ is a chain} \}$$ Can $\sup$ be replaced by $\max$? (without ...
0
votes
1answer
26 views

Are there necessary and sufficient conditions for Krein-Milman type conclusions?

This, the third of three self-answered questions, contains a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The second question is here. ...
2
votes
1answer
29 views

Properties of the Majorization Order on $\mathbb{Z}^n$

I'm looking for background material on the majorization (aka dominance) order over $\mathbb{Z}^n$ (rather than over partitions). Let $v=(\psi_0,\dots,\psi_{n-1})$ and $u=(\phi_0,\dots,\phi_{n-1})$ ...
0
votes
1answer
13 views

Conditions for augmenting a collection of sets so that the new sets are small but the hull is large?

This is the second of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The third ...
0
votes
1answer
29 views

Are there necessary and sufficient conditions so that every element in a partially ordered set is either the least element or in the upset of an atom?

This is the first of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The second question is here. The third ...
0
votes
1answer
44 views

Constructive fixed-point theorems where finite iteration yields the fixed point

I would like to show that $p$, a fixed point of some effective map $f : S\rightarrow S$, can be constructed effectively. Ideally, I would like there to exist a finite $n$ such that $p = f^n(p_0)$, ...
1
vote
1answer
119 views

Exercise in Well Orderings

Prove that if $\prec$ is a well-ordering on a set X and if $Y \subseteq X$, then $\prec_Y=\{(x,y) \mid (x \in Y) \wedge (y \in Y) \wedge (x \prec y)\}$ is a well ordering on Y. I am a little ...
1
vote
0answers
24 views

Set theory chain proof help!

Let $A_i$ be a partially ordered set and $C_i$ a chain of $A_i$. Order $A_1\times A_2$ lexicographically. Prove that $C_1\times C_2$ is a chain of $A_1\times A_2$. This is a set theory proof ...
0
votes
1answer
19 views

Look for the group members $\left ( (\mathbb Z/24\mathbb Z)^*,\underset{24}{\odot} \right )$ and calculate their orders.

Look for the group members $\left ( (\mathbb Z/24\mathbb Z)^*,\underset{24}{\odot} \right )$ and calculate their orders. The elements are $\overline1,\overline2,\ldots,\overline{23}$. Have the ...
0
votes
1answer
20 views

Evidence about the group $\left ( (\mathbb{Z}/p\mathbb{Z})^*,\underset{p}{ \odot} \right )$

Be $p$ an odd prime number. Show that the group $\left ( (\mathbb{Z}/p\mathbb{Z})^*,\underset{p}{ \odot} \right )$ has a unique element of order $2$, namely $\overline{p-1}$, and show that ...