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
1answer
22 views

Width of Join Semilattice in $\mathbb R^n$

Suppose $S$ is a join semilattice that can be generated by $m$ generators. I would like to know an asymptotic upper bound on the width of $S$ (the maximum cardinality of all antichains in $S$) under ...
0
votes
1answer
34 views

to prove that Inf$(B) \sqsubseteq $ Inf$(A)$.

In a poset $(P, \sqsubseteq)$, and $A \subseteq B \subseteq P$. Also Infimum$(A)$ and Infimum$(B)$ exists. I need to prove that Inf$(B) \sqsubseteq $ Inf$(A)$. My Attempt. Considered $x \in A$, it ...
-1
votes
2answers
44 views

If a finite nonempty set of real numbers has a maximum then it has a minimum, prove.

so as the title says. I first proved that all finite nonempty sets of real numbers have maximum, but I cannot see how from this I can prove that it also has a minimum. Any advice would be ...
0
votes
1answer
42 views

Prove every finite set of real numbers is well ordered.

so as the title says how do we prove it? I mean it is obvious but i have no idea how to do it. Without referring to general principle of mathematical induction, as that would be circular logic i ...
2
votes
1answer
27 views

Width of poset of posets

Let $P$ be the set of all labelled posets on $[n]$ ordered naturally by edge extension. What is the cardinality of the largest antichain in $P$?
2
votes
3answers
35 views

$M=\lbrace \frac{(-1)^n}{n}:n \in \mathbb N \rbrace$ not orderly countable

A non-empty set $M$ is called orderly countable if there is an surjective, strictly increasing $f: \mathbb N \to M$. Proof: $M=\left\{ \frac{(-1)^n}{n}:n \in \mathbb N \right\}$ is not orderly ...
1
vote
2answers
28 views

Partial Orders: “Minimum property” iff “Maximum property”?

Given a partially ordered set $(X,\leq)$, is it true that $$ \forall P\subseteq X:P\neq\emptyset\text{ and }P\text{ is bounded below }\to P\text{ has a minimum}\\ \updownarrow\\ \forall ...
0
votes
1answer
21 views

Show that $\mathbb N $ with the usual order is well ordered.

Show that $\mathbb N $ with the usual order is well ordered. My attempt Let $A\neq\emptyset$ a subset of $\mathbb N$. Since $A\subset \mathbb R$ is under-bounded by $0$, there is an infimum. Let ...
0
votes
0answers
14 views

Function on power set: Negativity implication leads to monotonicity

so I have a binary function $f: P \times P \to \mathbb{R}$ over some power set $P$. I also have a partial ordering $(P,≤)$ over $P$ (by set size). For this function I know that $f(a,b) ≥ 0 \implies ...
0
votes
0answers
6 views

Indecomposable representations of poset (1,1,m), m>=1

The problem says : Find indecomposable representations of poset (1,1,m) where m $\geq 1$. I've tried to find the the associated matrix problem for this poset but got nowhere. Any help would be ...
2
votes
2answers
26 views

Monotonic function which is not an order-embedding

I wrote down this definition during the lesson: Let $\langle P, \leq_P\rangle$ and $\langle Q, \leq_Q\rangle$ be two posets. A function $f: P \rightarrow Q$ is monotonic, if $x \leq_P y \implies ...
1
vote
1answer
39 views

A formula for a monotone bijection between two intervals in $\mathbb Q$

While I was writing this answer, this answer, the following question occurred to me. A special case of a well known result of Cantor is that if $\alpha,\beta\in\mathbb R \setminus\mathbb Q$ then ...
0
votes
0answers
7 views

Form of binary function that is monotone in first and antitone in second argument

if I have a partially ordered set $P$, and I have a function $f: P \times P \to \mathbb{R}$ that is monotone over the first and antitone over the second argument, i.e. for any $a,b,c \in P$ $a ≤ b ...
1
vote
2answers
53 views

A set with a maximal element but not supremum?

I have a problem which is asking me to show by example that a set (with respect some partial ordering) may have a maximal element but still no supremum. I've been sitting here for hours trying to ...
0
votes
2answers
28 views

Lexicographic order is a partial order on the the set of all partitions of the positive integer n.

I think the above statement is false, if not then please give a hint to prove.I know majorization is a partially order.
0
votes
1answer
30 views

How to find a linear extension of a poset

Give linear extensions of the three posets in the image. This is the image of the posets: I am unsure how to began doing linear extensions on this so if someone could please explain linear ...
0
votes
0answers
158 views

Can we express every partial order with these two combinators?

Consider the following two combinators: $\alpha<\beta$ meaning “all objects mentioned in $\alpha$ are smaller than the objects mentioned in $\beta$” $\alpha\mid\beta$ meaning “all objects ...
-1
votes
1answer
23 views

X is totally ordered under ≤ if and only if X follows the law of trichotomy?

