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

Positive elements of a $C^*$-algbera form a poset

My knowledge of $C^*$-algebras is very little. We call an element positive if $a=b^*b$ for some $b$ and make a relation on all positive elements by saying $$ b \geqslant a \iff b-a \text{ is ...
2
votes
1answer
26 views

Is there a nice characterization of those posets in which $\vartriangle_P$ is transitive?

Whenever $P$ is a poset and $x,y$ are elements of $P$, write $x \vartriangle y$ to mean that $x$ and $y$ have a lower bound. Then $\vartriangle_P$ is always reflexive and symmetric, but it may or may ...
3
votes
1answer
38 views

Categorial description of the subposet of $\prod_{i \in I}P_i$ of all $x \in \prod_{i \in I}P_i$ with $\{i \in I \mid x_i = \bot_{P_i}\}$ cofinite

By a grounded poset, I mean a poset $P$ with a least element $\bot_P$. Definition. Whenever $P$ is a family of grounded posets, write $\bigotimes_{i \in I}P_i$ for the subposet of $\prod_{i \in ...
0
votes
0answers
18 views

union of directed sets is directed

I try to prove below theorem "any union of directed sets is directed". I have tried as below Let $\mathcal{D}=\{D_i:i\in I\}\subseteq \mathcal{P}(P) $ , where $D_i$ is directed subset of ...
2
votes
2answers
63 views

When multiplying by $i$ in inequalities, does the sign flip?

Take $1>-1$, when you multiply by $-1$, to get $-1<1$ you have to flip the sign. What if you are multiplying by $i$? Would you flip the signs? If you didn't it would net the expression ...
0
votes
1answer
68 views

Does there exist an amazing poset that is neither totally-ordered nor well-founded?

Definition. Let $P$ denote a poset. Then $P$ is amazing iff every $A \subseteq P$ has the property that if $A$ has a unique minimal element (call it $m$), then $A$ has a minimum element (namely $m.$) ...
0
votes
1answer
48 views

A question about cofinal totally ordered sets.

Let $A$ be an uncountable set, and let $L$ be the poset consisting of all finite subsets of $A$ (the ordering on $L$ is inclusion). Show that $L$ does not have a totally ordered cofinal subset. I am ...
0
votes
0answers
32 views

mapping functions for power set graphs

Let $G(\mathcal{P}(n),E)$ be a power set graph for $[n]$ elements with the inclusion relation. The width of such graph is known by Sperner's theorem $w=\binom{n}{n/2}$. By Dilowrth's theorem we can ...
0
votes
1answer
38 views

Notation for rank of weakly ordered elements

I'm looking for a mathematical notation for the following algorithm where $D$ is a diagonal square matrix and $w$ a scalar value. Sort $D$ by the diagonal entries ascending for the first entry ...
1
vote
1answer
27 views

Number of linear extensions

Let $le(X, \preceq)$ denote the number of linear extensions of a partially ordered set $(X, \preceq)$. Prove $le(X, \preceq) = 1$ iff $\preceq$ is a linear ordering $le(X,\preceq) = n!$ where $n = ...
2
votes
1answer
23 views

Composition of permutations is an equivalence relation

For a permutation $p : X \rightarrow X$, let $p_k$ denote the permutation arising by a $k$-fold composition of $p$, i.e. $p^1 = p$ and $p^k = p \circ p^{k−1}$ . Define a relation $\approx$ on the set ...
2
votes
1answer
29 views

Prove that if X is well-ordered, there is no strictly decreasing sequence of elements in X.

Im not sure how to go about this. I know this isn't correct but so far this is all I can come up with. Assume that $(x_i)$ is a strictly decreasing sequence in $N$. Then we can say that $x_i$ such ...
1
vote
1answer
22 views

(Partial) symmetry order for matrices

Does there exists commonly used ( possible partial) orderings which would rank matrices as a function of their "degree of symmetry"? I am thinking one could for instance have $\succeq_{SYM}$ defined ...
1
vote
0answers
26 views

Uniqueness of smallest element in poset

Prove that a smallest element, if it exists, is determined uniquely. This is follows directly for definition. An element $a \in X$ is called the smallest element of $(X, \preceq)$ if for every $x \in ...
0
votes
0answers
24 views

Summarize binary sequences

I have a length $n$ sequence of elements $\{0,1\}$ (e.g. $0110$). Elements more to the right are more valuable. This defines a partial order for each set with a fixed number $k$ of $1$'s. For example ...
0
votes
1answer
37 views

Construction of uncountably many non-isomorphic linear (total) orderings of natural numbers

I would like to find a way to construct uncountably many non-isomorphic linear (total) orderings of natural numbers (as stated in the title). I've already constructed two non-isomorphic total ...
0
votes
2answers
34 views

Is necessarily a total order on $R^n$ a bijection on $R$?

I don't think it's true but: is necessarily a total order on $R^n$ equivalent to a bijection on $R$? If someone knows how to show that is true, or false... Thanks
6
votes
1answer
40 views

Can the order relation on $\mathbb{R}$ be recovered from the topology?

It's well-known that the usual topology on $\mathbb{R}$ is induced by the order relation, since the open intervals $\{(a, b) : a < b\}$ are a base for the topology. I am wondering if you can go ...
0
votes
1answer
34 views

Orders of Cosets

Let H be a normal subgroup of G and for any $g \in G$ that $|g|=n$ and $|G/H|=m$. Suppose the $gcd(n,m)=p$ where $p$ is prime. Show that for any $ a\in gH$, then $a^p\in H$. Could I get some help on ...
-1
votes
1answer
18 views

Monotonicity of a sequence of length 1 or 0

A sequence or list $a_i$ is said to be strictly monotonically increasing if for each pair of adjacent elements the successor is greater than its predecessor, or: $a_i < a_{i+1}$. But what if there ...
1
vote
1answer
49 views

Does $f ≥ g$ always imply $f^{-1} ≤ g^{-1}$ for invertible $f, g$?

If $I = (I, ≤)$ and $J = (J,≤)$ are linearly ordered sets, does $f ≥ g$ awalys imply $f^{-1} ≤ g^{-1}$ for invertible $f, g \colon I → J$? This is easy to prove if $f$ and $g$ are assumed to be ...
1
vote
1answer
28 views

Lattice of a POSET Realtion

Given a set $S=\{1,2,3,4,5,6,7,8\}$, defined by a partial order relation Divisibility. Now consider all 4 elements containing sub-graphs, out of which $\{1,2,4,8\}$ is a Lattice obviously . Is ...
1
vote
1answer
26 views

Non strictly convex “singleton” preferences

A relation $\succeq $ over a vector space $X$ is rational if it is transitive and complete. We say $x\succ y$ iff $x\succeq y$ and NOT $y \succeq x$ Moreover $x\sim y$ iff $x\succeq y$ and $y ...
0
votes
0answers
17 views

About Knaster-Tarski theorem

The Knaster-Tarski theorem states the following: Let $L$ be a complete lattice and let $f : L → L$ be an order-preserving ...
0
votes
0answers
24 views

Kleen fixed-point theorem and complete lattice

The Kleene fixed-point theorem states the following: Let $(L, \sqsubseteq)$ be a CPO (complete partial order), and let $f : L → L$ be a Scott-continuous (and therefore monotone) function. Then $f$ ...
0
votes
1answer
18 views

Definition of complete partial order and difference with complete lattice

According to this wiki page, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). Whereas, the ...
0
votes
0answers
32 views

Determine maximal, minimal, least and greatest elements.

R = {(0,0),(1,0),(2,0),(2,2),(3,0),(3,1),(3,2),(3,3)}. Is it 0 / \ ...
2
votes
2answers
108 views

Counting permutations that respect a partial order

Suppose you have three kinds of coins, say: pennies, nickels, and dimes. Each penny has a unique date, likewise for nickels and dimes. (A penny and a nickel may have the same date, etc.) How many ways ...
0
votes
0answers
22 views

What are such pairs of monotone mappings?

Let $P, P'$ be some partial orders and $f$ and $g$ two monotone mappings of type $P \to P'$. Consider the property $g(f(x)) \leq f(x)$, for all $x \in P$. My questions: Have you encountered such ...
2
votes
2answers
46 views

Prove that $(\mathbb{N},\le)$ and $(\mathbb{Z}, \le)$ are not order isomorphic

I want to prove that $(\mathbb{N},\le)$ and $(\mathbb{Z}, \le)$ are not order isomorphic. So what I want to show is that the following is not true: $$x \le_\mathbb{N} y \iff f(x) \le_\mathbb{Z} ...
2
votes
5answers
60 views

Well-ordered set with greatest element is compact

Let $X$ be a well-ordered set with a greatest element $\alpha$. We consider all sets of the form $]x,y]$ where $y \in X$ and $x$ is either another element of $X$ or the symbol $\leftarrow$ (the ...
2
votes
1answer
267 views

bijective homomorphisms between non isomorphic posets, example , explanation needed

Could someone please give a super simple example of a "bijective homomorphism between a non isomorphic poset"? I don't understand the sentence marked by green in the picture taken from Awodey's book. ...
1
vote
1answer
39 views

Forcing a functor to map to a given set

Let $(X, \leq)$ be a poset and $J$ a small category. Let $S$ be a subset of $X$. Viewing $(X, \leq)$ as a category, does there exists a functor $F: J \rightarrow (X, \leq)$ such that $\{F(j)\}_{j \in ...
5
votes
1answer
66 views

Is every linear ordered set normal in its order topology?

I'm trying to prove (or disprove) that every linear ordered set $(X, <_X)$ is normal in its order topology. I was able to prove $(X,<_X)$ is hausdorff, simply by taking two open intervals with ...
2
votes
2answers
72 views

Connection between monads and posets?

I understand this is broad, but could any elucidate and/or direct me on which structures, areas, and objects to study to get a deep understanding of the relationship between monads and partially ...
1
vote
0answers
29 views

Partially ordered sets

I have a question on Posets. Suppose we have $P = \{3, 6, 9, 18, 7, 14\} $ ordered by divisibility. We want to partition $P$ to subsets so that each two elements in each subset are related directly ...
0
votes
2answers
43 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
0
votes
0answers
15 views

How do you count a grouping without a sequential count?

So, rather than explaining how this problem pertains to the actual situation I think its easier and a great deal less work to give you a situation that you can visualize. Imagine a person who has ...
1
vote
0answers
25 views

Subsets of $ \mathbb Q $ of order type $ \omega^{\alpha}$ for each countable ordinal $\alpha $.

My introductory text in Set Theory (Stillwell) includes an exercise (6.3.1) asking for an explicit example of a subset of $ \mathbb Q $ or order type $ \omega^2 $. This seems straight forward enough. ...
2
votes
1answer
33 views

Mapping (any, not only bijection) from $\mathbb{R}^2$ to $\mathbb{R}$ that preserves lexicographic order?

Is there a (not necessarily bijective) mapping $f \colon \mathbb{R}^2 \rightarrow \mathbb{R}$ that preserves lexicographic order? That's to say, we'd need to have $f(x_1, x_2) \leq f(y_1, y_2)$ iff ...
1
vote
1answer
27 views

I have a question about infinite partially ordered sets.

If I have an infinite partially ordered set $P$ where every chain has finite order and I take some maximal element $x_1$ (which must exists because our chains are finite) and then I take a maximal ...
0
votes
0answers
38 views

Does the set $[0,1] \times [0,1]$ have the least upper bound property under the dictionary order?

Let $A$ and $B$ be two non-empty ordered sets with the order relations $<_A$ and $<_B$, respectively. Then the dictionary order on the Cartesian product $A \times B$ is defined as follows: $a_1 ...
1
vote
1answer
57 views

Showing finite lattices are isomorphic to their sets of ideals.

I'm working out a problem from Gratzer '71. We are to show that any finite lattice $L$ $\simeq$ $I(L)$. My attempt was as follow: prove the contrapositive. So assume $L$ is not isomorphic to $I(L)$. ...
1
vote
1answer
65 views

First order theory - define a domain with an even number of elements

I'm trying to write a first-order theory that defines a domain of even size (containing an even number of elements). I'm told that I can use a single binary predicate symbol, R, that can be defined as ...
3
votes
2answers
116 views

First order thoery - define a finite domain

I'm trying to write a first-order theory that defines a domain containing a maximum of 2 elements. Up to this point, I've only been working with theories that use functions, constants, and relations, ...
1
vote
0answers
31 views

Group of Orientation-preserving Homeomorphisms of the Reals.

Let $h: \mathbb{R}\rightarrow\mathbb{R}$ ; $\mathbb{R}$ Reals be an orientation-preserving homeomorphism. I can see $h$ includes linear maps $h=ax+b$ with $a>0$ . Can we say that every ...
0
votes
1answer
45 views

How are the real numbers complete?

The completeness axiom for the real numbers states that any subset of the reals that is bounded above has a supremum. But if we take an example: Completeness of the real numbers - Least upper bound ...
3
votes
2answers
53 views

Exercise on posets and antichains in Steven Roman's Lattices and Ordered Sets

I have just began reading through Steven Roman's "Lattices and ordered sets", and I came across an exercise in Chapter 1 that I can't seem to find a good answer to. All the others are fairly easy, so ...
2
votes
0answers
44 views

The width of a power set graph and its orientations

Let $G(\mathcal{P}(n),E)$ be the undirected graph for the power set of $[n]$ elements under the inclusion relation (i.e. a poset). The width of this poset - which is defined as the size of the maximum ...
1
vote
0answers
14 views

Stochastic Orders

Does the partial order below (R) has a name? Has anyone seem something somewhat similar or related before? The book Stochastic Orders (my bible for this stuff) has no reference on it. Any references ...