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 algebraic structures.
4,463 questions
2
votes
1
answer
106
views
Are the Lattice of basis generated topology always distributive?
Let $\mathcal{B}$ be a topological basis, let $\mathcal{P}$ be the topology generated by $\mathcal{B}$. Suppose we define $\mathfrak{P}$ to be the lattice generated by $(\mathcal{P},\subseteq )$. I ...
- 64
0
votes
1
answer
40
views
Are maximal subgraphs related with posets?
I read that given a graph $G$, we say $S$ is a maximal subgraph of $G$ with property $p$ if for all $S'$ contained in $G$ which strictly contain $S$, then $S'$ does not have property $p$.
I was ...
0
votes
1
answer
54
views
Does this local property of a poset imply that it is a lattice?
Birkhoff (1967, sec. II.8) defines a "modular" poset: (1) When $x, y \in J$ and $x$ and $y$ both cover an element of $J$, then they are both covered by an element of $J$ (which may not be ...
- 501
2
votes
0
answers
101
views
Does the existence of a continuous bijection give a useful preorder on the class of topological spaces?
Consider the binary relation $\gtrsim$ between topological spaces defined by
$A \gtrsim B$ iff there exists a continuous (not necessarily bicontinuous!) bijection from $A$ to $B$.
This relation is ...
- 6,940
2
votes
1
answer
121
views
Constructively weaker versions of well-order, well-foundedness and so on
I have heard that, from a constructive point of view, it is quite difficult to show that a given order $X$ is a well-order, i.e. each subset of $X$ has a minimum, or better constructivley $\forall_x(\...
- 309
1
vote
1
answer
55
views
Unable to solve an exercise about the dual of a partially ordered set. Is this a textbook typo?
Page 54, Set theory and logic, Book by Robert Roth Stoll. Unable to do exercise 11.6. There is no errata for Stoll textbook.
I'm unable grasp the meaning of the last sentence:
How can we form a ...
- 141
6
votes
1
answer
477
views
Is a topology determined by its converging nets?
I would like to prove or disprove that the following:
Given a set $X$, if two topologies $\tau_1$ and $\tau_2$ on $X$ are such that for all $\bar{x}=(x_i: i\in I)$ net on $X$ there is an element $x_1\...
- 81
5
votes
0
answers
184
views
Does Birkhoff-von Neumann's Theorem easily imply Hall's Marriage Theorem or equivalent?
The following is a collection of combinatorics theorems commonly refereed as "equivalent" due to one being easily derived from another.
Theorem (Hall).
A finite bipartite graph $G = (A\...
- 7,029
7
votes
1
answer
125
views
Has linear order tetration appeared?
For linear orders $L_1$ and $L_2$, the constructions of linear order addition and linear order multiplication are well-known, they are defined respectively using the disjoint union and cartesian ...
- 1,761
1
vote
0
answers
38
views
Is the class of cycle-free binary relations the same as the class of binary relations whose transitive closure is a strict partial order?
A binary relation $R$ is said to be cycle-free if there are no cycles in the relation, meaning, for every positive integer $n$, there are no $x_1,...,x_n$ such that $x_1Rx_2...Rx_1$. Also, a strict ...
- 24.8k
3
votes
1
answer
80
views
About constructing a normal Suslin tree
In Jech 9.13 he describes how to construct a normal Suslin tree from a given arbitrary Suslin tree. In the second step Jech adds new elements $a_C$ for chains $C = \{ x \in T_1 | x < y \}$ where $y ...
- 137
0
votes
0
answers
24
views
Does the square root preserve the Löwner order? [duplicate]
Let the $n \times n$ real matrices ${\bf A}, {\bf B}$ be symmetric and positive semidefinite. If ${\bf A} \succeq {\bf B}$, can one conclude that ${\bf A}^{\frac12} \succeq {\bf B}^{\frac12}$, i.e., ...
- 23.6k
0
votes
0
answers
60
views
Is there a natural def of divergence on posets
Similar to how we think of divergence of $\mathbb{N}$ or $\mathbb{R}$ one can naturally inherit this concept to talk about divergence on those sets as with the std order. But what about in a more ...
- 49
3
votes
0
answers
92
views
Logic behind shuffled order of pages
I am exporting slides to pdf at an Optoma interactive touchscreen display I use in my lectures. The order of pages in the exported pdf is shuffled and I am trying to understand the logic how the ...
- 3,709
2
votes
2
answers
90
views
Does every poset arise as the reachability relation of some DAG?
Let $G=\left(V,E\right)$ be a directed acyclic graph (DAG). Define a relation $\preceq$ on $V$ by
$$a\preceq b \iff \text{there exists a directed walk from $a$ to $b$}$$
(If needed, allow the length-0 ...
- 47
-1
votes
1
answer
174
views
Prove that the axiom of completeness does not hold for the field of rational functions over $\mathbb{R}$
Prove that the axiom of completeness does not hold for the field of rational functions over $\mathbb{R}$. By explicitly presenting two sets that satisfy the assumptions of the axiom of completeness ...
- 33
10
votes
0
answers
340
views
Is Zorn's Lemma equivalent to the Axiom of Choice for individual sets?
It is well-known that in $\mathsf{ZF}$, the Axiom of Choice and the Well-ordering Theorem are equivalent. What is perhaps less well-known is that there is a "local" version of this ...
- 24.1k
12
votes
1
answer
413
views
Are $(c_0^+, \prec)$ and $(c_0^+, \succ)$ isomorphic?
This is a segue from this question I posted the other day.
For $a, b:\mathbb N\to\mathbb R$, we write $a\prec b$ iff $\{n\in\mathbb N:a_n<b_n\}$ is cofinite. It is easy to see $\prec$ is a strict ...
- 7,029
1
vote
1
answer
94
views
Order preserving maps and maximal antichains
Let $\mathbb{P}$ and $\mathbb{Q}$ be two partial orders. An antichain is a subset $A$ such that all elements in $A$ are pairwise compatible - that is, for all $p,q \in A$, there is no $r$ in the ...
- 8,657
0
votes
0
answers
38
views
Equivalent definition of $T_D$ spaces in Sober case.
Let $X$ be a Sober space, TFAE:
For every $x\in X$, $\{x\}$ is open in $\overline{\{x\}}$.
No proper subspace of $X$ have soberification homeomorphic to $X$.
The soberification is defined to be $\...
- 696
1
vote
0
answers
45
views
Does order preserving bijection (isomorphism) imply irrationality perserving?
I have encountered a math problem that requires the construction of a choice function that picks an irrational number from a closed interval $[a,b]$ of reals. My solution could be made significantly ...
- 381
2
votes
2
answers
193
views
Prove that the ordered set of numerical sequences has uncountable cofinality
Prove that there does not exist a countable set $P$ of numerical sequences such that $\forall(x_n)_{n∈\mathbb{N}}\in\Bbb R^{\Bbb N}\ \exists(p_n)_{n∈\mathbb{N}}\in P\ \forall n \in \mathbb{N}\ x_n\le ...
- 33
3
votes
0
answers
102
views
Understanding the order on $\mathbb{N\times N}$ defined by $(m,n)\leq (p,q)\iff \frac{2m+1}{2^n}\leq\frac{2p+1}{2^q}$. [closed]
I encountered an order relation $\leq$ on the set $\mathbb{N\times N}$ defined by $$(m,n)\leq (p,q)\iff \frac{2m+1}{2^n}\leq\frac{2p+1}{2^q}\text{, for every }(m,n),(p,q)\in \mathbb N\times \mathbb N$$...
- 4,386
0
votes
1
answer
33
views
If a distributive lattice is finitary and has finite upward covers, does its poset of join-irreducibles have finite upward covers?
(This question seems to be just enough out of the ordinary that the standard references do not mention it. So I am documenting it here.)
Suppose $L$ is a distributive lattice, $L$ is finitary (that ...
- 501
6
votes
1
answer
227
views
Why the set of subspaces of countable dimension of a vector space having an uncountable base is not Zorn?
By Zorn's lemma, we know that for a set $A$, if every chain in $A$ has an upper bound, then A contains a maximal element.
Let $V$ be a vector space having an uncountable base and $S$ be the set of ...
- 75
1
vote
1
answer
161
views
Maximal Independent Set in an adjacency and divisibility graph
Here is a problem most likely from a high school competition but I don't know the source. I was stomped by it for a while. We are given a set $\{1, 2, 3, \ldots, 2002 \}$. The question is to find the ...
- 1,506
1
vote
1
answer
70
views
When is the max set of a Priestley space closed?
A Priestley space is a compact partially ordered topological space $P$ with the property that if $x,y \in P$ and $x$ is not less than or equal to $y$, then there is a clopen upset containing $x$ and ...
- 10.9k
0
votes
1
answer
52
views
If a poset is locally finite and modular, must maximal chains between $a$ and $b$ have the same length?
Suppose a poset $P$ is locally finite and also that it is "modular". Specifically, a poset is "modular" iff: if $a \neq b$ both cover $c$ then there exists a $d$ that covers $a$ ...
- 501
0
votes
0
answers
61
views
$\text{TREE}(n)$ and well-quasi-ordered sets
I recently got curious about understanding the growth rate of $\text{TREE(n)}$ (and/or the weaker $\text{tree(n)}$ with unlabeled trees). What I understood so far is that the existence and finiteness ...
- 73
5
votes
1
answer
145
views
How many topological types are realized by countable subspaces of $\mathbb R$?
Earlier today, I thought the answer was "obviously $\frak c$".
Every countable subset of the real line can be encoded into a single binary string by a zigzag interleaving process. So there ...
- 11.7k
4
votes
1
answer
84
views
What are the coatoms of the partial order of equations in the signature of magmas?
Consider the signature of single binary operation $*$, and consider the set $Eq$ of all equations in that signature. I can define a preorder $\geq$ on $Eq$ by stipulating that $E \geq E'$ precisely ...
- 24.8k
7
votes
1
answer
195
views
Are ultraparacompact metrizable spaces orderable (LOTS)?
Let $X$ be a topological space.
$X$ is called ultraparacompact if every open cover of $X$ has a refinement that is a partition of $X$ by clopen (or equivalently, open) sets.
$X$ is called orderable (...
- 7,644
10
votes
1
answer
175
views
Are $\ell^1_+$ and $\ell^\infty_+$ order-isomorphic?
For $a, b:\mathbb N\to\mathbb R$, we write $a\prec b$ iff $\{n\in\mathbb N:a_n<b_n\}$ is cofinite. It is easy to see $\prec$ is a pre-order relation over $\mathbb R^\mathbb N$.
Let
$$\begin{aligned}...
- 7,029
3
votes
1
answer
59
views
Is the category of upward directed sets with order-preserving maps complete?
A filtered set (or upward directed set) is a non-empty preordered set (or proset for short) $(S,\leq)$ s.t. every pair of elements have a common upper bound. A morphism of filtered sets is a morphism ...
- 2,569
1
vote
0
answers
84
views
Prove that the category $\Delta$ of simplicial sets has coproducts.
I'm concerned here with the first part of the exercise IV§9.8, p.159 in "Algebra - third edition, Saunders MacLane, Garret Birkhoff," in which one is asked to
"[sic] Prove that the ...
- 455
0
votes
0
answers
71
views
How to properly formulate the principle of duality for posets
I'm studying order theory from Introduction to Lattices and Order by Davey and Priestley and have come to the principle of duality:
Principle of Duality: Given a statment $\Phi$ about ordered sets ...
- 31
2
votes
0
answers
36
views
Do the lattices of ideals of graded posets have any special properties?
The (order) ideals of a poset form a lattice (under set containment), and the lattice is distributive. Conversely, any finite lattice (and some infinite lattices) is isomorphic to the lattice of ...
- 501
0
votes
0
answers
46
views
Question of proof of a field strictly containing $\mathbb{R}$ not having any Archimedean order
Proposition: Every field $K$ strictly containing $\mathbb R$ does not have any Archimedean orders.
This should follow using the Theorem: If $K$ is an ordered field with an Archimedean order, then ...
- 81
3
votes
1
answer
145
views
Exercise 7(c) in Bourbaki theory of sets, Chapter 3, section 2
Let $E$ be an ordered set, a map $f:E\rightarrow E$ is called a closure if the following 3 conditions hold:
$f$ is increasing;
$f(x)\geqslant x$ for each $x\in E$;
$f(f(x))=f(x)$ for each $x\in E$.
...
- 398
0
votes
0
answers
31
views
Do unbounded sequences on lattices have subsequences for which no further subsequence is bounded?
Let $\Omega$ be a partially ordered set with partial order $\le$ and, furthermore, be an unbounded lattice (there exists a a smallest $x \vee y$ such that $x \le x \vee y$ and $y \le x \vee y$, and $x ...
- 1,553
2
votes
0
answers
88
views
Indiscernible interval?
I'm interested in a certain property of an interval $[a,b]$ in a partial order $L$.
The property is that for any element $c \notin [a,b]$, $a$ and $b$ agree on whether $c$ is large or small: that is,
$...
- 3,052
3
votes
1
answer
97
views
set filter vs poset filter
Jech gives the following definitions in Chapters 7 and 14 of Set Theory (2002)
Given a set $S$, a set filter $F$ on $S$ is a subset of $\mathcal{P}(S)$ satisfying the following properties:
$S \in F$ ...
- 31
1
vote
1
answer
72
views
A special property about functions on directed abelian groups
Let $\Lambda = (\Lambda,+,\leq)$ be a directed, torsion-free abelian group (that is, $\Lambda$ is a torsion-free abelian group together with a partial group ordering $\leq$ such that every two ...
- 83
1
vote
1
answer
104
views
Why do we need a weakly homogeneous (almost homogeneous) partial order to prove that the maximal element forces any formula or it's negation?
A weakly homogeneous partial order $P$ (also called almost homogeneous in Kunnen's set theory book) is such that $\forall p,q \in P$ there is an automorphism $\pi$ such that $\exists r \in P (r \leq \...
- 312
0
votes
1
answer
86
views
Existence of a maximal element
I came across a statement that authors claim is trivial but it is not trivial to me. Take a family of functions defined on a sigma algebra of a subset of a Euclidean space, $u = \{u_1, \dots, u_n\}$. ...
- 325
1
vote
0
answers
51
views
Non principal prime filter over the division lattice
I'm currently studying the division lattice, i.e. the lattice arising from $\mathbb N$ and divisibility relation: $m|n$ iff $\exists q$ such that $n=qm$.
I need to find an example of non-principal ...
- 21
3
votes
0
answers
173
views
Can we avoid the Axiom of Choice by modifying the Well-Ordering Principle?
It is well known that without the Axiom of Choice, many theorems essential to modern mathematics cannot be proven. However, I wonder whether there might be a different route: can we replace the Axiom ...
- 311
3
votes
1
answer
214
views
Counting pairs of strictly increasing sequences
Let $n \geq 1$ and $k \in \{1, \ldots, n\}$. Consider the set $D$ of all pairs
$(\{r_1 < \cdots < r_k\}, \{s_1 < \cdots < s_k\})$
such that $r_d, s_d \in \{1, \ldots, n\}$, $r_1 = s_1 = 1$,...
- 1,257
0
votes
1
answer
86
views
Textbooks combining order theory, topology and algebraic structure
It looks like a greedy title.However, when I learn about construction of real numbers and different equivalent ways to do completion like Dedekind completion and Cauchy completion from some papers ...
- 299
3
votes
0
answers
140
views
A property of a cyclic order on an abelian group
Earlier I came across this problem in the research of 3-line circulant matrices. The problem goes as following: "Let $n > 3$, define rem(s) as the usual reminder of s divided by n (...
- 109