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

6
votes
1answer
115 views

Is Wikipedia wrong about the least-upper-bound property?

Wikipedia states that the least-upper-bound property “ is a fundamental property of the real numbers and certain other ordered sets. A set $X$ has the least-upper-bound property if and only if every ...
1
vote
1answer
133 views

Let G be an abelian group, and let a∈G. For n≥1,let G[n;a] := {x∈G:x^n =a}. Show that G[n; a] is either empty or equal to αG[n] := {αg : g ∈ G[n]}… [closed]

We were given questions to study for our exam coming up. We have not covered much of this topic, so any help would be greatly appreciated! Let $G$ be an abelian group, and let $a\in G$. For $n≥1$, ...
1
vote
0answers
25 views

Smallest Rational Number Proof [duplicate]

Can anybody help me out with solving this mathematical proof? Prove the statement “There is no smallest rational number greater than 2” by contradiction. Contradiction: There is a smallest ...
-1
votes
1answer
235 views

There is no smallest rational number greater than 2

I have a problem that I am seriously stuck on. I'm not sure what to do I've seen similar proofs online with the least positive rational number but this is apparently different and I'm not sure why. ...
1
vote
0answers
26 views

Proving the principal of inclusion-exclusion using Möbius inversion

In Enumerative Combinatorics v. I, Stanley applies Möbius inversion to $B_n$, the poset of subsets of $[n]$, to show that $\forall f,g : B_n \to \mathbb{C}$, $$ g(S) = \sum_{T \subset S} f(T) \, \, ...
2
votes
1answer
44 views

Is there a bijection $f: X \to X$ such that $f(a) \succ a$ for some $a \in X$ and $f(x) \succeq x$ for all $x \in X?$

$X$ is a prewellordered set with respect to $\succeq$. The prewellordering is in general not antisymmetric relation in contrast to a well-order, i.e. $x \succeq y$ and $y \succeq x$ doesn't imply ...
0
votes
1answer
27 views

Field property proof

I have tried quite a lot of "turn and twists" but I just can`t get around it. Here it is : if x > y then x > z > y for all $x,y$ in the partially ...
0
votes
2answers
37 views

For each $x,y∈\mathbb N$, if $x≤y$ and $y≤x$, then $x=y$ [duplicate]

Proof: For each $x,y∈\mathbb{N}$, if $x≤y$ and $y≤x$, then $x=y$ By definition of order, $x≤y$ if and only if $x<y$ or $x=y$ By definition of order, $x<y$ if there exist a $K∈\mathbb{N}$ such ...
1
vote
2answers
43 views

For each $x,y,z∈\mathbb N$, if $x<y$ then $x+z<y+z$

For each $x,y,z∈\mathbb{N}$, if $x<y$ then $x+z<y+z$ I know how to solve this if it was $x=y$ then $x+z=y+z$ (which my professor said I need to do) Is there a definition that says I can change ...
1
vote
1answer
23 views

Kuratowski's closure-complement problem for the upper/lower bound functions

This is an order theory problem in the flair of Kuratowski's closure-complement problem. Let $(X,\le)\newcommand{\up}{{\uparrow}}\newcommand{\dn}{{\downarrow}}$ be a set with a reflexive order on it, ...
1
vote
0answers
19 views

Proof of Antisymmetry [duplicate]

I am stuck with proving antisymmetry under the natural numbers. Prove "For each x,y E N, if x <= y and y <= x, then x=y. I am not really sure where to start with this proof. Im assuming I will ...
0
votes
1answer
28 views

Why is this lattice modular?

I'm reading Stanley's Enumerative Combinatorics, and he says every lattice with at most six elements is modular. But what about the lattice below on the right? If $x,y$ are the two elements at the ...
0
votes
1answer
26 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
48 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
64 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
29 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
32 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
23 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
18 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
7 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
32 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
46 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
56 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
32 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.
2
votes
1answer
73 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
220 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
26 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 ...
1
vote
1answer
32 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 ...
2
votes
0answers
40 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
22 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
22 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
44 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
54 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
99 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
44 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
39 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
21 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
28 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
39 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
25 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
40 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 ...
2
votes
1answer
68 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
25 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
198 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
60 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?