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
0answers
17 views

Lattices and Boolean algebra

I have read in a text book that the set of natural numbers form a lattice under divisibility. How can it possibe, since there is no upper bound and therefore a Sup of the set?
2
votes
2answers
11 views

Checking injectivity of a certain function from a union of a family indexed by $K$ to $K$

Let $A = \{ A_k | k \in K \}$ be a family of sets indexed by $K$. By Zermelo's theorem, $K$ can be well-ordered. Now, let $\leq$ be a well-order on $K$. Define $j: \bigcup\limits_{k \in K} A_k \to ...
0
votes
1answer
19 views

Hasse diagram of a total order not linear

A total order is also called a linear order. But the Hasse diagram of a total order does not need to be a simple single line. So the terms 'linear' and 'chain' are misleading. Is this correct?
1
vote
1answer
14 views

Does convergence of bounded, increasing sequences generalize from the set of real numbers to arbitrary partially ordered sets?

If $t$ is any real number, then I can find a strictly increasing sequence $(t_n)$ of real numbers converging to $t$. E.g. $t_n = t - \frac{1}{n}$ would do. Does this generalize to arbitrary partially ...
3
votes
0answers
23 views

Iterate Over Integer Partition Refinement in Sage

A partition of an integer $n$ is a non-decreasing list of positive integers summing to $n$. For example, $3$ can be partitioned as $1 + 1 + 1$, $1 + 2$ or just $3$, but $2 + 1$ is indistinct from $1 + ...
1
vote
1answer
14 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
1
vote
1answer
47 views

Is there any order isomorphic function between $\mathbb N \times \mathbb Z$ to $\mathbb Z \times \mathbb N$?

Is there any order isomorphic function between $\mathbb N \times \mathbb Z$ to $\mathbb Z \times \mathbb N$? (With lexicographical order) Thanks
2
votes
1answer
83 views

