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

2
votes
1answer
97 views

Every increasing function from a certain set to itself has at least one fixed point

I need a hint for the following question: Let $S$ be a nonempty ordered set such that every nonempty subset $E\subseteq S$ has both a least upper bound and a greatest lower bound. Suppose $f:S ...
3
votes
2answers
61 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
33 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 ...
2
votes
3answers
123 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
50 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 ...
8
votes
1answer
87 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
49 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
60 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
53 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
20 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
26 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
75 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
53 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
34 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
37 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
17 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
35 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
45 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
126 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
27 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
20 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 ...
1
vote
1answer
23 views

Be $G=\{ e,g_1,g_2,\ldots, g_n \}$, $|G|=n+1$. Suppose $G$ has a unique element of order $2$, say $g_1$. Show that $eg_1g_2\ldots g_n=g_1$.

Be $G=\{ e,g_1,g_2,\ldots, g_n \}$ an abelian group of order $n+1$. Suppose $G$ has a unique element of order $2$, say $g_1$. Show that $eg_1g_2\ldots g_n=g_1$. I have serious difficulties with ...
0
votes
1answer
43 views

Proving questions about posets

How do I tackle a proof about posets? I have know idea how to approach this problem. Thanks! Prove that if all subsets of a poset P have least upper bounds, then all subsets of P have greatest lower ...
3
votes
0answers
40 views

Prove that for every 2 elements in the set F of all functions from N to N, there's an element in F that's bigger than both

let there be $\ F$ the set of all functions from $\ N \rightarrow N$. K is a relation on F, for every f,g$\in$F , (f,g)$\in$K $\leftrightarrow$ for all $\ n\in N$, $\ f(n)\leq g(n)$ Prove that for ...
0
votes
1answer
47 views

How to show a quasi-order ~ on a set S with relation // induces a partially ordered relation?

Let ~ be the quasi-order relation. and let // be defined as the relation s~t and t~s(s,t elements of S). Show that ~ induces a partially ordered relation on the set of equivalence classes relation //, ...
0
votes
1answer
29 views

Building an antichain in a finite poset

Given some finite poset $P$ we would like to find an antichain $A$ which intersects each maximal chain. How to do that? Note that each chain $C$ and each antichain $A$ intersects at one element as ...
1
vote
1answer
71 views

Order of cycles in graph

In a school assignment, I am to use contradiction to prove that if a graph is bipartite then all of its cycles have even order. In this context, what does it mean for a cycle to have even order? I ...
1
vote
1answer
63 views

How many ways can we totally order a set $X$ (but not necessarily the whole set $X$, perhaps just a subset) up to isomorphism?

Here's Attempt #2 at asking this question. Suppose $X$ is a set (not necessarily finite), and let $T$ denote the collection of all totally ordered sets $(A,\leq)$ such that $A \subseteq X.$ Now let ...
3
votes
2answers
38 views

Isomorphism of intervals of a distributive lattice

