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,277
questions
2
votes
2
answers
59
views
Every countably infinite linear order has a copy of $\omega$ or $\omega^{op}$
Every countably infinite linear order $L$ has a copy of $\omega$ or $\omega^{op}$. I'm interested in different kinds of proofs of this fact.
One I came up with is: pick $x_0 \in L$. Wlog $[x_0, +\...
- 349
0
votes
1
answer
48
views
Is the grading of a poset unique?
A graded poset is a poset $(P,\leq)$ with a map $\rho:P\rightarrow\mathbb{N}$ where $\rho$ is strictly monotone, and if $x,y\in P$ where $y$ covers $x$, (i.e. $x\lessdot y$), then $\rho(y)=\rho(x)+1$. ...
- 187
0
votes
1
answer
48
views
Problem with dense set
On ' Set theory with an introduction to real point sets'(Dasgupta, Abhijit ,2014) i found this exercise:
This is interesting because compare the topological (left,1) and order (right,2) definition of ...
- 375
0
votes
0
answers
38
views
Extending the $M_3,N_5$ theorem from distributive lattices to frames
It is known that a lattice $L$ is distributive if and only if it does not contain the diamond $M_3$ or the pentagon $N_5$ as sublattices.
A complete lattice is one in which every subset has an infimum ...
- 53
7
votes
3
answers
471
views
Would the category of directed sets be better behaved with the empty set included, or excluded?
In a topology book of mine, a directed set is defined as a nonempty set $D$ equipped with a relation $R$ that is transitive, reflexive, and for all elements $x$ and $y$ of $D$, there exists a $z$ in $...
- 21.3k
0
votes
1
answer
25
views
terminology related to inducing a total order
Imagine I have 10 students in an elementary school. I believe it is proper to say the following: The students' age induces a total order on the students (assuming no 2 students have the exact same age)...
1
vote
1
answer
44
views
+50
Proof of variant Sperner's Theorem for divisibility posets
I'm trying to determine the size of the maximal antichain in the poset of divisors of $N$ where the partial order is divisibility. Looking at the prime factorization of $N=p_1^{e_1}\cdots p_d^{e_d}$ ...
- 5,182
1
vote
1
answer
41
views
Partial order on power set & set of partial orders
Consider a set $X$ and a partial order $\preceq$ on the power set $2^X$ of $X$. We assume that $\preceq$ extends the usual subset relation $\subseteq$, i.e. whenever $A\subseteq B\subseteq X$ then $A\...
- 428
3
votes
0
answers
72
views
Show the following forcing poset is $\sigma$-centered
In Kunen, there's the following exercise:
Assume MA(κ)
and (X,<)
be a total order with |X|≤κ
, then there are $a_x$⊂$ω$
such that if x<y
then $a_x$⊂∗$a_y$
. (x⊂∗y
if |x−y|<ω
and |y−x|=ω
.)
...
- 31
1
vote
1
answer
80
views
Convexity structures and partial orders
Can any convexity structure be defined by a partial order $\preceq$ in the sense of the order topology: a given set $A$ is convex if for any $a,b \in A$ and any other element $c$ for which $a\preceq c ...
- 428
0
votes
0
answers
42
views
Is $\mbox{row}_i(A) \cup \mbox{col}_j(A)$ for a matrix $A$ a thing?
In working on a research problem in order theory, I have encountered a symmetric rank-1 matrix that can be expressed as
$$
A = 30 \begin{pmatrix}
1 \\\\ 1/5 \\\\ 1/2 \\\\ 1/6 \\\\ 1/15 \\\\ 1/30
\...
- 2,170
3
votes
1
answer
17
views
Permutations maximally matching given pairwise order relations
Given $n \in \mathbb{N}$ and a sequence of $T$ pairwise orders $(i_t, j_t)$'s for $1 \leq t \leq T$.
Q: Are there any existing algorithms to find permutations of $[n]$ ($\sigma \in S_n$) such that as ...
- 2,150
1
vote
3
answers
112
views
Symbolic notation for "$A_1\subseteq A_2\subseteq\cdots$"
Background
Definition: A ring $R$ is said to satisfy the ascending chain condition (ACC) for left (right) ideals if for each sequence of left (right) ideals $A_1,A_2,\ldots$ of $R$ with $A_1\subseteq ...
- 3,641
0
votes
0
answers
35
views
Why Is the Following Proof of a Finite Nonempty Totally Ordered Set Containing Its Maximum Wrong?
I wish to prove the result suggested in the title without induction on the cardinality of set. Here is my approach:
Let $S$ be a finite nonempty totally ordered set, i.e. $S=\lbrace x_{1},x_{2},\ldots,...
- 1
0
votes
1
answer
49
views
Congruences on the pentagon lattice $\mathcal{N}_5$
Let $\mathcal{N}_5$ refer to the Pentagon lattice, or the lattice generated by the set $\{0, a, b, c, 1\}$ subject to $1 > a$, $1 > c$, $a > b$, $b > 0$ and $c > 0$.
My aim is to find ...
- 497