Is [a, a[ empty?

Is the segment $[a, a[$ equivalent to the point $\{a\}$ or the empty set $\varnothing$? Can one or other be formally proved? I was wondering because in computer science it is the empty set, as the ...
1
vote
1answer
27 views

Order-preserving maps on a directed-complete poset

Definitons. A poset $P$ is directed if every finite subset has an upper bound in $P$. It is directed-complete if every directed subset has a least upper bound in $P$. For any poset $P$ let $[P\to P]$ ...
1
vote
0answers
50 views

A classification of the types of poset extensions that raise local-global principle is equivelent to the axiom of choice?

EDIT: Completely overhauled the question, remove category theory from it (stated in plain set theory): The original question Adding relations to a partial order Let $X$ be a set and let $P: Pow(X) ...
5
votes
1answer
31 views

Adding relations to a partial order

Let $(X,\leq)$ be a poset. For every $A\subseteq X$, $a \in A$ is called isolated iff there are only finite number of elements in $A$ that can be compared to it. A continuous (probably not the best ...
0
votes
0answers
10 views

Example of non-way-below Auxiliary Relation in a Poset.

As the title have suggested, I am looking for an example of an auxiliary relation in a poset that is not the way-below relation. Any suggestion of books/paper to read is appreciated. Thanks. Edit: ...
0
votes
0answers
25 views

Higher order partial order

I'm trying to find an effective and making sense way (for programming purposes, but also from math interest) to order partial orders, means, given a set and many partial orders (trees) over it. How ...
2
votes
1answer
36 views

Free cocompletion of thin categories

Let $C$ be a thin category. Is there a cocomplete thin category $C\to C'$ such that for every functor $C\to D$ into a cocomplete thin category there is a unique, up to isomorphism, cocontinous functor ...
-1
votes
0answers
41 views

impose an order on R^2 (I think there isn't one)

I think that there is no way to order R^2. Since it appears structurally the same as C, and I've learned from my friend, Rudin, that C is not an ordered set. is this true?
0
votes
1answer
19 views

Partially ordering finite graphs

What are some interesting partial orders on the set of all finite graphs (identified up to isomorphism), apart from the usual (induced) subgraph relation and the (topological) minor relation, and why ...
0
votes
2answers
23 views

Given a partial order $R$ on the set $A$, prove that there exists a total order $\leq$ on $A$ such that $R \subseteq {\le}$

Let $A$ be a finite set, and $\langle A,R\rangle $ be partially ordered. $\textbf{Prove}$ that there exists a total order $\leq$ over $A$ such that $R \subseteq {\le}$. $\textbf{My ...
1
vote
1answer
30 views

Filters and antichains in preorders

In a preorder $\mathbb{P}$ (reflexive and transitive), what means to say that a subset $C\subset\mathbb{P}$ is not contained in any filter of $\mathbb{P}$? For example, it is obvious that if $C$ ...
3
votes
2answers
95 views

How well-behaved can well-orders on $\mathbb{R}$ be?

Well-orders on $\mathbb{R}$ are interesting because they witness the "alephness" of the cardinality of the continuum, and they're therefore connected to the continuum problem. It seems reasonable, ...
22
votes
2answers
2k views

Why do people accept the axiom of choice given the well ordering principle?

We know without any doubt that the axiom of choice implies (in fact is equivalent to) the well ordering principle. The well ordering principle can't be true! If we take the open interval $(0,1)$ for ...
2
votes
1answer
28 views

When is a join semilattice not a meet semilattice?

When would a join semilattice not also be a meet semilattice (and vice versa)? I can't think of any way. An example or two would probably be very helpful.
0
votes
1answer
19 views

If $(A, \preceq)$ is well quasi order, is $(A^\omega, \ll)$ well quasi order as well?

Suppose $(A, \preceq)$ is well quasi order. $\ll$ is subsequence ordering on $A^\omega$ i.e. $u \ll v$ if $v$ has a subsequence $w$ such that $|u| = |w|$ and $u_i \preceq w_i$. Then is it true that ...
1
vote
0answers
53 views

$\epsilon_0$ is closed under addition, multiplication, exponentiation of ordinals

Question: Let $f: \Bbb{N}\rightarrow \text{Ord}$ (where "Ord" is the set of ordinals) be defined inductively by: $$f(0)=\omega\\ f(n^+)=\omega^{f(n)}$$ Let $\epsilon_0=\{\sup f(i) : i \in \Bbb{N}\}.$ ...
2
votes
0answers
49 views

Flip/flop of finite joins and finite meets of lattices

Let $\mathfrak{A}$, $\mathfrak{B}$, $\mathfrak{C}$ be lattices (in fact in the example I have in mind, they are distributive and even co-Heyting lattices). Let maps ...
1
vote
2answers
36 views

Can every poset be toplogically sorted?

A partial ordering $\preceq'$ on $S$ is said to be compatible with another partial ordering $\preceq$ if for all $a,b,\in S$, $$ a \preceq b \Rightarrow a \preceq' b$$ Given a poset $(S, \preceq)$, ...
1
vote
0answers
27 views

Any efficient approach to find the minimal vectors?

$\bullet$ A vector $X=(x_1,\cdots, x_m)$ is less then vector $Y=(y_1,\cdots,y_m)$ when $x_i\leq y_i$, for each $i=1,\cdots, m$, and for at least one $j$, we have $x_j<y_j$. $\bullet$ A vector ...
0
votes
1answer
40 views

Classifying singularities and determing orders of complex functions

Here are a few functions for reference purposes: $f(z) = \frac{sin(2z)}{z^3}$, $ \space g(z) = \frac{sin(z)}{tan(z)}$, $ \space h(z) = z^2 sin(\frac{1}{z})$ Suppose I was calculating the ...
1
vote
0answers
15 views

Characterization of noncommutative $L^2$-spaces as ordered vector spaces

If $M$ is a von Neumann algebra and $\tau\colon M_+\to[0,\infty]$ is a normal, semi-finite, faithful trace, the associated GNS Hilbert space is the completion of $\{x\in M\mid \tau(x^\ast ...
3
votes
1answer
36 views

Is BPIT equivalent to some ordering principle?

Working in $\mathsf{ZF}$, is $\mathsf{BPIT}$ (Boolean Prime Ideal Theorem) equivalent to some statement of the form "every set can be ***ly ordered"? I know that $\mathsf{BPIT}$ implies that every set ...
0
votes
0answers
16 views

“Contiguity” classes of order morphisms

I was having problems with this exercise that seems really hard. Let $X$ and $Y$ be both FINITE posets and $f$, $g:X \rightarrow Y$ order morphisms such that $f \leq g$. Then there exists $f_0, f_1, ...
0
votes
1answer
30 views

Finding distance from valid number

I have a game related problem that is pretty complex. Here is the simplified version of the problem. I have a list of "good" numbers. ...
1
vote
1answer
28 views

If $P$ has all binary joins, and all chain-shaped joins, is $P$ necessarily a complete lattice?

Question. Let $P$ denote a poset with all binary joins, and all chain-shaped joins (of arbitrary cardinality). Is $P$ necessarily a complete lattice? Motivation. Let $f$ and $g$ denote ...
2
votes
1answer
64 views

Every $\alpha < \kappa^+$ can be embedded in any interval of $\kappa^{<\omega}$.

Let $\kappa$ be a cardinal. I want to show that every ordinal $\alpha < \kappa^+$ can be embedded (as an order) in any interval of $\kappa^{<\omega}$, ordered lexicographically. This is exactly ...
0
votes
0answers
10 views

Do the Arithmetic Operations form a Heyting Algebra?

I was reading an article about partial orders, and it gave an exercise to find a relation where multiplication formed meets and addition formed joins (it did not specify an underlying set, but it ...
0
votes
3answers
42 views

Can an ordinal be limit of a smaller set of ordinals?

The Wikpedia article Regular cardinal contains the following weird sentence: An infinite ordinal $\alpha$ is regular if and only if it is a limit ordinal which is not the limit of a set of smaller ...
1
vote
1answer
31 views

No uncountable subset can be well-ordered $\iff$ Hartogs ordinal is $\omega_1$

I'm looking at an exercise which starts as follows: Suppose that no uncountable subset of $\mathcal P\omega$ can be well-ordered (equivalently, the Hartogs ordinal $\gamma(\mathcal P\omega)$ is ...
0
votes
0answers
23 views

Product of directed partial orders

Is a product poset (with componentwise order) of nonempty posets a dcpo if and only if each multiplier is a dcpo? (for both binary and arbitrary products)
6
votes
0answers
67 views

Question about a linear order

Let $L$ be the set of countable limit ordinals. For each $\alpha \in L$, let $\langle \alpha_n : n < \omega \rangle$ be a strictly increasing cofinal sequence in $\alpha$. Define a linear order on ...
2
votes
1answer
48 views

Is there any well-ordered uncountable set of real numbers under the original ordering?

I know that the usual ordering of $\mathbb R$ is not a well-ordering but is there an uncountable $S\subset \mathbb R$ such that S is well-ordered by $<_\mathbb R$? Intuitively I'd say there is no ...
0
votes
1answer
35 views

Get well-order from total order by choosing finite subsets

Exercise 7.9 in this book: Given that any set has a multiple-choice function, ie a function picking out a nonempty finite subset of each nonempty subset, show that any totally orderable set can be ...
1
vote
0answers
22 views

(Partial/total/well-) order vs ordering

Order or ordering – what is the difference? Is either correct? Is one British and one American English? Not exactly a maths question but probably still the best place to ask.
0
votes
1answer
26 views

How do I prove that every chain has an upper bound?

Let $A$ be a non-empty set. Let $X$ be the collection of bijections $f:U→V$ where $U,V$ are disjoint subsets of $A$. Define the relation $≥$ as follows: $$(f:U→V) ≥ (f′:U′→V′) \text{ iff } U′⊆ U ...
10
votes
1answer
624 views

Is directed set countable, if for each element there are only finitely many smaller ones?

A directed set is a pair $(A,\leq)$ where $\leq$ is a reflexive, transitive relation such that for any $x,y\in A$ we have some $z$ such that $x,y\leq z$. (This comes up when dealing with categorical ...
0
votes
1answer
24 views

$ord(f(a)) \leqslant ord(a) $ for every a in G

Let $f: G \to H$ be a group homomorphism. I want to show that: (i) $ord(f(a)) \leqslant ord(a) $ for every a in G (ii) If $ord(a)$ is finite, then $ord(f(a))$ divides $ord(a)$ (ii) If $f$ is an ...
3
votes
3answers
31 views

Is the equivalence of the ascending chain condition and the maximum condition equivalent to the axiom of dependent choice?

Assuming the axiom of dependent choice, for a partially ordered set $(X,\le)$, the following statements are equivalent: $X$ fulfils the ascending chain condition, i. e. every chain $x_1\le ...
1
vote
1answer
40 views

Hausdorff Maximal Principle

"Hausdorff's Maximal Principle" says that any partial order P has a maximal chain (chain = linear suborder). It is equivalent to the axiom of choice. If we restrict Hausdorff's Maximal Principle to ...
1
vote
1answer
26 views

Prove that $R$ is a total order

Prove that $R$ is a total order $$R=\{(x,y)\in \mathbb{R}\times \mathbb{R}~|~ x\geq y\}$$ I just need to figure out the final portion for total order. I already have it at partial order. Thanks for ...
1
vote
3answers
51 views

Name for a “layered” type of partial order?

I have a partial order $\prec$ over a (finite) set $S$ satisfying the following property: There exists a function $f:S\rightarrow \mathbb N$ such that $x\prec y \Leftrightarrow 0<f(x)< ...
1
vote
2answers
27 views

Lexicographic ordering on ${\cal P}(\kappa)$

How is the "lexicographic ordering" (which is supposed to be a total ordering) on ${\cal P}(\kappa)$ defined, where $\kappa$ is any cardinal? (I apologize if this question is a bit fuzzy.)
0
votes
0answers
25 views

Let a and b be commuting elements in a group G such as $a^m=b^n=e$. Prove that $(ab)^{mn}=e$

The problem I am working on says, "Let a and b be commuting elements in a group $G$ such that $a^m=b^n=e$. Prove that $(ab)^{mn}=e$" So what I know from this information is that ab=ba, a is an ...