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
0answers
28 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
10 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
0answers
12 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
12 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
13 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
14 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
18 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
94 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
18 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
34 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} ...
-1
votes
0answers
23 views

Number of chains having k subsets [closed]

In a partition of the subsets of {1,2, ... ,n} into symmetric chains, how many chains have k subsets in them?
2
votes
5answers
42 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
250 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 ...
4
votes
1answer
52 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
57 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 ...
5
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
14 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
18 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
25 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
34 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
51 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
56 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
101 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
29 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
43 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
36 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
38 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
11 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 ...
-8
votes
7answers
273 views

How is greater than defined for real numbers?

I have an understanding of real numbers. For example, I can imagine real numbers as points on the line. The point which is more to the right represents bigger number. Or if I have decimal ...
1
vote
1answer
14 views

Order-preserving function

I have an order on $\mathbb R ^ \mathbb R: f \le g $ iff $\forall x \in \mathbb R: f(x) \le g(x)$. Now I have a function $\mathbb R ^ \mathbb R \to \mathbb R ^ \mathbb R: F (f)(x)= f(x^2)+1$. I have ...
0
votes
0answers
17 views

Nomenclature for posets s.t. for all $x<y$, there exists $z$ with $x<z<y$.

I can't remember the nomenclature (if it exists) for a poset with the property in the title, that is, a poset $(P,\leq)$ with the following property: If $x<y$ in $P$, then there exists $z\in P$ ...
0
votes
0answers
19 views

The size of largest antichain to the total number of incomparable elements

Given a poset $>$ over a set $A$, every two elements $x,y\in A$ stands in exactly one of three cases: either $x>y$ or $y>x$ or $x\bowtie y$. The last case says $x$ and $y$ are incomparable. ...
0
votes
0answers
35 views

cardinality of maximum antichains in power set posets

Let $\mathcal{P}(S)$ be the power set of a non empty set $S$. Consider the poset $\succ$ for the inclusion relation over the elements of $\mathcal{P}(S)$ (which is equivalently represented by a single ...
0
votes
0answers
11 views

Term of partially ordered set with “levels”

Suppose that we have a partially ordered set $(X,\leq)$ such that the following condition holds: There exists a disjoint partition $X = \bigcup_{ i \in \mathbb N_0 } X_i$ such that for $i < j$ we ...
0
votes
0answers
15 views

Monotone actions of the infinite cyclic group

For reasons which are too long to explain, I grew interest in the theory of monotone actions of partially ordered groups, by which I mean monotone functions $G\times P\to P$ satisfying the axioms of ...
0
votes
1answer
42 views

How ae these three order types on $Z_+ \times Z_+$ different?

Let $Z_+$ denote the set of positive integers. Consider the following relations on $Z_+ \times Z_+$: The dictionary order; that is, $(x_0,y_0) < (x_1,y_1)$ if either $x_0 < x_1$, or $x_0 = ...
0
votes
1answer
13 views

Example of a poset with elements not included in a maximal element?

I am reading Gratzer's General Lattice Theory and one of the exercises is to give an example of a poset with maximal elements in which not every element is included in a maximal element. I am ...
0
votes
0answers
17 views

Order Type Stratification

Is there some sort of interesting way of organizing certain order types that aren't ordinals? When I say certain order types, some examples include but are not limited to: order types of dense ...
3
votes
1answer
44 views

Uncountable Dense Linear Orders

Is there an example of two uncountable equipollent dense linear orders without endpoints that don't satisfy the same first order properties? Or is it true that two uncountable equipollent dense linear ...
2
votes
1answer
33 views

Order preserving functions that do not preserve binary operations

According to Tarski's Fixpoint Theorem for lattices, if I have a complete lattice, $L$, and an order-preserving function, $f:L \to L$, then the set of all fixpoints of $L$ is also a complete lattice. ...
0
votes
0answers
14 views

Well ordering+finite number of steps between elements property name?

So, I just did a counterexample in topology that relied upon a well ordering in which you there were a pair of elements that you could not connect between in a finite number of steps. (The standard ...
0
votes
1answer
35 views

Prove if 0(a) is odd, show a is a square.

Let $G$ be a group and a is an element of $G$. If $o(a)$ is odd, show $a$ is a square. I started by supposing that $o(a) = 2n+1$ which implies $a^{2n+1}=1$. I am not sure if I am on the right track ...
0
votes
1answer
47 views

An interesting puzzle for some, confusing for me

Suppose that $a$ is of odd order $k$ and $bab=a$. I need to show that $b$, must be of order $2$. We can prove this anyway we want to, but our hint is to expand $(bab)^k$ and re-associate and then ...
6
votes
1answer
115 views

The “Largeness” of Subsets of the Natural Numbers

Recently, I was thinking about the Erdős conjecture on arithmetic progressions, which says that, if, for a set $A\subseteq\mathbb{N}$, the sum $\sum_{a\in A}\frac{1}a$ diverges (i.e. "A is large"), ...
1
vote
1answer
20 views

Non-continuous Poset without Interpolation property.

There is a theorem that said if $X$ is a continuous poset, then if $x \ll y$, there exists $z\in X$ such that $x\ll z\ll y$, where $\ll$ is the way below relation. I am not sure why the continuity ...
1
vote
0answers
30 views

Total ordering on the free group

The free groups can be totally (bi-)ordered. This paper shows how to do it (page 4). In short, you embed the group in multiplicative structure of the ring of power series in non-commuting variables, ...
0
votes
1answer
27 views

For real number, Is it true that $sup\{x_i + y_i: i\in I\}=sup\{x_i:i\in I\}+sup\{x_i:i\in I\}$?

If $I$ is an indexing set for real numbers so $x_i \text{and} y_i$ are reals. Is it true that $sup\{x_i + y_i: i\in I\}=sup\{x_i:i\in I\}+sup\{x_i:i\in I\}$? I thought I need this statement to prove ...