Questions tagged [order-theory]

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. Order theory is not about the order of a group nor the order of an element of a group or other alegbraic structures.

Filter by
Sorted by
Tagged with
0
votes
2answers
157 views

Name for a discrete ordered set with finite subranges

Is there a term for a set that is: discrete totally ordered has finite subranges (not a technical term), i.e. for any a and b, $\{x|a<x<b\}$ is finite At first glance, it seems this implies ...
4
votes
1answer
745 views

Cardinality of the set of ultrafilters on an infinite Boolean algebra

Let $\mathfrak B$ be a Boolean algebra with an infinite power $\kappa$. My question is how many ultrafilters does it have? $\kappa$ or $2^\kappa$? Or even smaller?
4
votes
5answers
249 views

Are there methods to well order a finite group in a meaningful way?

Can some finite groups be well ordered in a "meaningful" way? I mean, it is clear that we can trivially find a bijection between $\{1,...,n\}$ and a finite group $G$ with $n$ elements, but I am ...
3
votes
1answer
194 views

Inducing maps between Boolean completions of posets

Given a separative poset $P$, we can form it's Boolean completion $B(P)$. This is a Boolean algebra whose elements are regular cuts on $P$, as defined here. Also, $P$ embeds densely into $B(P)$ by ...
6
votes
2answers
311 views

Stone duality for ideals and filters (exercise)

In A Course in Universal Algebra (Burris, Sankapannavar), the exercise 4.4.7-8, p.158, says: Let $A$ be a Boolean algebra. Denote $A^\ast:=\{\text{ultrafilters of }A\}$, and give $A^\ast$ the ...
4
votes
2answers
364 views

Are the Join and Meet operators on complete lattices both continuous?

Suppose that $(A,\le)$ is a complete lattice, that means $(A,\wedge,\vee)$ is a lattice which satisfies $$\forall B \subseteq A[\bigwedge B\text{ and }\bigvee B\text{ exist}].$$ And of course $(\wp(A),...
13
votes
4answers
540 views

A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets

If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ?
5
votes
1answer
332 views

$M_3$ is a simple lattice

I'd like to prove (exercise 9.5 in Roman's Lattices and Ordered Sets, p.203) that the lattice $M_3$ is simple, meaning that the only congruences on $M_3$ are the trivial ones (the 'equality' ...
2
votes
1answer
301 views

ideals of a ring form a modular lattice

We know that if $M$ is a left $R$-module, then $(\{\text{submodules of }M\},\subseteq)$ is a modular lattice. Taking $M\!=\!R$, we deduce that $(\{\text{ideals of }R\},\subseteq)$ is a modular ...
7
votes
3answers
5k views

Isomorphisms: preserve structure, operation, or order?

Everyone always says that isomorphisms preserve structure... but given the (multiple) definitions of isomorphism, I fail to see how the definitions equate with the intuitive meaning, which is that two ...
1
vote
1answer
69 views

When is an interval (order theory) = line segment (in $\mathbb{R}^n$)?

If $(X,\leq)$ is any poset and $a,b\!\in\!X$, then we define the interval as $$[a,b]_\leq:=\{x\!\in\!X;\;a\!\leq\!x\!\leq\!b\}.$$ If $a,b\!\in\!\mathbb{R}^n$, then we define the line segment as $$[...
1
vote
3answers
324 views

Minimum set of component wise ordering relation

$\leq_{cw}$ is the partial component wise ordering relation. Given a set $M \subset \mathbb{N}_0^n$ we define $N = \min_{cw}(M)$ with $v \in N$ iff if $u \in M$ and $u \leq_{cw} v$ then $u = v$. I ...
3
votes
1answer
417 views

Number of possible partial orderings on a finite set

I've been reading about lattices and partial orders (my reference: Applied Abstract Algebra by Lidl, Pilz) while this question struck me. Let X be a finite set. Is there any way to determine the ...
2
votes
3answers
585 views

Example of directed set (directed towards $x_0$)

On this page there are some examples of directed sets. One of those cites: "If $x_0$ is a real number, we can turn the set $\mathbb{R} − \{x_0\}$ into a directed set by writing $a \leq b$ if and only ...
3
votes
2answers
571 views

Example of total order with some properties that is not well ordered

Is there an example of a total order with properties there is a least element and every element has a (unique) successor not is not also a well ordering?
6
votes
1answer
143 views

The Real line uniqueness …

I have a question in the following exercise: Let $\langle X, <\rangle$ be a total ordering with no first or last element, connected in the order topology and separable.Show that $\langle X,<\...
6
votes
0answers
515 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 ...
2
votes
1answer
162 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
355 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
809 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 ...
1
vote
2answers
695 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
313 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 ...
30
votes
6answers
2k 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 \...
3
votes
1answer
4k 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 haven'...
5
votes
2answers
410 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
151 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
80 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
648 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
906 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 ...
8
votes
1answer
2k 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
206 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 ...
7
votes
3answers
1k 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 ...
7
votes
1answer
762 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 stuff ...
18
votes
6answers
12k 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
173 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 ...
4
votes
0answers
204 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
260 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
175 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
187 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 ...
8
votes
3answers
877 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
825 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
204 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 D\rbrace$$...
2
votes
2answers
331 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
2answers
406 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$ ...
1
vote
2answers
1k 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
88 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
487 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. ...
7
votes
2answers
2k 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
192 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
148 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 ...