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

5
votes
3answers
225 views

How to find a real number which comes just after a particular real number?

This is like when we say that the integer which comes just after $2$ is $3$. I want to know such a way so that I could find the real number which comes just after a particular real number in the usual ...
5
votes
0answers
40 views

What is known about this well-ordering of the rationals in a finite interval?

Given any interval $I=(a,b) \subset \mathbb R^+$, we may order the rationals in $I$ with a denominator-first lexicographic order, as follows: First, we list, in increasing order of numerator, all $q ...
2
votes
2answers
51 views

minimal embeddings of topological spaces into connected spaces

Defintions: Let $X$ be a topological space. 1) A connected space $Y$ is a minimal connected ambient (m.c.a for short) space for $X$ if there exists an embedding $i:X\mapsto Y$, and for every ...
2
votes
2answers
34 views

A Chain of Subsets of $\mathbb{R}$ Without any Good Countable Subchain

Consider which $\bigl{(} A_i \bigr{)}_{i\in I}$ is a chain of subsets of $\mathbb{R}$. We say that a countable chain like $\bigl{(} B_n \bigr{)}_{n\in \mathbb{N}}$ is good if : for every $n\in ...
0
votes
1answer
24 views

Are these partial order or total orders?

I just want to know if the following are considered partially ordered sets or total set. Here is the definition: $\mathbb{R}^2$ : (a,b) R (c,d) iff $a\leqslant c$ and $b\leqslant d$ $\mathbb{R}^2$ ...
3
votes
1answer
64 views

Relationship between $S$ and $S^{-1}$

This is one of the problem I have been solving in Velleman's How to Prove book: Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that if $R$ is symmetric, ...
0
votes
0answers
38 views

Lexicographic order, $\mathbb{Z^+ \times Z^+}$ $\space \color{red}{ VS} \space $ $\mathbb{Z}$

Why $\mathbb{Z}^+\times \mathbb{Z}^+$ with $(a1,a2) \preceq (b1,b2)$ if $a_1 < b_1$ or if $a_1 = b_1$ and $a_2 \leq b_2$ is a well-order set but $\mathbb{Z}$ set is not a well-ordered one? I read ...
0
votes
0answers
25 views

Does total order imply linearisation

Suppose $X$ is a totally ordered set. Does this mean that $X$ can always be linearised? I mean can $X$ be always written in a linear order like $\mathbb{R}$ ? I came across this question when I was ...
2
votes
1answer
65 views

Characterizing affine subspaces order-theoretically

Let $V$ denote a real vectorspace and $\mathrm{Con}(V)$ denote the poset of convex subsets of $V$. The goal is to identify those elements of $\mathrm{Con}(V)$ that happen to be affine subspaces of $V$ ...
2
votes
1answer
44 views

What do we call well-founded posets whose elements have a unique height?

What do we call those well-founded posets $P$ with the property that for every $x \in P$, all maximal chains in the lowerset generated by $x$ have the same length? Examples: The set of all finite ...
1
vote
1answer
43 views

Zorn's lemma converse? (Context: Maximal proper subgroups)

So, in my qual prep class a pretty simple question popped up: "Prove that for any nontrivial finite group there exists a maximal proper subgroup." So of course, my natural inclination was to ...
2
votes
3answers
25 views

Order by inclusion

Given the set $E = \{a,b,c\}$, order the power set of $E$ (all subsets) by inclusion. I think the order would be $\varnothing$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a,b\}$, $\{a,c\}$, $\{b,c\}$, ...
2
votes
1answer
52 views

$|\alpha\times\alpha|=|\alpha|$ for infinite ordinal $\alpha$, definably

I am trying to prove Proposition 1.7 of http://math.bu.edu/people/aki/7.pdf: Proposition 1.7 (Halbeisen–Shelah). If $\aleph_0\le|X|$, then $|{\cal P}(X)|\not\le|{\rm Seq}(X)|$. In words, ...
0
votes
2answers
18 views

Using substitution to make an equation into a separable differentiable equation

I have the question: By making the substitution $y = t^nz$ and making a cunning choice of n, show that the following equations can be reduced to separable equations and solve them. $$\dfrac{dy}{dt} = ...
2
votes
1answer
40 views

Proving that every submodel of DLOE is an elementary submodel

Let $A$ and $B$ be models of the theory of Dense Linear Orders without Endpoints such that $|B| \subset |A|$. I'm trying to prove that $B$ is an elementary submodel of $A$. Using Tarski-Vaught test I ...
2
votes
1answer
27 views

Does multiplication by the inverse of a Cholesky matrix preserve order?

Let $n \in \{1, 2, \dots\}$ and let $C \in \mathbb{R}_{n, n}$ be a real, symmetric and positive definite $n \times n$ matrix. Define $B \in \mathbb{R}_{n, n}$ to be the real, lower triangular matrix ...
0
votes
0answers
6 views

proving properties of (graph) dominance defined via a system of equations

