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
vote
1answer
32 views

A question about cofinal and coinitial order-preserving injections between linearly ordered sets

There is an inclusion $f : \mathbb{Z} \hookrightarrow \mathbb{R}$. Furthermore, if $A \subseteq \mathbb{R}$ has a maximum element, then so too does $f^{-1}(A)$. There is also an inclusion $g : ...
2
votes
1answer
35 views

Lower Bound for subsets of $\mathbb{N}$ [duplicate]

Let $P = \{A \in \mathbb{N} : A \neq \emptyset, |A|<\infty, |A| = 2k, k\in \mathbb{Z}^{+}\}$. Consider $X = \{ A \in P: 1 \in P \}$. Does $X$ have a lower bound in $(P,\subseteq)$. We can see that ...
0
votes
1answer
40 views

Does X have a lower bound?

Let P={A $\subseteq$ $\mathbb N$: A is non-empty, finite and has an even number of elements}. Consider X={A $\in$ P : 1 $\in$ A}. Does X have a lower bound in (P,$\subseteq$)? I think that there is a ...
2
votes
1answer
45 views

For any $a\in S_\Omega$, either it has an immediate predecessor or there is an increasing sequence in $S_\Omega$ whose l.u.b. is $a$. [duplicate]

Specifically I would like to show: Let $S_\Omega$ be the minimal uncountable well-ordered set. For any $a\in S_\Omega$, either $a$ has an immediate predecessor in $S_\Omega$, or there exists an ...
0
votes
1answer
17 views

does isomorphic Hasse diagrams represent two different posets or same poset?

I want to have a clear picture of isomorphic hasse diagrams, what do they represent, same poset or two different posets?
1
vote
0answers
29 views

Why is every monomial order a well-ordering?

Let $R$ be a commutative, unital ring. According to wikipedia, a monomial order is a total order $\leq$ on the space of monomials of a given polynomial ring of $R$ such that If $u\leq v$ and $w$ is ...
0
votes
1answer
19 views

Prove that, for all ordered sets P, Q and R,

$\langle P \rightarrow \langle Q \rightarrow R\rangle \rangle \cong \langle P \times Q \rightarrow R\rangle $ where $\langle Q \rightarrow R\rangle $ is the set of all order-preserving maps from Q ...
2
votes
2answers
77 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
28 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
45 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 ...
2
votes
2answers
72 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
69 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
57 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
45 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
43 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
34 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
47 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
35 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
29 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
30 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
26 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
88 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
40 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
45 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
37 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
21 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
51 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
114 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
31 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
1answer
30 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 ...
1
vote
1answer
27 views

Show that if a subset of an ordered field has a least upper bound, then any two least upper bounds for it have to coincide

Show that if a subset of an ordered field has a least upper bound, then any two least upper bounds for it have to coincide Should I prove by contradiction then turn my proof into a direct proof using ...
3
votes
2answers
154 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
29 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 ...
3
votes
2answers
56 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
82 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 ...
3
votes
1answer
327 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
41 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
110 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
79 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
31 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
48 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
18 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
66 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
38 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
38 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 ...
1
vote
1answer
70 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
78 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
151 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
39 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
50 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 ...