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
votes
1answer
17 views

Order of an element in a finite group - what does it tell me? [on hold]

I get the basics on how to calculate the order of an element in a finite group, but not sure why I want to. When I find the order what does it allow me to do or know about the group? Real world ...
1
vote
0answers
14 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for $y=(y_1,y_2, ..., ...
0
votes
1answer
16 views

Partial ordered sets and supremum.

Let $A,B$ subsets of a partial ordered set $(X,\succeq)$, such that $A\subseteq B$. Suppose that $sup(B)$ exists, Do $sup(A)$ exists? I could prove that all upper bound of $B$ is an upper bound of ...
1
vote
1answer
26 views

Can the order on an ordered, cancellative monoid be extended to its Grothendieck group?

Suppose we have an ordered, cancellative monoid and we wish to apply the Grothendieck group construction to it. Can the total order be extended to the larger group? Example: consider the ordered ...
1
vote
1answer
57 views

Does this property have a name?

When I have a set of numbers such as $\Bbb Z$ and say I have some $n\in \Bbb Z$, if I put some lower and upper bounds on $n$, that is $a>n>b$, then there are finite options for $n$. Does this ...
2
votes
1answer
20 views

Log-determinant ordering for sum of positive definite symmetric matrices

If, for real positive definite symmetric $A, B, C$, $$\log\det (A+B) \geq \log\det(A+C)$$ then can it be said that $$\log\det(B) \geq \log\det(C)?$$ NOTE: A crude form of the reverse is certainly ...
1
vote
3answers
52 views

Let $\omega$ be the ordinal of the well ordered set $\mathbb{N}$, what does means $\omega^\omega$?

Let $\omega$ be the ordinal of the well ordered set $\mathbb{N}$, then we can define the ordered sum and product, and so the sum and product of ordinal. Is easy to see that ...
0
votes
0answers
35 views

Properties of Coefficients of Order Polynomials

I am working on a problem involving determining the order polynomial $\Omega_P(k)$ of a partial order $P$, which counts the number of order-preserving transformations/maps from $P$ to the $k$-chain ...
4
votes
1answer
67 views

Cantor's Theorem with Posets

Cantor's theorem states that we cannot construct an surjective map from $X \to \mathcal{P}(X)$ which can be rephrased as there is no $X$ such that $X \to \{0, 1\} \cong X$. I was wondering if this is ...
0
votes
0answers
24 views

Different definitions of completeness

I'm quite confused with these 3 definitions: (From Wikipedia) A partially ordered set is chain complete if every chain in it has a least upper bound. Definition 1 (From Wikipedia) A totally ...
1
vote
0answers
26 views

On properties of linear orders

I have a simple question. Let A={a,b,c,...} be a set and > a total strict order on $2^A$. Total strict order means that for any two subsets of A, say S and S', either S>S' or S'>S but not both. The ...
3
votes
0answers
44 views

Squares of adjunctions / Galois correspondences

$ \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\PS}{\mathcal P} \newcommand{\Idl}{\operatorname{Idl}} $ There are many situations where one encounters a square of things which are related by ...
3
votes
1answer
91 views

When a vector space will be a complete lattice?

Let $E$ a vector space, and let $P$ a strict cone in $E$ (i.e) $P\subset E$ verify: $$ \mathbb{R}^+ P\subset P \\ P+P\subset P\\ P\cap (-P)=\{0\} $$ So we can easily construct a partial order on $E$ ...
1
vote
0answers
45 views

Finite partitions of $\mathbb{N}$ and relations betweens sets of natural numbers

Suppose that $R\subseteq \mathcal{P}(\mathbb{N})\times\mathcal{P}(\mathbb{N})$ is a relation such that $(x,y)\in R$ only if $|x|=|y|$. Say that a partition $P$ divides a set $x$ if $x$ is the union ...
0
votes
1answer
20 views

An example of a lattice that's not totally ordered

The following is an excerpt from my textbook: A lattice need not be a totally ordered set. Consider the partially ordered set $(ω,D)$ where D is the relation on $ω$ defined by $x D y$ iff $x | ...
2
votes
3answers
28 views

$A$ is the power set of set $C$, and $S$ is the relation on $A$ defined by $x S y$ iff $x \subseteq y$.

The following is an exercise from my textbook: Let $C$ be a set and let $A=\mathcal{P}(C)$, the set of all subsets of $C$. Let $S$ be the relation on $A$ defined by $x S y$ iff $x \subseteq y$. ...
1
vote
1answer
37 views

Use the Well Ordering Principle to prove that every finite, nonempty set of real numbers has a minimum element

This is a textbook problem. Here's my "proof": Assume for contradiction there exists a finite, nonempty set of real numbers which doesn't have a least element, call it $C$; suppose there are $n$ ...
0
votes
2answers
25 views

