Skip to main content

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
0 votes
1 answer
23 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\}\} \end{gather*} obeys \begin{gather*} ...
user9871234's user avatar
1 vote
1 answer
58 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 ...
Manuel Bonanno's user avatar
0 votes
0 answers
21 views

Question about connected relation and trichotomy

I’ve been reading about ordered relations and I came across this definition of strict total order on Wikipedia. I looked at the Wikipedia article on the connected relation and found this: I’ve read ...
Dr. J's user avatar
  • 73
2 votes
0 answers
60 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. ...
lelouch_l8r4's user avatar
2 votes
1 answer
67 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. ...
PatrickR's user avatar
  • 4,361
1 vote
0 answers
32 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 - ...
Dave's user avatar
  • 11
0 votes
0 answers
19 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 ...
Carinha logo ali's user avatar
7 votes
0 answers
126 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 ...
Lucina's user avatar
  • 647
3 votes
2 answers
108 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 $|\...
lelouch_l8r4's user avatar
0 votes
1 answer
51 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$...
eitan.sh21's user avatar
-1 votes
1 answer
46 views

Does $\langle\mathbb{Q},<\rangle\cong\langle\mathbb{Q}\times\{{1,0}\},<_{lex}\rangle$? [closed]

I had an exam today with this question and unfortunately I didn't solve it. Does $\langle\mathbb{Q},<\rangle\cong\langle\mathbb{Q}\times\{{1,0}\},<_{lex}\rangle$ order-isomorphic?
eitan.sh21's user avatar
4 votes
0 answers
48 views

Prove for a monotone, continuous, and rational preference relation $\succsim$ on $X=\mathbb{R}^L_+$, $y\geq x$ implies $y\succsim x$.

I need to prove the following result: For a monotone, continuous, complete, and transitive preference relation $\succsim$ on $X=\mathbb{R}^L_+$, $y\geq x$ implies $y\succsim x$. I tried it myself, ...
Champa's user avatar
  • 41
1 vote
1 answer
38 views

Every second countable LOTS is embeddable in $\mathbb R$

I'd like to prove the following (Engelking, exercise 6.3.2(c)). Theorem: Every second countable LOTS is embeddable in $\mathbb R$. Here, LOTS = linearly ordered topological space. "Embeddable ...
PatrickR's user avatar
  • 4,361
4 votes
1 answer
76 views

Induction does not preserve ordering between cardinality of sets?

Consider building a binary tree and consider it as a collection of points and edges. Here is one with five levels, numbered level $1$ at the top with $1$ node to level $5$ at the bottom with $16$ ...
jdods's user avatar
  • 6,310
0 votes
0 answers
27 views

Definition for orders corresponding to directed acyclic graphs (DAG)

My question What is the name for a binary relation $R$ on $V$ that corresponds to a graph $G = (V,E)$ that is a directed acyclic (simple) graph? Background There is a bijection between simple directed ...
Berber's user avatar
  • 394
1 vote
1 answer
70 views

Any subset of a well-ordered set is isomorphic to an initial segment of this well-ordered set.

I wanted to prove the fact for which I have a sketch of proof: Let $(W,\leq )$ be a well-ordered set and $U$ be a subset of $W$. Then considering the restriction of $\leq $ to $U\times U$, we have ...
boyler's user avatar
  • 345
2 votes
0 answers
59 views

Ordering complex numbers compatible with the product

I'm looking for a total order relation in $\mathbb C$ that is compatible with the product but not necessarily with the sum. I haven't been able to find one! Of course, we know that there doesn't ...
Noname's user avatar
  • 517
0 votes
0 answers
24 views

Maximal elements of set with respect to partial order on $\mathbb{N}_0^2$

I might ask a trivial question, but it's been confusing me a bit. Suppose $(P,\leq)$ is a partially ordered set, and let $S=\{p_1,\dots,p_n\}\subset P$. Am I right to define $\max(S)$ - the set of ...
RFZ's user avatar
  • 16.9k
1 vote
1 answer
45 views

Alternative characterization of distributive lattice

Let $(X,{\leq},{\wedge},{\vee})$ be a lattice. The lattice is called distributive if for all $x,y,z\in X$ both distributive laws hold: $$ x \wedge (y \vee z) = (x \wedge z) \vee (y \wedge z) \quad\...
azimut's user avatar
  • 22.8k
2 votes
1 answer
37 views

Möbius function of distributive lattice only takes values $\pm 1$ and $0$.