I'm having trouble with this proof. I know that this proof requires two parts. My attempt so far: Proof: ($\Rightarrow$) Assume $X$ is a totally ordered set under $\le$. Let $m,n$ be two ...
0
votes
1answer
27 views

Can a Proper Partial Order have a Totally-Ordered 'Spine'?

Suppose $P$ is an arbitrary poset. Define a subset $Q \subset P$ to be dense to mean that for every $a,b \in P$ with $ a < b$ there is some $q \in Q$ such that $a \le q \le b$. This may not be ...
1
vote
0answers
30 views

Motivation for looking at the coalgebra structure of incidence algebra resp. group algebra

In basic combinatorics course we learn about the incidence algebra of a poset. Now i've read that one could start by defining the co-incidence algebra and then it is a fact that the dual vector space ...
1
vote
1answer
20 views

Why is the set R = $\{(x,y) \in \mathbb{R} \times \mathbb{R} | |x| < |y| \bigvee x=y) \}$ a partial order?

For a set to be a total order it must have 4 properties: Reflexive Antisymmetry Transitive $\forall x \in A\forall y \in A((x,y) \in R \bigvee (y,x) \in R)$, where A is a set and R is a relation ...
0
votes
1answer
21 views

Prob. 12, Sec. 3 in Munkres' TOPOLOGY, 2nd ed: How to relate these order relations?

Let $\mathbb{Z}_+$ denote the set of positive integers. Consider the following order relations on $\mathbb{Z}_+ \times \mathbb{Z}_+$: (i) The dictionary order: $x_0 \times y_0 \prec x_1 \times y_1$ ...
3
votes
1answer
42 views

What part of digraphs are posets?

Let $D_n$ denote the collection of all directed graphs on vertex set $[n]=\{1,\ldots, n\}$. Let $P_n$ denote the subcollection of all digraphs in $D_n$, which have the structure of a partial order. ...
0
votes
1answer
28 views

on the lexicographic order on $\mathbb{C}$

I know that the lexicographic order on $\mathbb{C}$ turns it into an ordered set. I just wonder if under this ordering, $\mathbb{C}$ has the least upper bound property
1
vote
2answers
51 views

Simple question about posets.

Suppose that $X$ is a set, and $\geq$ is an ordering on that set. To determine if $(X, \geq)$ is a poset, we must reflexivity, transitivity, and anti-symmetry. My question is concerned with this ...
1
vote
1answer
51 views

For every partial order ≤ is the relation < transitive?

For every general partial order ≤ is the relation < := ≤ ∩ ≠ transitive I tried working with the definition of the partial order. A partial order is antisymmetric, transitive and reflexive. The ...
0
votes
1answer
93 views

About left-orderable group and convex subgroup

Let $G= \def\<#1>{\left<#1\right>}\<a,b,c,d \mid \text{finite number of defining relations}>$ be a left-orderable group. Let $H=\<a,b \mid \text{a partial subset of defining ...
1
vote
1answer
40 views

Partial order involving cartesian product: P x Q

So I'm a bit confused with the concept of a partial order. P = {1, 4} Q = {1, 2} How do you define a partial order Z on (P x Q)? and how would the hasse diagram of Z look like? is it even possible ...
1
vote
2answers
36 views

If $f:[0,1] \longrightarrow \mathbb{R}$ is $C^{\infty}$, can we say that it is positive or negative?

The title of the question is not so clear: I am sorry about this. While studying totally ordered groups, I found that a direct sum of totally ordered groups can be ordered by means of lexicographic ...
1
vote
1answer
19 views

Best $g$ Approximation Poset maps

Let $P, Q$ be posets, $g: P\rightarrow Q$ be a monotone map. Let $x\in Q$. By a $g$-approximation of $x$ we mean an element $y\in P$ with $x\leq g(y)$. A best $g$-approximation of $x$ is a ...
1
vote
0answers
27 views

What is the standard term for the property of an order-embedding $h \colon P \to P$ such that for all $a \in P$, $a \leq h(a)$?

In an essay, I want to talk about order-embeddings $h \colon P \to P$ on a partially ordered set P such that for all $a \in P$, $a \leq h(a)$. Does somebody know the standard term for a function ...
1
vote
1answer
25 views

Ordering on ultrapower of $\mathbb{Q} $

Prove that the ordering on the real number is not isomorphic to an ultrapower of the ordering of the rationals. Hint: an ultrapower of $\mathbb{Q} $ is not complete. I cannot understand the hint; I ...
1
vote
1answer
24 views

Reference for compact ordered spaces

A compact ordered topological spaces is a compact topological space $(X, \tau)$ together with a partial ordered $\leq$ on $X$ such that $\leq \subseteq X^2$ is a closed subset in the product topology. ...
0
votes
1answer
38 views

Totally ordered set. Defining a subset and a Least upper bound

