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,464 questions
3
votes
1
answer
84
views
Extending a compatible order on a free monoid
Let $M = \langle a, b \rangle$ be the free monoid on two generators. Let $<$ be a strict partial order on $M$ compatible with its multiplication. (It suffices to require that for all $x < y$, we ...
- 674
5
votes
2
answers
165
views
Construction of a dense linear order with $2^\kappa$ cuts
The question is the following:
Given a cardinal $\kappa$, is there a dense linear order of size $\leq \kappa$ such that there are $2^\kappa$ cuts (a cut is a downward closed subset)?
The question is a ...
- 115
0
votes
0
answers
65
views
What is the name of the property of $x\mapsto 3f(x)$ that its orbits are wellordered by $f$? [closed]
Consider the dynamical map that terminates on all natural numbers:
$f_o:x\mapsto (x+1)/2$ if $x$ odd
$f_e:x\mapsto x/2$ if $x$ even
This is easily proven to terminate for all natural numbers.
Now ...
- 9,768
2
votes
1
answer
113
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
62
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
58
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
115
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,950
2
votes
1
answer
125
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
492
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\...
- 115
5
votes
0
answers
192
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,009
7
votes
1
answer
133
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
47
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
84
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
25
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