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,283
questions
0
votes
1
answer
37
views
Galois connections give rise to complete lattices
I am reading Introduction to Lattices and Order, second edition, by Davey and Priestly. On page 161, it says
Every Galois connection $(^\rhd,^\lhd)$ gives rise to a pair of closure operators, $^{\rhd\...
- 1,889
-2
votes
0
answers
23
views
The supermodularity of probability of intersection [closed]
Given a finite sample space $E$, let $E=\{A_1,A_2,\dots,A_n\}$ be a collection of random events.Then, is $f(S)=\mathbb{P}\{\cap_{A_i\in S}A_i\}$ a supermodular function for $S\subseteq E$?
- 31
0
votes
3
answers
98
views
How to phrase the proof of $m \lt n$ if and only if $m \le n-1$
I have been reading Knuth's "The Art of Computer Programming" and in the mathematical preliminaries chapter of volume 1 there is on page 476 the answer to an exercise where he states
... ...
- 3
0
votes
0
answers
22
views
If sub-universe $S$ of lattice has congruence $\theta$, does the lattice have a congruence $\lambda = \theta \cap S^2$? [duplicate]
Let $(L, \lor , \land )$ be a lattice and $S$ a sub-universe of the lattice. A sub-universe of a lattice will be any subset of the lattice set that is non-empty and closed under $\land$ and $\lor$. ...
- 3,468
0
votes
0
answers
41
views
Understanding the definition of congruences over a lattice
Let $(L, \land, \lor)$ a lattice and $\theta$ a binary relation over $L$. We say $\theta$ is a congruence iff
$$
x_0\theta x_1, y_0 \theta y_1 \Rightarrow (x_0 \lor y_0)\theta(x_1 \lor y_1)
$$
(and ...
- 3,468
5
votes
3
answers
487
views
Motivation of inventing concept of well-ordered set?
I've started studying set theory for a while. I understand what is an ordered sets but i still fail to see what motivated mathematicians to invent these concept.
Could you please enlightment me ?
...
- 1,350
0
votes
1
answer
45
views
Number of lattices over a finite set
I'm interested in finding a general formula for the number of lattices possible over a finite set $S$ as a function of the set's cardinality.
For instance, how many lattices over $\{1, 2, 3\}$ are ...
- 3,468
2
votes
1
answer
55
views
Do the monotone maps from a poset into a Heyting algebra form a Heyting algebra?
I am interested in generalizing the fact that the up-sets of a poset always form a Heyting algebra.
Let $P$ be a poset and $H$ a Heyting algebra. $\operatorname{Hom}(P,H)$ can be made a bound lattice ...
- 43
2
votes
2
answers
65
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
49
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$. ...
- 967
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 ...
- 387
0
votes
0
answers
53
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
478
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.5k
0
votes
1
answer
26
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
56
views
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
42
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\...
- 438
3
votes
0
answers
73
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
2
votes
1
answer
92
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 ...
- 438
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
120
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,683
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
50
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
1
vote
0
answers
40
views
List of all posets of size $n$ for small $n$? [duplicate]
Is there a good reference for, or an easy way of generating, all Hasse diagrams of partially ordered sets of small size (say $n\leq 6$)? I am familiar with the OEIS entry A000112 listing the number of ...
- 1,307
2
votes
0
answers
50
views
Converting "improper" partial order to total order
I suspect that if I knew what to search for, this would be easy to find an answer to, but I don't know what the proper name is for the input portion of the problem statement.
I have a set and a ...
- 663
0
votes
0
answers
20
views
Optimization of totally ordered set valued function.
I am familiar with the meaning of optimizing a function $f : \Omega \to \mathbb{R+}$. However I was just wondering if there's some theory of math explaining how to optimize mapping from $f : \Omega \...
- 5,317
2
votes
0
answers
63
views
Necessary and sufficient conditions for finding graphs based on posets
Let $\Gamma$ be any graph (say finite, simple, undirected), then denote by $P(\Gamma)$ the set of all non-isomorphic subgraphs of $\Gamma$. Let $\gamma$ be another graph, then denote $\gamma \subseteq ...
- 967
1
vote
1
answer
52
views
Lattice with supermodular height function is lower semimodular
Question
Let $(L,\leq)$ be a lattice of finite length and let its height function $h$ be supermodular, meaning that
$$h(x \wedge y) + h(x \vee y) \geq h(x) + h(y) \quad \forall x,y\in L.$$
Does it ...
- 23.1k
0
votes
1
answer
49
views
Understanding ordered fields and the subset $P \subseteq \mathbb{F}$ of positive elements.
I'm following Real Analysis: A Long-Form Textbook (Jay Cummings) and there is a part about defining the positive set $P \subseteq \mathbb{F}$.
The following definition is given:
An ordered field is a ...
1
vote
0
answers
63
views
Is it possible to order proper classes?
Let's assume that we have NBG/MK, with its global choice.
Assume a relation F, a family of classes, is given. (a class-function, such that $F(x)=\bigcup\{s|(x,s)\in F\}$ is considered to be "in&...
- 842
2
votes
0
answers
29
views
Counting the number of posets with fixed dimension
I'm reading through a few of Trotter's papers on dimension and cardinality over certain posets, and I was curious about some combinatorial questions on posets with fixed dimension.In particular, what ...
- 63
1
vote
1
answer
27
views
How to get the distributive law for an l-group?
In Birkhoff an l-group G is defined as a group that is also a poset and in which group translation is isotone:
\begin{gather*}
x\leq y\implies a+x+b\leq a+y+b\;\forall a,x,y,b\in G,
\end{gather*}
and ...
- 23
1
vote
0
answers
46
views
Why can't po-groups have a greatest element?
Birkhoff defines a po-group G as a group that is also a poset and in which group translation is isotone:
\begin{gather*}
x\leq y\implies a+x+b\leq a+y+b\;\forall a,x,y,b\in G.
\end{gather*}
A trivial ...
- 23
13
votes
2
answers
2k
views
What are ordered pairs, and how does Kuratowski's definition make sense?
I have been watching the YouTube series 'Start Learning Mathematics' by The Bright Side of Mathematics.
I am currently on episode #3 of the set series and he's just introduced us to 'ordered pairs.'
...
0
votes
0
answers
53
views
Ranking and unranking of a binary subset
Let's consider "N" bits.
We want to rank and unrank a specific subset of bit combinations based on the following criteria -
...
- 13
0
votes
0
answers
15
views
Number of initial segments in a certain poset
For $[n] = \{1,\dotsc,n\}$, the set $\binom{[n]}{k}$ of $k$-element subsets of $[n]$ has a partial order $\leq_p$ induced by the total order on $[n]$. An element $S$ of the set $H(n, k, l) := \binom{\...
- 2,254
4
votes
1
answer
71
views
Is multiplication of finite partial orders cancellative? can we even prove the simplest case?
I was interested in whether taking the product of two finite partial orders is cancellative, i.e. whether $A \times C \cong B \times C$ implies $A \cong B$. I found that this was too difficult, so I ...
- 5,633
0
votes
0
answers
32
views
Binary combinations with special criteria
Let there be a binary value of "n" bits which consists of only "0"s and "1"s.
If we pick exactly "r" "1"s of them (and the rest "n-r" are &...
- 13
0
votes
1
answer
28
views
Binary combinations - rank and unrank [closed]
Let's consider a binary value of "n" bits (which consists of only "0"s and "1"s).
We want to pick exactly "r" "1"s of them (and the rest "n-r&...
- 13
1
vote
1
answer
82
views
Is it possible to explicitly construct a total order in $\mathbb R^{\mathbb R}$? [duplicate]
Is it possible to explicitly construct a total order in $\mathbb R^{\mathbb R}$?
There is a total order in $\mathbb R^{\mathbb R}$ according to Well-ordering theorem. But I'm curious if there's an ...
- 358
0
votes
1
answer
30
views
Reconciling Continuity of Binary Relations with Continuity of Functions/Correspondences
I asked this question in the Economics StackExchange as well, but figured it may be better-suited here.
There are various ways to express the concept of continuity of a binary relation, but one I've ...
- 91
2
votes
1
answer
56
views
How to get the height function for modular lattices?
In these notes, it is said that for modular lattices of finite lengths the height function
\begin{gather*}
h(x)=lub\{l(C):C=\{x_0,...,x_n:x_0=O\prec...\prec x_n=x\}\}
\end{gather*}
obeys
\begin{gather*...
- 33
1
vote
1
answer
78
views
Complete iff Compact in Well-Ordered space
Let $T=(S, \leq, \tau)$ a well-ordered set equipped with order topology (defined here).
Definition 1: $T$ is called complete iff every non-empty subset of $T$ has a greatest lower bound (inferior) and ...
- 188
2
votes
0
answers
73
views
Set of ordinals isomorphic to subsets of total orders
Background. Given a poset $(S,<)$ we'll indicate with $\tau(S,<)$ the set of all the ordinals which are isomorphic to a well ordered subset of $(S,<)$. We're in $\mathsf{ZFC}$.
Questions.
...
- 509
3
votes
1
answer
102
views
Equivalent definitions for GO-spaces (generalized ordered spaces)
GO-spaces (= generalized ordered spaces) are subspaces of LOTS (linearly ordered topological spaces). There are several definitions in use and I am wondering how to show the equivalence between them.
...
- 4,500
1
vote
0
answers
37
views
Binary subset rank and unrank [closed]
Let there be N=5 bits.
We want to rank and un-rank a specific subset of bits based on the following criteria -
...
- 13
0
votes
0
answers
21
views
Find a set A that satisfies the following
Find a set A with a order relation such that:
$$\forall a, b,c \in A, \inf({\sup({a,c}),b}) = \sup({\inf({a,b}),\inf({a,c})})$$
It's easy to find a set A of two or one element that satisfies this, but ...
- 411
7
votes
0
answers
144
views
Is every set an image of a totally ordered set?
It is known that the statement "Every set admits a total order" is independent of ZF. See here, for example. However, can it be proven in ZF that for every set $Y$, there exists a totally ...
- 657
3
votes
2
answers
119
views
Order-automorphisms of countable total orders
Background. These are the last two questions of a problem (I've already proved that $|\operatorname{Aut}(\mathbb Q,<)| = |\operatorname{Aut}(\mathbb R,<)| = 2^{\aleph_0}$ and that if $|\...
- 509
0
votes
1
answer
63
views
Partial order on sets and application of Zorn's Lemma to construct well-ordered subset
I would appreciate help with the following question:
Let $(A,<)$ a linear ordered set.
a. Let $F\subseteq P(A)$. Prove that the following relation is a partial order in $F$: $X\lhd Y$ for $X,Y\in F$...
- 35