In this Wikipedia article, I found the statement [...] shares some properties with distributive lattices: for example, its Möbius function takes on only values 0, 1, −1. My question is: How it can ...
azimut's user avatar
  • 22.8k
2 votes
1 answer
44 views

Is the product of a reversible lattice and a non-reversible lattice non-reversible?

I was messing around with lattice structures when I thought of this problem: Let $L$ be a (bounded) lattice. $L$ is called reversible if there is a lattice isomorphism from $L$ to $L^c$ ($L^c$ being ...
kabel abel's user avatar
2 votes
0 answers
78 views

Minimum information to order integers based on prime factorization without a priori knowing the order.

Suppose I give you the set $S$ that contains the integers $2$-$n$ but I have obscured it somehow so that you don’t know the true identity of S and you can’t discern the numeric notion of magnitude of ...
tyobrien's user avatar
  • 3,521
-3 votes
1 answer
51 views

Prove that the order type of $\alpha\cdot\beta$ is the antilexicographic order in $\alpha\times\beta$. [closed]

This question is related to this one, but not a duplicate, since I am struggling with injectivity and monotonicity, rather than proving that $\{\alpha\cdot\eta + \xi:\eta<\beta\textrm{ and }\xi<\...
Antonio Maria Di Mauro's user avatar
3 votes
1 answer
37 views

Is there an Archimedean Dedekind-complete ordered division ring of characteristic zero that is non-isomorphic to the real line?

I know an Archimedean Dedekind-complete ordered field of characteristic $0$ must be isomorphic to $\mathbb{R}$. My question is what if I start from an ordered division ring? Would it still be ...
user760's user avatar
  • 1,422
0 votes
0 answers
27 views

Well-founded Relation on infinite DAGs

A well-founded relation on set $X$ is a binary relation $R$ such that for all non-empty $S \subseteq X$ $$\exists m \in S\colon \forall s \in S\colon \neg(s\;R\;m).$$ A relation is well-founded when ...
MB7800's user avatar
  • 51
0 votes
0 answers
19 views

Show arbitrary intersection of partial orders is a uniquely determined partial order

Let $\mathcal{A}$ be a relation defined on set $X$, and let $\Omega(\mathcal{A})$ be the set of all supersets of $\mathcal{A}$ that are partial orders. Define $$P(\mathcal{A})=\bigcap_{\mathcal{B}\in\...
Asi Cruz's user avatar
  • 103
2 votes
1 answer
25 views

The join of two set partitions in the refinement order

Let $X$ be a set. The set $\Pi_X$ of all partitions of $X$ is partially ordered via the refinement order, which is defined by $\alpha \leq \beta$ if and only if for each block $A\in \alpha$ there is a ...
azimut's user avatar
  • 22.8k
0 votes
0 answers
21 views

Szekeres example 1.5 errata?

In Peter Szekeres's text "A Course in Modern Mathematical Physics", example 1.5 (dealing with partial orders) says: The power set $2^S$ of a set $S$ is partially ordered by the relation of ...
MattHusz's user avatar
  • 173
0 votes
1 answer
32 views

Reconstructing a closure operator from a set of fixed points

Let $L$ be a lattice, not necessarily complete. We define a closure operator as a function $f\colon L\to L$ which is: idempotent, $f(f(x)) = f(x)$, isotone, $x\leq y \Rightarrow f(x) \leq f(y)$, ...
Jakim's user avatar
  • 386
4 votes
0 answers
72 views

Zorn's lemma: counterexample to chain with upper bound?

The premise required for invoking Zorn's lemma is that every chain in $X$ have an upper bound. So that makes me wonder: what is a good example of a poset $X$ for which that property is false? That is ...
Hank's user avatar
  • 131
7 votes
3 answers
667 views

Is every continuum-sized dense subset of the irrationals order isomorphic to the irrationals?

This is a strengthening of a question another user asked, here: Are irrational numbers order-isomorphic to real transcendental numbers?. In the answer to that question, it was stated that the ...
user107952's user avatar
  • 20.9k
1 vote
1 answer
120 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 ...
lelouch_l8r4's user avatar
1 vote
1 answer
53 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
  • 1,293
6 votes
2 answers
164 views

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,050
0 votes
0 answers
17 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
  • 47
0 votes
0 answers
62 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
  • 1,293
0 votes
0 answers
36 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
18 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
10 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
69 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
1 answer
24 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
  • 439
0 votes
0 answers
38 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
47 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
79 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,361
4 votes
1 answer
54 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 ...
lelouch_l8r4's user avatar
5 votes
2 answers
156 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
186 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
34 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
57 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

1
2 3 4 5
86