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

4
votes
2answers
100 views

$f'(x)\geq 0$ only, but still strictly increasing

It is a quick corollary of the Mean Value Theorem that for a real differentiable function $f:(a,b)\rightarrow\mathbb R$ that if $f'(x)\geq 0$ for all $x\in (a,b)$ then $f$ is (weakly) increasing if ...
0
votes
0answers
15 views

strict partial orders that guarantee monotonic orientation functions

Given a strict partial ordered set $>$ over a set $V$. Consider its directed acyclic graph $G=(V,E)$ where $(v,u)\in E$ if $u> v$ and there is no $w$ s.t. $u> w$ and $w>v$ Consider the ...
0
votes
2answers
17 views

Prove that a simple ordering implies a partial ordering

I am having difficulty proving theorem 55 section 3.2 page 73 of Patrick Suppes Axiomatic Set Theory. This is the theorem to be proven. (R is a simple ordering) ⇒ (R is a partial ordering). He states ...
1
vote
0answers
48 views

Olympiad problem similar to Sperner's theorem, inspired by OMM 2 ( unproven conjecture of mine)

This problem is inspired by problem 2 here. Consider a set of cubes $F$, such that each corner $(x,y)$ of any given cube of $F$ satisfies $0\leq x,y \leq n$, and each cube has a corner with ...
0
votes
0answers
30 views

Intersection/conjunction matrix and transforms?

I'm looking for a method to understand particular types of inclusion/intersection between objects (sets). Say I have a collection of sets, and between every pair of sets [A,B] I can derive a number ...
1
vote
1answer
43 views

A question on proof of the Zermelo's theorem “Every set is well-orderable.”

There exists some proof for the theorem. Some of them use Transfinite Recursion. Some of them use same argument with the following. Proof:(copied from proofwiki) "Let $S$ be a set. Let ...
1
vote
0answers
24 views

A group with an element of finite order and another element of infinite order?

I have a (probably) stupid question. I'm in an intro to group theory class and I am trying to better grasp the concept of element order. My question is if I have a group and it has an element of order ...
0
votes
0answers
27 views

order relations & doubts

It is given a relation $R=\left \{(1,1); (2,2); (3,3); (4,4); (5,5); (3,5); (4,3); (4,2); (4,5); (2,5)\right \}$ for a set $A=\left \{ 1,2,3,4,5\right \}$. I found this relation is reflexive, ...
0
votes
0answers
13 views

Definitions Continuity Using the Order (Landau) symbolism.

Is an $o(1)$ function always continuous?
0
votes
2answers
35 views

Prove that every discrete poset is projective.

Is this proof correct (assuming the Axiom of Choice)? $e:P\longrightarrow Q$ epic, then $e$ is a surjection (Proof that the epis among posets are the surjections). For any arrow, $f:A \longrightarrow ...
1
vote
2answers
31 views

Order of $ab$ and inverses

Let $a$ and $b$ be elements of a group, with $a^2=e, b^6=e$ and $ab=b^4a.$ Find the order of $ab$ and express the inverse in each of the terms $a^mb^n$ and $b^ma^n.$ Just want to cross check my ...
1
vote
1answer
49 views

Abelian Group G and it's order (Let G be an abelian group, and let a∈G)