$(A,\leq)$ is a partially ordered set. That each finite non-empty subset of $A$ has a $maxB$ implies $(A,\leq)$ is totally ordered.

My textbook contains the following exercise: Let $(A,\leq)$ be a partially ordered set. Prove that if each finite non-empty subset of $A$ has a greatest element, then $(A,\leq)$ is totally ...
2
votes
1answer
30 views

Classification of dense and complete linear orders

Question. Is there a decent classification theorem for linear orders satisfying all three of: Dense. Given a pair of elements $y,x$ with $y>x$, there exists $k$ satisfying $y>k>x$. ...
3
votes
3answers
41 views

Java comparator documentation: confused about the terminology “total order.”

I was recently reading the documentation for the Comparator type in the Java programming language. This type is used to let the programmer define custom ordering ...
5
votes
2answers
54 views

Why doesn't Zorn's lemma apply to $[0,1)$?

Consider the real interval $[0,1)$, this is partially ordered set (totally ordered actually). This set has a upper bound like $1$, and according to Zorn's Lemma each partially ordered set with a upper ...
2
votes
0answers
53 views

Proof of unboundedness of a set

Prove that $\{2^n : n \in \mathbb{N} \}$ is not bounded. Proof: By Induction; $2^n \geq n,\forall n \geq 1$. By Archimedean property $\mathbb{N}$ is not bounded above. Assume that $\{2^n : n \in ...
0
votes
2answers
30 views

Upper topology vs. Alexandrov topology

Let $(P, \le)$ be a poset. We define the following two well-known topologies over $P$. The upper topology has the principle upper sets, that is upper sets of the form $\{\uparrow x : x \in P\}$, as ...
0
votes
0answers
20 views

Representing an order relation with a real-valued function

Let $\succeq$ be a relation on a set $X$. The function $u: X\to \mathbb{R}$ represents the relation $\succeq$ if $x\succeq y \iff u(x)\geq u(y)$. I am looking for a good reference on questions such ...
3
votes
1answer
63 views

Are the hyper-reals countably transitive?

A hyper-real field is $ R^*=(R^N)_{/U}$ where $U$ is a free ultrafilter on $N$. If A and B are any countable order-isomorphic subsets of $R^*$, is there an order-automorphism of $R^*$ that maps $A$ ...
1
vote
0answers
12 views

Examples of Riesz homommorphisms and solid linear subspaces [closed]

Hi I'm looking for some standard examples of Riesz homomorphisms and solid linear subspaces.
0
votes
1answer
31 views

What does “descends to a partial order” imply?

For context: For $i \in \Sigma$, we let $[i]=\{j \in \Sigma: i \geq j \geq i\}$ and define $\Gamma_A := \{[i]:i \geq i\}$. The relation descends to a well-defined partial order on the set ...
0
votes
0answers
24 views

Relation between number coding in shortlex order for different alphabets

Let $X_r = \{ 0, 1, \ldots, r-1 \}$ and $X_b = \{ 0, 1, \ldots, b-1 \}$ be two finite alphabets with order's given by their numerical value. Consider the quasilexicographic (or shortlex) order on ...
0
votes
1answer
39 views

How many totally ordered sets can be constructed from a given finite poset?

For a finite poset $S=\{x_1,\cdots,x_n\}$, there are $k$ ordering relations $x_{k_0}>x_{k_1}$ ($k_0\neq k_1$) that generate all the ordering of the poset $S$. Now we want to make $(S,\geq)$ a ...
0
votes
1answer
8 views

Why a function from a product of $\omega$-complete partial order is continuous?

In “The Formal Semantics of Programming Languages” by Glynn Winskel, there is Lemma 8.10 in “8. Introduction to domain theory/3. Constructions on cpo's/2. Finite products” which is promised to be ...
1
vote
2answers
52 views

Orders with no anti-symmetry requirement?

A ordered/partially ordered set is required to satisfy the $x \leqslant y$ and $y \leqslant x$, $\implies x=y$ (antisymmetry) axiom. Are there any viable theories where this condition is weakened? ...
10
votes
1answer
192 views

Is there a non-trivial countably transitive linear order?

A linear order $<$ on a set S is countably transitive iff, whenever A and B are order-isomorphic countable subsets of S, there is an order-automorphism of S which maps A onto B. Does such an order ...
1
vote
1answer
31 views

Representing numbers by quasilexicographic ordered strings, formula for size of conversion between different alphabets

Let $X_r = \{ 0, 1, \ldots, r-1 \}$ and $X_b = \{ 0, 1, \ldots, b-1 \}$ be two finite alphabets with order's given by their numerical value. Consider the quasilexicographic (or shortlex) order on ...
2
votes
2answers
29 views

Order-preserving map between $X^*$ and $\mathbb N$ for some finite set $X$

Let $X = \{ 1, \ldots , r \}$ be $r$ symbols with $1 < 2 < \ldots < r$ and define on the set of all finite sequences $X^*$ the lexicographic ordering as given here on Wikipedia. Is it ...
1
vote
1answer
27 views

Lattices and Hasse diagrams

I would like to know which is the exact difference between lattices ans Hasse diagrams. In some cases, such as when lattices are used to represent maximal and minimal ideals, it seems to me that both ...
2
votes
2answers
49 views

Proof that any finite subset of a lattice has a supremum.

Let $C\subseteq D$ where $C = \{c_{1}, c_{2},\ldots, c_{n}\}$ and $D$ is a lattice. I believe that this supremum is $((c_1 \vee c_2)\vee c_3)\vee \ldots \vee c_n)$ (sorry about the notation). However ...
8
votes
2answers
92 views

