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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
90 views

Partition of $\mathbb R$ in convex subsets/badly ordered sets

Background: These questions come from two different exercises, but since the first is much shorter and of the same kind of one of the others, I preferred to put everything in only one thread. (We work ...
leluch_l8r4's user avatar
1 vote
1 answer
52 views

A partially ordered set has all suprema iff it has all infima

Let $(P, \leq)$ be a partially ordered set. We will show that every nonempty set bounded above in $P$ has a supremum iff every nonempty set bounded below in $P$ has an infimum. Obviously, it suffices ...
Smiley1000's user avatar
5 votes
0 answers
77 views
+50

Partial order where only some elements are reflexive

Are there interesting examples of "almost" partial orders $\preccurlyeq$, where only some elements $x$ satisfy the reflexivity axiom $x \preccurlyeq x$, but every $x$ has at least some $y$ ...
Jannik Pitt's user avatar
  • 2,000
0 votes
0 answers
16 views

$P = (X, \leq)$ ... vertex-edge partial order of the graph $W_4$, $\text{dim}(P)$=?

Let $P = (X, \leq)$ be a vertex-edge partial order of the graph $W_4$. Calculate $\text{dim}(P)$. All the theory we have covered: Let $G$ be a graph. The vertex-edge incidence partial order $P = (X, \...
ukm2030's user avatar
0 votes
0 answers
59 views

Categories in which there is a mono $A \to B$ iff there is an epi $B \to A$

Consider the property $P$ of a category $\mathcal{C}$ that for two objects $A$, $B$ in $\mathcal{C}$ there exists a monomorphism $A \to B$ iff there exists an epimorphism $B \to A$. Does the property $...
Smiley1000's user avatar
0 votes
0 answers
31 views

Binary subset rank and unrank [closed]

I want to rank and unrank a "K" bit binary subset within a set, where only $\leq$ "m" consecutive $0$s and $\leq$ "n" consecutive $1$s are allowed. I referred to the ...
Dave's user avatar
  • 1
0 votes
0 answers
33 views

Find necessary and sufficient conditions for ordinal monotonicity.

First of all let's we remember the following result. Theorem Let be $\lambda$ and ordinal: a predicate $\mathbf P$ is true for any $\alpha$ in $\lambda$ when the truth of $\mathbf P$ for any $\beta$ ...
Antonio Maria Di Mauro's user avatar
2 votes
0 answers
17 views

Let $f(x) \in F[x]$, and $K / F$ an extension which contains $R_f$, the set of all root of $f(x)$. show the equivalence for a subfield $D \leq K$

I have to show the equivalence of this Let $f(x) \in F[x]$, and $K / F$ an extension which contains $R_f$, the set of all root of $f(x)$. show the equivalence for a subfield $D \leq K$ : (a) $D$ ...
Tyson Bett's user avatar
1 vote
0 answers
9 views

Stratification associated to hyperplane arrangement induced by projective compactification of linear space

I am reading this Brief Introduction to Tropical Geometry and I am trying to understand section 5.4. In particular I want to understand the following construction given at the beginning of the chapter:...
mijucik's user avatar
  • 535
2 votes
0 answers
65 views

Law of Trichotomy for Well-Orderings

Often in beginning set-theory courses, and in particular in Jech's book Set Theory, it is proved from scratch that given any two well-orderings, they are isomorphic or one is isomorphic to an initial ...
rea_burn42's user avatar
0 votes
0 answers
16 views

Partial Orders on Integer Partitions

My question is the following: An integer partition $\lambda$ can be represented as an integer sequence $(f_1,f_2,f_3, \cdots)$ where $f_i$ is the number of parts used in $\lambda$. For instance, $4 + ...
ALNS's user avatar
  • 457
0 votes
0 answers
36 views

Functions which commute with incomparable elements

I have a claim that I believe to be true, but am not sure how to prove it. Suppose I have a (strict) partially ordered set $(A, <)$ and some other set $B$ and a function $f : A \times B \to B$ such ...
NathanLiitt's user avatar
2 votes
1 answer
46 views

Countable, self-similar total orders

A total order $I$ is said to be weakly self-similar if there exists a proper subset $J \subsetneq I$ together with a bijective, order-preserving function $f:I \to J$ (that is, $J$ is isomorphic to $I$)...
Andrea Marino's user avatar
4 votes
1 answer
71 views

In a poset with a cofinal chain, does every cofinal subset admit a cofinal chain?

Let $(P, \le)$ be a partially ordered set. A subset $A\subseteq P$ is a chain if any two of its elements are comparable. A subset $A\subseteq P$ is cofinal if every element of $P$ is less than or ...
PatrickR's user avatar
  • 4,292
4 votes
1 answer
49 views

Cofinal subset equivalent to unbounded subset?

As stated in the title, given a poset $(S,\leq)$ I think it's trivial that an unbounded subset $A \subseteq S$ is cofinal, but does the opposite implication hold? Definition 1. A subset $X$ of a poset ...
leluch_l8r4's user avatar
5 votes
2 answers
155 views

Is subset relation preserved under limit for Hausdorff metric?

Let $X$ be a metric space. I consider elements in $Y=2^X\setminus \emptyset$ and use the Hausdorff metric for $Y$. Suppose that $A_n \subseteq B_n$ for $A_n,B_n \in Y$ and $A_n \rightarrow A$ and $B_n ...
Paul H.Y. Cheung's user avatar
5 votes
3 answers
182 views

Are linearly ordered topological spaces well-based?

A linearly-ordered topological space or LOTS is one whose topology admits a basis generated by open intervals of a total ordering of its points. A well-based space is one which admits a local basis of ...
DanTheMan's user avatar
  • 153
1 vote
1 answer
46 views

Does every set with a supremum contain a monotone net converging to that supremum?

It's well known that if $U \subset \mathbb{R}$ is bounded, then there exists a monotone increasing sequence $(x_{n})^{\infty}_{n=1}$ converging to $sup(U)$. My question is: Let $X$ be a lattice, and ...
user33598's user avatar
0 votes
2 answers
33 views

Relations Symmetry and Transitivity

Given the following Relations over the set $M := \{α, β, γ\}$ $R1 := \{(α, α), (α, β), (β, α), (β, β), (γ, γ)\}$ How is $R1$ transitive? The condition for transitivity is $(a,y)\in R1 \text{ and }(...
robsmayer's user avatar
1 vote
0 answers
44 views

simplicial category is generated by cofaces and codegeracies

As the title says, I'd like to understand whether the following proof of the well known fact that give $f \in \Delta([m],[n])$ weakly increasing is uniquely determined by being $f = \delta^{i_1}\circ \...
jacopoburelli's user avatar
0 votes
1 answer
38 views

Necessity of denseness and completeness for a surjective monotone being continuous

It turns out that the familiar result that surjective monotones $\mathbb R\to\mathbb R$ are continuous extends to general LOTS (linearly ordered topological spaces): Theorem. If $X$, $Y$ are LOTS ...
Atom's user avatar
  • 3,925
6 votes
1 answer
187 views

Number of surjective functions with given property

Let $n \in \mathbb{N}, n \geq 2$ and $M = \{1, 2, \ldots, n\}$. Show that there are more than $2^n$ surjective functions $f : \mathcal{P}(M) \rightarrow \{0, 1, \ldots, n\}$ such that $f(A) \leq f(B)$ ...
Stevineon's user avatar
  • 175
0 votes
0 answers
26 views

Relabel According to the Order of First Occurrence

Let $a\in\mathbb R^n$ be a tuple of length $n\in\mathbb Z_{>0}$. Let $X=\{a_i:1\le i\le n\}$ be the set of elements of $a$ for $x\in X$ let $$i(x)=\min\{j:a_j=x\}$$ be the first occurence of $x$ in ...
Matija's user avatar
  • 3,558
1 vote
1 answer
40 views

How are the two definitions of Eulerian posets equivalent?

I have been following Stanley's Enumerative combinatorics for the definition of an Eulerian poset. It is defined as follows: Definition: A finite graded poset $P$ with $\hat{0}$ and $\hat{1}$ is ...
Vasac's user avatar
  • 73
3 votes
2 answers
107 views

Is $\emptyset : \emptyset \to \emptyset$ an isomorphism from $(\emptyset, \leq)$ to $(\emptyset, \leq)$?

I was asked to determine whether the following statement is true: If every function $F : P \to P$ is a homomorphism from $(P, \leq)$ to $(P, \leq)$, with $\leq$ an arbitrary order, then $|P| = 1$. ...
lafinur's user avatar
  • 3,322
0 votes
0 answers
18 views

Hasse Diagram multiple choice. Upper/lower bound and maximal/minimal.

Hi, this is one of the questions from my Discrete Mathematics exam that I got wrong. I believe I answered 2 since I did not see the "not" in the question. Which of the following statements ...
Jacob's user avatar
  • 11
1 vote
0 answers
50 views

Complete a total ordered abstract set

Given a total ordered abstract set $(S,\preceq)$. The set is said to be complete if any non-empty subset that is bounded from above/below has a supremum/infimum. Given a $(S,\preceq)$ may not be ...
William Wang's user avatar
2 votes
1 answer
32 views

How to frame the dual statement in a lattice ordered set or an algebraic lattice in general

I am learning the theory of posets and lattices which will eventually lead to Boolean Algebra. I am stuck with the proper understanding of the concept of duality. Followings are what I have gathered ...
Subhajit Paul's user avatar
1 vote
1 answer
33 views

Definition of 2-chain in Posets

The definition of a 2-chain comes from Fayer's paper at: https://qmro.qmul.ac.uk/xmlui/bitstream/handle/123456789/64468/Fayers%202-chains%3A%20an%20interesting%202020%20Accepted.pdf?sequence=2&...
Haimu Wang's user avatar
0 votes
1 answer
33 views

Weaker notion of topological ordering for directed graphs

Let $G = (V,E)$ be a directed graph with $v \rightarrow w$ denoting an edge from $v$ to $w$. Now if $\le$ is a total order on $V$ then $\le$ is called topological order of $G$ if $v \rightarrow w$ ...
MKR's user avatar
  • 204
1 vote
1 answer
73 views

Example where r.v. $X_2$ stochastically dominates $X_1$ but $P(X_1 > X_2) \geq 0.95$

The problem is from a textbook I'm reading, but even with the hint, I'm not being able to come up with a solution. Let $X_1$ and $X_2$ be two random variables with CDFs $F_1$ and $F_2$. We say $X_2$ ...
akm's user avatar
  • 374
1 vote
0 answers
33 views

Does this poset property have a name?

I have a poset with the following property: For any infinite descending chain $x_1 > x_2 > \dots$ and any $y$ that is a lower bound for the chain ($y < x_i$ for all indices $i$), there ...
GMB's user avatar
  • 4,186
6 votes
1 answer
177 views

Do all infinite posets contain an isomorphic proper subposet.

Given an infinite poset $P$, does it always contain a proper subposet $Q \subsetneq P$ such that $P$ and $Q$ are isomorphic as posets? What motivated this question is the following. It can be seen ...
tamionv's user avatar
  • 63
0 votes
0 answers
42 views

Proof of non-isomorphic orders

Task: Let $A = \{(n, k) ∈ N × N : k \leq n\}$ and $B = \{(n, k) ∈ N × N : n \leq k\}$. Consider the restriction of the lexicographic order $N ×_{lex} N $to these sets: a pair $(n_1, k_1)$ is less than ...
Minnefirospex's user avatar
0 votes
2 answers
120 views

Does $\mathcal{P}(\mathbb{N})$ contain an uncountable antichain?

I was given the following question on my homework: Given a set $B$, a subset $\mathcal{A}$ of $\mathcal{P}(B)$ is called an antichain if no element of $\mathcal{A}$ is a subset of any other element of ...
robert lewison's user avatar
2 votes
0 answers
55 views

The subspace topology of $Y_u$($Y$ with upper topology) is strictly coarser than the one induced from $X$?

Let $(X,\leqslant )$ be a poset, we define the upper topology has the principle upper sets, that is upper sets of the form $\left \{ \uparrow x:x\in P\right \} $, as the subbase. We can define ...
Peter's user avatar
  • 31
1 vote
1 answer
43 views

Embedding a Countable Linear Order into Q: How to use the Axiom of Choice

I have a question about the rigorous justification of how to construct an embedding of a countable Linear Order into Q. In brief, where/how is the Axiom of Choice applied in this construction? More ...
Cassius12's user avatar
  • 407
2 votes
0 answers
35 views

Number of partial orders such that a given function is monotone (order homomorphism)?

Given a set $X$, a poset $(Y, \preceq)$, and an arbitrary function $f: X \to Y$, how many partial orders $\le$ can one construct on $X$ such that $f$ becomes an order homomorphism $(X, \le) \to (Y, \...
hasManyStupidQuestions's user avatar
1 vote
1 answer
121 views

Partial orders and isomorphisms

Task: An element of order is called distant if it is greater than an infinite number of limit elements and less than an infinite number of limit elements. a) Prove that with isomorphism of orders, ...
Little Mandelbrot's user avatar
4 votes
2 answers
108 views

Non-isomorphisms of orders

Task: Let A = $\{ (x, y) \in \mathbb{N} \times \mathbb{N} : x ⩾ y \}$ and B = $\{ (x, y) \in \mathbb{N} \times \mathbb{N} : x ⩽ y\}$ . Consider the restriction of the lexicographic order $\mathbb{N} \...
Jacobs Monarch's user avatar
2 votes
0 answers
136 views

Partial orders and antichains

Task: Let $(P, ⩽_{1} ), (P, ⩽_{2} )$ be such partial orders on one set (nonempty) that the size of the maximum antichain in the first is $k_{1}$ , in the second is $k_{2}$ . Is it true that the size ...
Jacobs Monarch's user avatar
1 vote
1 answer
191 views

Antichains and chains in partial orders

Task: Give an example of a partial order in which there are exactly two antichains of size 10, and these antichains do not intersect; and there are exactly 100 chains of size 3 (the size of the chain ...
Little Mandelbrot's user avatar
2 votes
0 answers
70 views

Abelian subgroups of order automorphism group $({\rm Aut}(\mathbb R,\le), \circ )$

I am searching for any results regarding Abelian subgroups of $({\rm Aut}(\mathbb R,\le), \circ )$, the order automorphism group of $\mathbb R$ (order automorphisms of $\mathbb R$ with the composition ...
Crispost's user avatar
  • 169
0 votes
1 answer
34 views

Positive semidefinite inequality: $(AXA^T)^+ \geq (AXA^T + Y)^{-1}$ on $\textrm{Im}(A)$

I asked a question earlier but it wasn't quite correctly stated, so I'll reset. Let $A$ be an $n\times n$ matrix of rank $k<n$ and let $X,Y$ be two symmetric positive definite matrices. Let $Z^+$ ...
Moya's user avatar
  • 5,258
5 votes
1 answer
109 views

Strict order and adjacent elements

Task: Prove that there is no strict order on 14 elements in which there are exactly 50 pairs of adjacent elements. Some clarifications: Elements x, y of order (X, <) are adjacent if x < y and ...
Jacobs Monarch's user avatar
2 votes
0 answers
81 views

Strict partial order and strict linear order

Task : A binary relation on a set of 7 elements contains exactly 20 pairs. Could it be : a) a strict partial order relation? b) a relation of strict linear order? In strict linear order, any pair of ...
Jacobs Monarch's user avatar
2 votes
1 answer
65 views

Number of orderings of a binary tree such that parent comes before children

I am currently making a research project on ILP based optimal unpacking of CHs and can not figure out a specific question. To compare my approach, I would like to know the total amount of possible ...
Florian Bauer's user avatar
0 votes
1 answer
75 views

Equivalence of existence of upper bound for totally ordered subset and increasing sequence.

Let $(X, \leq)$ be an ordered set. I would like to know if the following two conditions are equivalent: Every totally ordered subset of $X$ has an upper bound. Every increasing sequence of $X$ has an ...
ZENG's user avatar
  • 845
1 vote
1 answer
45 views

If the direct product of two semilattices exists, what does its Hasse diagram look like in terms of its constituent semilattice Hasse diagrams?

This is likely to be a quick question. Definition: A semilattice $(L,\lor)$ is a commutative, idempotent semigroup. The Hasse diagram $H$ of $L$ is with respect to the order $x\le y$ iff $x\lor y=y$....
Shaun's user avatar
  • 45.1k
1 vote
1 answer
56 views

What can we say about Green's relations on a semilattice?

Note: This is a soft-question in the flavour of, say, "what does $X$ look like?" and "Is there a description of $Y$?" - so, hopefully, it is not too broad. Let's focus on the ...
Shaun's user avatar
  • 45.1k

1
2 3 4 5
85