Some notions on graphs can be defined via a system of equations with values in a lattice. For example, dominance $d(v_1, v_0)$ ($v_1$ dominates $v_0$) in a graph $g$ is defined by a system $\forall ...
3
votes
0answers
23 views

About elements of a poset

Consider a poset $\mathfrak{A}$. I denote $a\not\asymp b$ iff there is a non-least element $x\in\mathfrak{A}$ such that $x\le a$ and $x\le b$. I denote $\star a = \{ x\in\mathfrak{A} \mid x\not\asymp ...
0
votes
0answers
36 views

Prove that if a function f is continuous then it is monotonic

Let ($L_1 , \le_1 $) and ($L_2 , \le_2 $) be two posets. A function $f : L_1 \to L_2 $ is continuous if $ \forall E_1 \subseteq L_1, E_1 \neq \emptyset, f(LUB(E_1)) = LUB(f(E_1)) $ Prove that if $f$ ...
1
vote
0answers
56 views

Is this ordered square mathematically interesting?

Build a $5\times5$ (say) square using $\frac{1-\left(\frac{3}{2}\right)^n}{(2 m-1) 2^n-1}+1$, $$ \left( \begin{array}{ccccc} 0.5\hfill & 0.9\hfill & 0.944444 & 0.961538 & 0.970588 \\ ...
2
votes
0answers
32 views

Is possible write $\gamma \in [2, 0)$ under certain condition?

I am writing an academic paper. I have a variable that vary its value from $2$, when speed is zero, until $0$ at high speed. So, I would like write that $\gamma \in [2, 0)$ and not $\gamma \in (0, ...
0
votes
1answer
25 views

Proving $S_1 \subseteq S_2$ for transitive closure

This is one of the problem I have been working from Velleman's How to prove book: Suppose $R_1$ and $R_2$ are relations on $A$ and $R_1 \subset R_2$l (a) Let $S_1$ and $S_2$ be the reflexive ...
0
votes
2answers
24 views

simple clarification of equivalence relation and order relation notation meaning

So by definition an equivalence relation is a binary relation on a subset of the cartesian product of our set A, i.e $A\times A$ satisfying the 3 conditions. But I'm a little confused about ...
0
votes
0answers
8 views

On the matter of order completion (Dedekind completion)

So I was introduced recently to this idea of "order completion" of partially ordered set. A more special case is when this poset is in fact a completely ordered set, such as rationals. Completing the ...
1
vote
1answer
34 views

The least relation which produces a partial order

Fix some set $U$. Let $E$ be a binary relation on $U$. By definition $S(E)=\operatorname{id}_U \cup E \cup E^2 \cup E^3 \cup\dots$. I define $\mu(E) = \bigcap \{X\in\mathscr{P}(U\times U) \mid ...
0
votes
1answer
48 views

group of functions $\Bbb N \to \Bbb N$

$F$ is the group of all functions fron $\Bbb N$ to $\Bbb N$, $S$ is a relation on $F$: for $f,g\in F: (f,g)∈K \iff$ for all $n\in\Bbb N, f(n)≤g(n)$. So what is $g$ or $f$ ? Are they the outputs of ...
0
votes
2answers
15 views

Prove $a \leq b$, $\mbox{GLB}(\{a,b\}) = a$ , $\mbox{LUB}(\{a, b\}) = b$ are equivalent

It seems really obvious to be as a set containing $a$ and $b$ have GLB as $a$ and LUB as $b$. But how can it be proved mathematically?
2
votes
1answer
46 views

Prove divisibility is a partial order relation over natural numbers

I have proceeded like this so far: (this natural number set includes $0$) Reflexivity: Proof: $a = k \cdot a,$ since $k$ also belongs to natural number, it is proved. Anti-symmetry: $a \mid b$ ...
0
votes
2answers
30 views

How can division on Natural numbers be a poset?

For natural numbers including 0, how can it be a poset while zero cannot divide zero. Doesn't this mean it isn't reflexive?
1
vote
2answers
34 views

Is Least Upper Bound of Empty Set equal to Greatest Lower Bound of a another Set?

We had this discussion today that $\operatorname{LUB}(\varnothing) = \operatorname{GLB}(L)$ in a complete lattice $(L,\leq)$. I'm not still not getting it why that is the case.
0
votes
2answers
15 views

partial DAG and number of linear orders

Let $>$ be a linear order relation over a set $A$. Consider the graph $G$ that represent the transitive closure of $>$. Obviously $G$ is directed and acyclic. Given a set of edges ...
1
vote
1answer
24 views

Proving that $B_1$ and $B_2$ doesn't have maximal element

This is one of the problem I have been solving form Velleman's How to prove book: Suppose $R$ is a partial order on $A$, $B_1 \subseteq A$, $B_2 \subseteq A$, $\forall x \in B_1 \exists y \in B_2 ...
0
votes
0answers
16 views

number of permutations that have $i<j$ against the ones with $j>i$

Consider a set $A=[a_1,a_2,\dots,a_n]$ and its all possible permutations $P$. Select one permutation $\sigma=(\sigma(a_1),\sigma(a_2),\dots,\sigma(a_n)\ )\in P$ and consider a set of distinct pairs ...
1
vote
1answer
17 views

Mimimum and Minimal element of an ordered set

During study of ordered sets,I gone through 'minimal element' and 'minimum element' of a set. Can someone explain the difference between them with examples? Many thanks and regards,
-1
votes
1answer
14 views

from linear extension to partial order

Going from partial order to a linear one is easy, we just do topological ordering. I am wondering about the other way around. In particular: let $>$ be a linear order over a set $A$. Let $\Gamma$ ...
7
votes
5answers
906 views

Isn't every totally ordered set well-ordered?

A well order is a total order on a set $S$ with the property that every non-empty subset of $S$ has a least element. But surely it follows from the definition of a total order that any non-empty ...
1
vote
0answers
67 views

Three theorems for the price of one? (like duality)

Why the notion of "duality" (when we get two theorems for the price of one) are ubiquitous in mathematics (order and lattice theory, category theory, group theory), but "triality" (three theorems for ...
2
votes
1answer
32 views

Order relations and counting the number of cases (Fubini numbers)

I have $n=2$ numbers $a$ and $b$, $a\in\Bbb{N}$ and $b\in\Bbb{N}$. Then I have the function $f$ defined as: $ f(x,y) = \begin{cases} -1, & \text{if $x<y$} \\ 0, & \text{if $x=y$} \\ +1, ...
0
votes
1answer
29 views

Why is the degree condition for a degree reverse lexicographic order necessary?

A degree reverse lexicographic order $\prec$ is defined as follows: Given the polynomial ring $R=K[x_1,...,x_n]$. Two monomials in $R$ have the order $x^u\prec x^v$, if $\deg(x^u)<\deg(x^v)$, or ...
0
votes
2answers
33 views

Partial ordering of functions

Let $X$ be the set of all real-valued functions $x$ on the interval $[0,1]$ and let $x \leq y$ mean that $x(t) \leq y(t)$ for all $t \in [0,1]$. Does it define a partial ordering/ total ordering? Does ...
0
votes
1answer
16 views

Is a lexicographic order over a partial-order and a total-order a total ordering?

Is the following statement true? If so, can someone advise on how to prove it? Let A = $(S_1,\prec_1)$ be a partially-ordered set and let B = $(S_1,\prec_2)$ be a totally-ordered set Let ...
2
votes
2answers
19 views

Prove there exists a strictly increasing function from the natural numbers to a partially strictly ordered set

Let $P$ be a non-empty partially strictly ordered set and assume no element of $P$ is maximal (i.e. for every $x \in P$ there exists $y\in P$ with $x < y$). Show there exists a function ...
1
vote
1answer
37 views

Partial order relations and posets

Suppose you are given to prove this question: Let $P=\{2,3,4,\ldots,10\}$. Define $\le$ by $a\le b$ if and only if $a\mid b$, i.e, $a$ divides $b$. Prove that it is a partial order on $P$. I think ...
1
vote
1answer
28 views

$p$-adics with the least upper-bound property

It is well-known (I believe?) that the $p$-adics do not admit an ordering in the 'usual sense', the "usual sense" being a total order that is compatible with the field operations. I do not want to ...
2
votes
1answer
107 views

A chain with more than two elements

A chain with two elements $0$ & $1$ is complemented as complement of $0$ is $1$ and that of $1$ is $0$.How to show that every chain with more than two elements is not complemented?
1
vote
2answers
15 views

Order types of subsets of the reals

Is there a subset of $\mathbb{R}$ that has the order type $\omega + (\omega^*+\omega)\cdot\eta + \omega^*$ (i.e., an $\omega$-sequence, followed by a bunch of copies of $\mathbb{Z}$ ordered like ...
0
votes
2answers
38 views

Help Showing a Relation is/isn't a Partial Order

Define the relation $\le$, as $(a,b)\le(c,d)$ if and only if $a+b\le c+d$ and $a\le c$. Is this a partial order? I know it's definitely not if we remove the $a\le c$ (because then it's not ...
0
votes
0answers
34 views

Partial Ordering and Hasse Diagram.

Draw the Hasse diagram for the partial ordering “x is a factor of y” on the following sets: S = {2, 3, 5, 7, 21, 42, 105, 210} I don't know how to find the partial ordering of this set. I know that ...
5
votes
1answer
95 views

Restriction of a monotone self-map (“endomorphism of $\mathbf{Pos}$”) to a wide subposet

Here's a poset, call it $P.$ $\hspace{1cm}$ Define a function $S : P \rightarrow P$ as follows. $$S(0) = 1, \qquad S(1) = 2, \qquad S(2) = 2$$ Clearly, $S$ is monotone. Now consider the following ...
0
votes
1answer
39 views

How to prove this theorem? (Logical symbols help)

This is a theorem from a book. I'm having a hard time on proving it. Suppose A is a set,$\mathcal{F}\subseteq \mathscr{P}(A)$, and $\mathcal{F} \neq \emptyset$. Then the least upper bound of ...