Ok, so I have 2 problems i've been working on and I want to see if I'm anywhere close to getting it right. Pretty new to the whole abstract math scene. The problems are defined as: X,≤ is a totally ...
0
votes
0answers
26 views

Does every function $P \rightarrow Q$ arise from some function $P \times P^\mathrm{op} \rightarrow Q$?

Let $P$ and $Q$ denote posets, and $f : P \rightarrow Q$ denote an arbitrary function. Question. Does there necessarily exist a monotone function $g : P \times P^{\mathrm{op}} \rightarrow Q$ such ...
0
votes
0answers
19 views

Compare two fixed points component-wisely

Tarski fixed point theorem conclude that a isotone from a complete lattice to itself have a largest fixed point. Now suppose I have two isotone on defined on the same lattice, and one isotone is ...
3
votes
0answers
149 views

A construction on boolean lattices is itself a boolean lattice?

Let $\mathfrak{A}$ and $\mathfrak{B}$ be (fixed) boolean lattices (with lattice operations denoted $\sqcup$ and $\sqcap$, bottom element $\bot$ and top element $\top$). I call a boolean funcoid a ...
1
vote
1answer
49 views

how to prove that abc and cba do not necessarily have the same order?

Let a, b and c be elements of a group G, how can I prove that abc and cba do not necessarily have the same order?
0
votes
1answer
17 views

Does there exist a boolean lattice without atoms?

There are atomic boolean lattices and this is the same as atomistic boolean lattices. Does there exist a boolean lattice without atoms? (except of the degenerative case of one-element lattice) Or at ...
1
vote
0answers
29 views

Any connection at all between the Gamma Function and the theory/enumeration of ordered sets and lattices?

Is there any connection at all between the Gamma Function and the theory/enumeration of ordered sets and lattices? I mean, the factorial function, amongst other things, counts the number of linear ...
2
votes
1answer
48 views

How to use well-ordering to form a “least counterexample derived contradiction” to prove rule for obtaining the remainder when dividing $3^n$ by 13?

By the division with remainder theorem, we know that there exists $q \in \mathbb{Z}$ and $r \in \mathbb{Z}$, where $0 \leq r < 13$, such that: \begin{equation*} ...
0
votes
1answer
21 views

every set of non compact elements has a maximum element

Let $P$ be a poset. An element $x$ of $P$ is compact if for every directed set $D\subseteq D$, $x\leq \sup P$ implies $x\in {\downarrow\!\! D}$. Is it true if the set of compact elements of $P$, ...
4
votes
1answer
35 views

Rationals $(\mathbb{Q},<)$ are isomorphic to a part of a finite partition

I believe the following statement is true but I can't find or figure out a proof: For any partition of the set $\mathbb{Q}$ of rationals into a finite number of parts, there is a part containing an ...
2
votes
1answer
30 views

Equivalence of two order-theoretic notions without Choice?

A question occurred to me as I was considering an earlier question of mine, and wasn't closely enough related for me to feel I could to include it. Let's say that a partial order $\langle ...
2
votes
0answers
51 views

Are the following conditions necessary and sufficient for the desired partial order isomorphism?

Before I get to my questions, let me clarify some terminology and notation that I will be using. $\DeclareMathOperator{\pr}{pr}$ $\DeclareMathOperator{\ext}{ext}$ $\DeclareMathOperator{\rank}{rank}$ ...
4
votes
6answers
895 views

why is there no order in metric spaces?

Why is there no abstract notion of order in the metric spaces? Surely, if there is a notion of distance there must be a notion of different values. If there is a notion of different values, why ...
1
vote
2answers
43 views

Is it possible to construct an order on $\Bbb R^2$ that turns it into a set with the least-upper-bound property?

What I already know: Any ordered field that has the l.u.b.p. is isomorphic to $\Bbb R$. However thing is a bit different in my question, I only request such an order that turns $\Bbb R^2$ into ...
0
votes
2answers
36 views

How to prove that $f(x) = (x-1)/ (x+1)$ and $g(x) = x$ are ordinally equivalent on domain $[0, ∞)$?

I can see that for all $x$ and $y$, $f(x)≥f(y)$ iff $g(x)≥g(y)$. But what would the formal proof look like? Would it be by induction?
2
votes
1answer
44 views

How can $-y\geq 0$ imply $y\leq 0$ in an ordered vector space?

The following is an excerpt from a Wikipedia article about ordered vector space: Given an ordered vector space $(V,\geq)$, the subset $V^+$ of all elements $x$ in $V$ satisfying $x≥0$ is a convex ...
3
votes
4answers
69 views

Are there $\in$-antichains of all cardinalities?

Say that a set $X$ is a $\in$-antichain iff $x\not\in y$ for any $x,y\in X$. Are there $\in$-antichains of cardinality $\mathfrak c$ ? More generally, for any ordinal $\alpha$, is there a ...