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

2
votes
0answers
238 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...
1
vote
1answer
124 views

“unexpected” isomorphism between finite posets?

The set of all divisors of a square-free number, partially ordered by divisibility, is trivially isomorphic to the set of all subsets of the set of prime factors, partially ordered by inclusion. Are ...
2
votes
1answer
228 views

algebraic closure and real closure are closure operators?

Are the algebraic closure (of a field) and the real closure (of a totally ordered field) closure operators (when restricted to appropriate sets of fields, so that they are maps on a set instead of a ...
5
votes
1answer
398 views

Is a chain-complete lattice a complete lattice without the axiom of choice?

This question is inspired by this question. Consider the following result: Let $(L,\leq)$ be a chain-complete lattice. Then $(L,\leq)$ is a complete lattice. Can this result be proven without ...
2
votes
2answers
288 views

Bourbaki-Witt fixed point theorem: two questions

Consider the following theorem: Let $f\colon E \to E$ have the propery that $f(x)\geq x$, where $(E,\leq)$ is a non-void partially ordered set with the property that every totally ordered subset of ...
1
vote
2answers
296 views

How to randomly generate weak orderings of a given length in a uniform fashion?

I recently found out how to calculate the number of all possible weak orderings of a given length. Now, however, I am looking for a way not to only count but to also randomly generate these orderings ...
21
votes
6answers
616 views

Embedding ordinals in $\mathbb{Q}$

All countable ordinals are embeddable in $\mathbb{Q}$. For "small" countable ordinals, it is simple to do this explicitly. $\omega$ is trivial, $\omega+1$ can be e.g. done as $\{\frac{n}{n+1}:n\in ...
0
votes
0answers
546 views

Prove that the set of positive real numbers is not bounded from above

I need to prove that $\mathbb{R}_{>0}$ (that is, the set positive real numbers) does not have an upper bound. I've come up with a proof that seems simple enough, but I wanted to check that I ...
5
votes
2answers
262 views

Why is a commutative ring with an infinite number of idempotent elements unstable?

In a book of model theory I found the following statement: A commutative ring with an infinite number of idempotent elements unstable. I haven't manage to prove it yet. As stability in the model ...
2
votes
2answers
91 views

Dense subsets of separative quotients

I have a question regarding the separative quotient featured in this question. I want to show that for every dense subset D of the separative quotient Q it's preimage under h is also dense. I have ...
1
vote
2answers
67 views

Showing that Ab(G) need not be complete

What's the easiest example to show that $Ab(G)$, the set of Abelian subgroups of a group $G$, need not be complete? I heard that $D_4$ was a good example, but $Ab(D_4)=Sub(D_4)$, which is complete. ...
0
votes
1answer
305 views

Order Theory: Definition

What is the difference between : Quasi Orders Partial Orders Well Quasi Orders Well Founded Orders and Complete Partial Orders What is the benefit of each of them if exist ? why do we need such ...
3
votes
1answer
333 views

When is the composition of partial orders a partial order?

I have been doing some thinking about the compostition of relations and I've had trouble remembering a number of simple facts about what happens when we compose specific types of relations. I've had ...
5
votes
1answer
725 views

Quickest way to understand Kruskal's Tree Theorem

I came across the Kruskal Tree Theorem the other day and thought it looked pretty interesting (especially the stronger finite form due to Friedman). I'm currently a first year mathematics ...
2
votes
1answer
80 views

How to deal with Ideals generation from a Poset of sets including the empty set?

This question is strictly connected with this one: Getting a Distributive-Lattice from Poset or, equivalently, a Greedoid from a Poset. I started this question a week ago and I am still struggling on ...
6
votes
3answers
369 views

Getting a Distributive-Lattice from Poset or, equivalently, a Greedoid from a Poset

Theoretic background Lets just set some background to be sure what I am talking about Posets A Poset is defined to be a couple $(S,\leq)$ where a set $S$ and its elements $s \in S$ are connected ...
5
votes
1answer
336 views

Need construction for coequalizer in $\mathbf{Poset}$

My question can be stated quickly: I would like to see a construction of the coequalizer of two arbitrary Poset morphisms (along with a proof of its correctness, of course). Thanks! (The ...
6
votes
4answers
3k views

Simplest Example of a Poset that is not a Lattice

A partially ordered set $(X, \leq)$ is called a lattice if for every pair of elements $x,y \in X$ both the infimum and suprememum of the set $\{x,y\}$ exists. I'm trying to get an intuition for how a ...
0
votes
1answer
110 views

Generated/induced/weak/strong partial orders

Let $f:X \to Y$ be a function. Suppose first that $\leq_X$ is a partial order on $X$. Is it possible to define a partial order $\leq_Y$ on $Y$, induced by $\leq_X$ (and optimal in some way), so ...
3
votes
0answers
103 views

Reference request: Indecomposable representations of posets

Let $I$ be a finite poset. Definition: A representation of $I$ is a functor $I\to\mathrm{Vect}_{\mathbb C}\ $. Equivalently, a representation of $I$ is a module over its incidence algebra $\mathbb C ...
4
votes
1answer
160 views

number of linear orders

It is well known that for every infinite cardinal $\kappa$ the number of non-isomorphic total orders of cardinality $\kappa$ is $2^\kappa$. Who first proved this, and in what context? Was it proved ...
7
votes
1answer
137 views

Total ordering of the reals with a certain property

I was communicated the following 1994 Miklos Schweitzer problem: Is there an ordering of the real numbers such that whenever $x<y<z$ (in this ordering), we have $y \neq (x+z)/2$? I really ...
2
votes
2answers
101 views

Construction of a partial order on a quotient of a coproduct

[NB: Throughout this post, let the subscript $i$ range over the set $\unicode{x1D7DA} \equiv \{0, 1\}$.] Let $(Y, \leqslant)$ be a poset, and $X\subseteq Y$. Let $\iota_i$ be the canonical ...
7
votes
2answers
383 views

Why do torsion-free abelian groups admit linear orders?

I have read a theorem that says that every torsion-free abelian group admits a linear order. The proof used tensor products and so was above my head. I tried to find another proof on the web and I ...
23
votes
2answers
412 views

Are irrational numbers order-isomorphic to real transcendental numbers?

I know that rational numbers are order-isomorphic to real algebraic numbers. Does it imply that irrational numbers are order-isomorphic to real transcendental numbers? I know that the order type of ...
0
votes
1answer
113 views

Section filter of a net and filter generated by a net

From Planetmath: Let $X$ be a set and $(x_i)_{i\in D}$ a non-empty net in $X$. For each $j\in D$, define $S(j):=\lbrace x_i\mid i\le j\rbrace$. Then the set $$S:=\lbrace S(j)\mid j\in ...
1
vote
2answers
176 views

The smallest filter (base) containing a subset of a power set

From Wikipedia's article for filter on a set: $P(S)$ is the power set of a set $S$. Given a subset $T$ of $P(S)$, we can ask whether there exists a smallest filter $F$ containing $T$. I was ...
2
votes
1answer
176 views

Cofinal subset and maximal elements in a poset

Let $(P;\leq)$ be a poset. A subset $A$ of $P$ is said to be cofinal in $P$ if for every $x$ in $P$ there is a $y$ in $A$ such that $x \leq y $. I was wondering if it is true that a subset of $P$ ...
2
votes
2answers
531 views

A question regarding the Continuum Hypothesis (Revised)

Given that the order type of the reals $(\mathbb R,<)$ has no definable points, can it be proven that $|\mathbb R|= \aleph_1$ by virtue of the fact that every uncountable proper subset $S$ of ...
1
vote
2answers
81 views

Does there exist an ordered field where only addition preserves positivity?

I am trying to find a field (I'll settle for other stuff - some type of ring) that is ordered and $a>0,\,b>0$ implies $a+b > 0$ yet $a,b > 0$ doesn't imply $ab > 0$. Much of the ...
8
votes
4answers
287 views

Is there an element with no fixed point and of infinite order in $\operatorname{Sym}(X)$ for $X$ infinite?

Let $X$ be an infinite set. Let $\operatorname {Sym}(X)$ denote the group of all bijections from $X$ onto itself. I have been thinking about the existence of elements of infinite order in this group. ...
2
votes
1answer
442 views

Rudin Theorem 1.11

After spending a few hours trying to understand Theorem 1.11 in Rudin's Principles of Mathematical Analysis, I still don't follow the proof. 1.11 Theorem Suppose $S$ is an ordered set with the ...
1
vote
2answers
149 views

Partial functions and fixed points

Let $\Phi : [\mathbb N \rightharpoondown \mathbb N] \to [\mathbb N \rightharpoondown \mathbb N]$ be the map from the set of partial functions $\mathbb N \to \mathbb N$ to itself (what's a nice way of ...
1
vote
2answers
92 views

Completeness of a poset

Suppose I have a poset $(P,\leq)$, and am trying to prove that it is complete. If, for a general subset $S \subseteq P$, I've come up with a candidate $x$ for its supremum and am trying to prove it is ...
3
votes
1answer
95 views

Question on order ideals

On p. 80 of his General topology, John Kelley gives the following theorem: Let $X$ be a distributive lattice, and let $A \subseteq X$ be an ideal and $B\subseteq X$ a filter such that $A\cap B = ...
10
votes
4answers
605 views

Examples of Galois connections?

On TWF week 201, J. Baez explains the basics of Galois theory, and say at the end : But here's the big secret: this has NOTHING TO DO WITH FIELDS! It works for ANY sort of mathematical gadget! If ...
0
votes
2answers
274 views

How to prove if an infinite set is total ordered?

Given the function: $$f:(a,b)\in\mathbb{Z}\times\mathbb{Z}\longrightarrow ab^2\in\mathbb{Z}$$ What can you say about injectivity and surjectivity? This is not injective. I have easily find ...
4
votes
2answers
177 views

Does the set $\mathbb{Z}$ satisfy the completeness axiom?

The Completeness Axiom states: A set $\mathcal{A}$ satisfies the Completeness Axiom if for every of its non-trivial and bounded subsets, a supremum exists in $\mathcal{A}$. If this is the ...
3
votes
1answer
112 views

A poset that's the union of the lower sets

Let $(P,\leq)$ be a poset, and let $\downarrow\! p = \{ x\leq p\}\subseteq P$. Let $M\subseteq P$ be the subset of all maximal elements of $P$. Question: is there a specific term for a poset ...
1
vote
0answers
69 views

About function inj, surj and something else. Is this exercise resolved correctly?

This is my problem: For every couple of integers $(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ we denote with $r(a,b)$ the remainder of the division between $a$ and $b$. Consider the ...
8
votes
2answers
459 views

Are ideals in rings and lattices related?

There are (at least) two notions of ideals: An ideal in a ring is a set closed under addition and multiplication by arbitrary element. An ideal in a lattice is a set closed under taking smaller ...
5
votes
4answers
765 views

Prove that for any infinite poset there is an infinite subset which is either linearly ordered or antichain.

Let $(X, \leq)$ be an infinite poset. Prove that there is an infinite $X' \subset X$ for which holds one of the following: 1) Induced order on $X'$ is linear. 2) $(X', ...
3
votes
3answers
264 views

Is there a name encompassing both limit inferior and limit superior

Is there a mathematical term which would include both liminf and limsup? (In a similar way we talk about extrema to describe both maxima and minima?) The only thing I was able to find was that some ...
1
vote
1answer
113 views

What elements of the pentagon lattice $N_5$ do not satisfy the distributive law?

I heard that the "pentagon lattice" $N_5 = (\{0,a,b,c,1\},\le)$ is not distributive, where $\le$ is the reflexive transitive closure of $\{(0,a),(a,b),(b,1),(0,c),(c,1)\}$. What elements of $N_5$ do ...
3
votes
4answers
205 views

A certain family of complex functions

Are there an uncountable linear order $(P, \leq)$ and a family of continuous complex-valued functions $\{f_p\colon p\in P\}$ defined on the interval $[0,1]$ such that for any $p<q$, $p,q\in ...
2
votes
1answer
144 views

Connected subsets of lines

For me every connected set has at least two elements. Connected subsets of the real line have non-empty interiors. I am curious if the same is true for connected subsets of any connected linearly ...
4
votes
2answers
267 views

Two order related questions for subgroups of infinite groups

For finite groups what I am asking is really trivial. In finite groups if we pick a non trivial subgroup $H$ of $G$ we can always find (there could be multiple choices) a subgroup that is an immediate ...
2
votes
1answer
171 views

How to show the ascending chain condition

Let $(A,\le)$ be a poset. Suppose that for any $a < b \in A$ and for any chain $Q$ of $A$ whose maximum and minimum are $a$ and $b$ respectively, $Q$ is finite. Let $C$ be the set of all chains of ...
1
vote
2answers
61 views

Minimum size of a subset to know a complete total order

Lets say we have a set $A$. Suppose that $A$ is ordered by $<$, $A$ is completely ordered. $<$ can be defined as $<:=\{(a,b) \in A\times A : a<b \}$ Given that $<$ is transitive, it ...
2
votes
1answer
108 views

What is a binary relation like whose reflexive transitive closure is a partial order?

Let $R$ be a reflexive binary relation and $R^*$ be its reflexive transitive closure. The question is what is the equivalent condition in terms of $R$ to $R^*$ being a partial order. Intuitively, a ...