Let $P$ be a distributive lattice and let for $a,b \in P$ by $a \land b$ and $a \lor b$ denote the usual notion of infimum and supremum. How can I show the following isomorphism? $$[a \land b , a ...
0
votes
1answer
136 views

Show that a particular set is a poset

I would like to know if my understanding of the concept of a poset is correct. From what I've learnt from the class: A poset must be transitive, reflexive, and antisymmetric. Am I right? Therefore, ...
0
votes
1answer
24 views

Going down from filters to sets for specific relations

Let $\mathfrak{A}$ be a bounded lattice. I call a $2$-staroid a relation $f\in\mathscr{P}(\mathfrak{A}\times\mathfrak{A})$ such that $i\sqcup j \mathrel{f} b\Leftrightarrow i\mathrel{f} b\vee ...
1
vote
2answers
51 views

Lattice from Preorder

I have seen many examples defining a lattice over a partially ordered set $(P, \sqsubseteq)$ together with a greatest lower bound $\sqcap$, a least upper bound $\sqcup$ and a top $\top$, and bottom ...
1
vote
1answer
51 views

Factor congruences of non trivial Lattices

A pair of congruences $\theta$ and $\theta^*$ are called factor congruences if $\theta \vee \theta^*$ = full congruence. $\nabla$ $\theta \wedge \theta^*$ = trivial congruence. $\triangle$ I need ...
0
votes
1answer
30 views

Chains of Well-ordered sets

Let $\{X_i\mid i\in I\}$ be a chain of sets and $\{R_i\mid i\in I\}$ be the corresponding chain of relations such, $R_i$ well orders $X_i$. Show that $\bigcup_{i\in I}R_i$ well orders $\bigcup_{i\in ...
2
votes
1answer
78 views

Does the empty set have a supremum or infimum? [duplicate]

I actually dont need this question to be answered for university or something, it was just a discussion I had with a friend. Does the empty set have an upper or lower bound? Since the supremum is ...
1
vote
1answer
43 views

define an order relation with respect to which …

Let $(S;<)$ and $(T;<')$ be two well-ordered sets. On $S \times T$, define an order relation with respect to which it becomes a well-ordered set. Give proofs for your answer. I was thinking ...
0
votes
0answers
36 views

Help with Quotient Groups, Order in D4.

What group is D4/ isomorphic? |D4/| = 8/2 = 4 so it can be isomorphic to V or Z4. How can I determine which group is it isomorphic to? I know that V (Klein-4 Group) is noncyclic and abelian and Z4 ...
5
votes
2answers
125 views

If a finite poset has greatest and least elements, is it a lattice?

Let $P$ be a finite partially ordered set with elements $0$ and $1$ such that $0 \le x \le 1$ for any $x \in P$. Does it follow that $P$ is a lattice? If not, what is a counterexample? I believe this ...
0
votes
0answers
43 views

How to show a directed set always has a “largest element” using induction

I know induction from my lower division classes, but have no idea what to do when it comes to sets. For example a directed set is such that every two elements has an upperbound. We are looking at ...
0
votes
1answer
44 views

Find a voting system - possibly Schulze Method

I remember the Schulze Method from back when I was studying Econ... that was years ago and my math isn't the greatest, go easy on me. We are piloting a project to make a to-do list app for teams, I'm ...
0
votes
1answer
22 views

Prime order of a number

Prove that if $a^p=e$ where $p$ is a prime number, then $a$ has order $p$ ($a\ne e$). Perhaps I should prove this using the contrapositive? Assume that $p$ is not the order of $a$, meaning there ...
1
vote
1answer
28 views

Notation/terminology: Existence of a nonleast element which is less of any element of a set

Let $A$ is a subset of a partial order $X$. Are there any name and/or notation for the following predicate $P(A)$? $P(A)$ iff there is a non-least element $x$ of $X$ which is a subelement of each ...
3
votes
1answer
81 views

What are some examples of “homogeneous” linear orders, other than $\mathbb{R}$ and $\mathbb{Q}$?

Let $L$ denote a linear order that is unbounded. Then it may or may not satisfy: Globally homogeneous. For all $x,y \in L \cup \{-\infty,\infty\}$, if $x < y$ then the interval $(x,y)$ is ...
1
vote
3answers
42 views

For a set $\mathbb{X}$ given order relation extended from that of $\mathbb{R}$, if $\mathbb{X} \supseteq \mathbb{R}$ then $\mathbb{X} = \mathbb{R}$?

For a set $\mathbb{X}$ given order relation extended from that of $\mathbb{R}$, if $\mathbb{X} \supseteq \mathbb{R}$ then $\mathbb{X} = \mathbb{R}$ ? Motivation for this question rose from an ...
1
vote
1answer
66 views

A set with a supremum and an infinum inside

What is the name of a set $A$ that has its infimum $i \in A$ and a supremum $s \in A$? Examples: $[0,1]$ has a supremum $1$ and an infimum $0$ which are inside $[0,1]$. $\{0,1,2,3\}$ has a supremum ...
0
votes
0answers
20 views

Regularization for unordered vectors

Let suppose we have two vectors u, v $\in \mathbb{R}^n$ and we want a function that returns $0$ if the ordering of the elements of both vectors are the same or a positive number otherwise, where the ...
1
vote
0answers
17 views

Recommendation for Order Theory texts

Order Theory, Lattice Theory, or any directly relatable subject is not taught at my university, and quick searches don't give much clue into good textbooks for the subjects. My question is: what are ...
1
vote
0answers
30 views

Order-preserving embeddings

(Follow-up to Existence of a utility function on the reals.) Say we have a totally ordered set $X$ which has a countable, dense subset $C$. I believe we can find an $f:C\to\mathbb R$ which is ...