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

0
votes
0answers
34 views

Orders, inf & sup of sequence

So I'm completely new to the idea of isomorphism and orders and I have to show, if the following sequence is bounded and find its inf / sup or show that it doesn't exist. $[{(0,1)^*\cup ...
0
votes
1answer
10 views
1
vote
1answer
16 views

How would i apply Dilworths Theorem to the following set: $S=\{ 0,1,4,6,7,8,9\}$ where any element $a$ is less than or equal to $b$?

This is the set $S=\{ 0,1,4,6,7,8,9\}$ under the order defined by divisibility. I know we have to find antichains and chains, and that the maximum number of partitions of $S$ into chains should equal ...
0
votes
1answer
14 views

Linear order where every initial segment is finite

It's true that a set with a linear order where every initial segment is finite is necessarily countable? I don't think so but I can't find a counterexample (or make a proof)
5
votes
0answers
48 views

Is there a linear order with this property

I was trying and failing to construct a linear order L each of whose uncountable subsets contains an uncountable well ordered subset but L is not a countable union of well ordered subsets. Is this ...
1
vote
0answers
30 views

Is there a name for those relations that behave a bit like $<$?

Consider a fixed but arbitrary preordered set $X$. Is there a name for those binary relations $R$ on $X$ satisfying the following? They seem to show up a lot. (Note that every such $R$ is necessarily ...
0
votes
2answers
52 views

An isomorphic map from natural numbers to positive rational numbers that preserves addition, multiplication and order

Since $\mathbb{Q}^{+}$ is countable, there is a bijection between $\mathbb{Q}^{+}$ and $\mathbb{N}$ (0 included). Then the question now is, can we go further by constructing an isomorphic map between ...
6
votes
2answers
67 views

Embedding $\omega_1$ in the hyperreals

I've been trying to show that there exists a subset of the hyperreals which has order type $\omega_1$, that is, that there exists a subset $A \subseteq {}^*\mathbb{R}$ for which there is an order ...
1
vote
1answer
20 views

Showing certaing Integral domain is not well ordered.

Let $\mathbb{Z}[\sqrt2]=\{ a+b\sqrt2 ~| a,b\in \mathbb{Z}\} $ be an integral domain. Let $p=\{ a+b\sqrt2 ~|a,b\in\mathbb{Z} ~~~ and ~~~ a+b\sqrt 2 ~~is~~a~positive~real~number \} $ Show that ...
3
votes
1answer
75 views

Why is this not a category?

Why need the composite of two monotone functions not be monotone? This is from Rings and Categories of Modules, Anderson., Fuller., page 7
1
vote
1answer
35 views

What are the orders of modulo 9 and modulo 28? [closed]

I know what is the order, but unfortunately I can't calculate it. Please help me if you can, thank you very much.
0
votes
0answers
5 views

Form Poset from (Non-zeta) Matrix

I have a matrix (well, really a table) of values that are the results of various indicator systems. Naturally, each system is slightly discordant, so no one true ranking exists. I'm looking to form ...
2
votes
1answer
40 views

Chain of elements of a chain of order ideals

Let $P$ be a partially ordered set, and let $I(P)$ be the set of order ideals (i.e. downward-closed sets) in $P$ ordered by inclusion. Suppose that $X$ is a chain of non-empty elements of $I(P)$. ...
0
votes
0answers
37 views

Dedekind(?) representation lemma on posets?

Here's an easy lemma: Any poset $(S, \preceq)$ is order-isomorphic to a subset of the powerset $\mathcal{P}(S)$ ordered by set-inclusion. I seem to recall having seen this attributed to Dedekind. ...
2
votes
1answer
36 views

Is there an orderpreserving bijection from $\mathbb R$ to $\mathbb R-\{0\}$?

Looking at $(\mathbb R,<)$ where $<$ denotes the usual order I understand that $\mathbb R-\{0\}$ will inherit an order (as every subset of $\mathbb R$). I could not find essential differences ...
1
vote
1answer
28 views

When can $\sup_x$ and $\sup_y$ be swapped?

$f$ is a mapping from $X \times Y$ to $Z$. $X$ and $Y$ are sets. $Z$ is a set with $\sup$ defined ( I am not very sure how to formulate that. Is $Z$ required to have some total order?), and can be ...
1
vote
1answer
27 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
30 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
34 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
36 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
7 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
19 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
15 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 ...
0
votes
0answers
17 views

Size of rankings in a round robin tournament

Let us have a round robin tournament in between $n$ teams. Let a ranking be a set of teams over which winning forms a total order. Prove that: a) There exists a set of $\log n$ teams which for a ...
2
votes
2answers
69 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
25 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
16 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
65 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
47 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
28 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
36 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
22 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
26 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
19 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
23 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
35 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
33 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
48 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
26 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
15 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
21 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
17 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 ...