Is the following a characterization of $\Bbb Q\cap\cal C$, where $\cal C$ is the Cantor set?

Let $A$ be an ordered set, with the following properties: $A$ is countable $A$ has a least and greatest element Between any two points with successors are points without successors; between any two ...
0
votes
2answers
23 views

Define a relation $D_n$ on $S$ by $xD_ny$ if and only if $x\mid y$. Determine if it's a poset.

Here is the question I am currently working on (screenshot): I'd appreciate some suggestions/guidance for part (a), proving that $D_n$ is a partial order. Reflexive: Let $x \in \mathbb{Z}$ ...
1
vote
1answer
60 views

Prove $\mathbb Q( \sqrt2)$ has only two orderings

I'm having trouble showing that there are only two unique orderings of $\mathbb Q$ restricted to square root of two. I can show that the rationals are ordered, but I can't seem to figure out how to ...
1
vote
0answers
15 views

Explain the compactness relation for elements of dcpos and also in a category if objects

The way below relation is used to define compact elements in a dcpo. Can someone explain compactness and an object way below itself. Also, when we abstract this relation to categories, where the ...
2
votes
1answer
38 views

Example of a Well-Ordered Class that is not Proper

I am currently studying well-ordered classes in the context of NBG set theory and I am trying to find a well-ordered class that is not proper. Here is the relevant definition of the terminology ...
4
votes
1answer
51 views

Any two countable atomless Boolean algebras are isomorphic

How to prove that Any two countable atomless Boolean algebras are isomorphic. This is an exercise of Jech - Set theory book for which I have some difficulty.
10
votes
5answers
434 views

Foundation of ordering of real numbers

This might be a silly question, but what is the mathematical foundation for the ordering of the real numbers? How do we know that $1<2$ or $300<1000$... Are the real numbers simply defined as ...
3
votes
1answer
35 views

Size of Totally Ordered Set with Countable Predecessors

Assume Choice. Let $S$ be a set, and $\trianglelefteq$ be a total order on $S$. If for all $s \in S$, the set $\{t:t\trianglelefteq s\}$ is countable, what are the possible cardinalities of $S$? ...
2
votes
1answer
27 views

$X$ connected in the order topology $\Rightarrow$ every $A\subset X$ that has an upper bound has a supremum

I have to prove $X$ connected in the order topology (w.r.t. a linear order <) $\Rightarrow$ every $A\subset X$ that has an upper bound has a supremum My attempt: Reason by contradiction: ...
0
votes
1answer
27 views

Filters and filter bases in order theory

Hi I would like to confirm the following ideas regarding filters in order theory: By definition I have that a filter is a subset of a poset $(P, \leq)$ which satisfies: $\mathcal{F}$ is non-empty. ...
3
votes
2answers
58 views

Showing $\lg(n!) = \Omega(n\lg n)$

I saw this equation in "Introduction to Algorithm" 3th edition in page 58 : $$\lg(n!) = \Theta(n\lg(n))$$ If $\lg(n!) = \Omega(n\lg(n))$ and $\lg(n!) = O(n\lg(n))$ then we can prove that. I can ...
3
votes
1answer
52 views

Order for sets in the real line

Consider the sets $[0,1]$ and $[1,2]$. I want to say that $[1,2]$ is greater than $[0,1]$. Is there a set order such that $$A \geq B \quad \text{if} \quad \inf A \geq \sup B.$$ What is the name of ...
0
votes
1answer
24 views

$R$ well-founded relation and $\forall y$, $\{x:xRy\}$ is finite implies $\forall y$, $\{x:xR^t y\}$ is finite (where $R^t$ is the transitive closure)

I am interested in proving the titular claim: $R$ well-founded relation and $\forall y$, $\{x:xRy\}$ is finite implies $\forall y$, $\{x:xR^t y\}$ is finite (where $R^t$ is the transitive closure) ...
1
vote
1answer
51 views

Topology on partially ordered set

Let $(X, \leq )$ be a partially ordered set. How would you define a topology on $X$ such that the closed sets are precisely the order-closed sets? Where $B \subset X$ is order-closed if ...