I already asked this question. However, it was closed off. I now have inserted by attempt at the solution: Let $G$ be an abelian group, and let $a\in G$. For $n≥1$, let $G[n:a] := \{x\in G:x^n ...
1
vote
0answers
32 views

Abelian Groups and orders

I came across this question, and was wondering what the notation G[n : a] means. Is x the generator? Any comments/explanations will be of great help. The question I found was: Let $G$ be an abelian ...
0
votes
1answer
24 views

Definitions On Landau Notation (Big O and little o)

What are the definitions on Big O and little o for when $x \in R^m$ approaches $s\in R^m$ And not $x$ going to infinity?
2
votes
1answer
24 views

Proving that restrictions of partial orders are partial orders

Prove: A set has a partial-order relation $R$ on it. $P$ is a subset of this set. Prove that the restriction of $R$ to $P$ is itself a partial-order relation. Assume that this relation, $T$, ...
0
votes
0answers
43 views

A function is monotonically increasing if for each i, j ∈ ℤ m, i < j ⇒ f(i) ≤ f(j).

Heres the whole question but I'm completely lost on even how to start or what to do. If anyone wouldn't mind showing me how to do part a I think I might be able to nudge my way through the rest. For ...
4
votes
1answer
45 views

How many chains are there in a finite power set?

Let $A$ be a finite set with $n$ elements. How many chains are there in $\mathcal P(A)$ -- that is, how many different subsets of $\mathcal P(A)$ are totally ordered by inclusion? It's easy enough to ...
1
vote
1answer
60 views

On the relation of Completeness Axiom of real numbers and Well Ordering Axiom

In my abstract algebra book one of the first facts stated is the Well Ordering Principle: (*) Every non-empty set of positive integers has a smallest member. In real analysis on the other hand one ...
3
votes
1answer
88 views

Why isn't there a total order of $\cal P(\Bbb R)$?

I have heard that, in some models of ZF, $\cal P(\Bbb R)$ has no total order. How could one prove this? I already know that $\Bbb R$ isn't necessarily well-ordered. I'm guessing that one could reduce ...
1
vote
0answers
22 views

Inclusion in posets

In this problem we work in the poset of naturals with the divisibility order, i.e, $k \leq n$ if and only if $k \ \vert \ n$. For $i \in \mathbb{N}$ fixed let $A_i:= \big\lbrace p_i^{\alpha_i} : ...
0
votes
1answer
16 views

How big the maximal decrease in consecutive elements of a sequence?

Consider a sequence $(s_1, ..., s_k)$, and we have it sorted in decreasing order $(\tilde{s}_1, ..., \tilde{s}_k)= (\sigma(s_1), ..., \sigma(s_k))$. Define $k_{\max} = \max \left( \max_i \left( s_i ...
0
votes
1answer
40 views

Why is the union of two closed sets again closed in the Scott topology?

I want to figure out why the Scott topology really forms a topology. In particular, I want to find out why the union of two closed sets is again closed. So say we have a partial order $P = (P, ≤)$. A ...
3
votes
2answers
85 views

The $n$-cells of a modular lattice are antichains

The terminology "$n$-cell" is made up by me, and I'd love to hear if this has an official name. Given a poset $(X,\le)$, define the set $A_n$ of $n$-cells of $X$ recursively as follows: An ...
2
votes
0answers
44 views

Name of the class of maps between posets such that $f(x)\le f(y)\implies x\le y$

Is there a name for such functions $f:\mathfrak{A}\rightarrow\mathfrak{B}$ from a poset $\mathfrak{A}$ to a poset $\mathfrak{B}$ that $$f(x)\le f(y)\implies x\le y$$ (for every $x,y\in\mathfrak{A}$)?
0
votes
0answers
25 views

Prove that this is a partial order

I am reading Charles Pinter's "Set Theory" and I found an exercise which I can't resolve. Maybe someone can help me. It says: We will consider pairs $(B,G)$ where $B \subseteq A$, and $G$ is an ...
1
vote
0answers
34 views

If not $b<a$, then $a\leq b$

In trying to prove the following inequality $\neg(a\leq b)\Longrightarrow b<a$ i could produce the following indirect proof: Let $\neg(a\leq b)$. Let $\neg(b<a)$ But ...
0
votes
0answers
19 views

Is there a name for a total order with a zero element?

Is there a name for a total order equipped with a zero/bottom element? (And not necessarily a unit/top element.)
0
votes
2answers
26 views

Can an uncountable set be a “chain”?

In the Wikipedia page about total orders, it's stated that a "chain" is a synonym for a totally ordered set. But this makes no sense to me, since "chain" seems to suggest countability, and yet the ...
0
votes
0answers
61 views

Equivalence of two definitions of complete distributivity

I would like to know if the following alternative definitions of complete distributivity are equivalent. Let's begin with defining choice functions: For any set $S$ and $U\in ...
0
votes
1answer
30 views

Question about proof of “every finite poset has a maximal element”.

I have seen various proofs (see, for example, here: http://math.stackexchange.com/a/436074/264885) where we're saying if $a$ is not a maximal element, then there necessarily is some $b$ such that $a ...
5
votes
1answer
53 views

Is the width of a poset well-defined?

According to the Wikipedia definition (current revision), the width of a poset is the cardinality of any maximum antichain, where "maximum antichain" here means an antichain of maximal cardinality. ...
-1
votes
1answer
31 views

Connections between Posets and WQO's

Here is the question that I posted on the Mathematics Chat Room that I was unable to find an answer to: Question: Under what conditions/properties is a poset ever a wqo (well-quasi-order)? Can we ...
6
votes
1answer
109 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
123 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
164 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
23 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
40 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
24 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
36 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
41 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
26 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
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 ...