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
0 answers
35 views

Clarification on Field Homomorphisms

Let $F, k$ be ordered fields. It is clear that a homomorphism $\phi : F \to k$ satisfies the properties of a ring homomorphisms, that is, preserving operations and multiplicative identity. But is it ...
n1lp0tence's user avatar
1 vote
1 answer
39 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\...
user146125's user avatar
3 votes
0 answers
61 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|=ω .) ...
Rafael's user avatar
  • 31
-3 votes
0 answers
21 views

Question about totally ordered sets and upperbounds [closed]

Let $A$ and $B$ be sets. Let $X$ be a set containing subsets of $B$ such that for each subset in $X$, say $X^{'}$, there is an injective map from $X^{'}$ to $A$. If $Y$ is a totally ordered subset of $...
Fraser Pye's user avatar
1 vote
1 answer
76 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 ...
user146125's user avatar
-2 votes
0 answers
30 views

Mobius Function- Inverse Mobius Function [closed]

Can anyone prove this by induction ? Thanks
Cẩm Ngọc's user avatar
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 \...
Paul Tanenbaum's user avatar
3 votes
1 answer
15 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 ...
Vezen BU's user avatar
  • 2,150
1 vote
3 answers
104 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 ...
Seth's user avatar
  • 3,565
0 votes
0 answers
34 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,...
Arian's user avatar
  • 1
0 votes
1 answer
45 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 ...
safsom's user avatar
  • 437
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 ...
Iian Smythe's user avatar
  • 1,307
2 votes
0 answers
49 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 ...
BCS's user avatar
  • 663
0 votes
0 answers
19 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 \...
user8469759's user avatar
  • 5,307
1 vote
0 answers
38 views

Is there a name for this set order? [closed]

Given $A, B\subseteq \mathbb{R}$ with $A\neq B$, what is it called if $\inf A\geq \sup B$? My first instinct is to call it "set dominance" but that terminology is already used in graph ...
tsm's user avatar
  • 582
2 votes
0 answers
54 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 ...
Jan's user avatar
  • 187
1 vote
1 answer
48 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 ...
azimut's user avatar
  • 23k
0 votes
1 answer
35 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 ...
Hans Brecker's user avatar
1 vote
0 answers
58 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&...
georgy_dunaev's user avatar
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 ...
kirky49's user avatar
  • 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 ...
User's user avatar
  • 23
1 vote
0 answers
45 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 ...
User's user avatar
  • 23
12 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.' ...
Spyridon Manolidis's user avatar
0 votes
0 answers
50 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 - ...
Dave's user avatar
  • 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{\...
Bubaya's user avatar
  • 2,244
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 ...
Zoe Allen's user avatar
  • 4,804
0 votes
0 answers
31 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 &...
Dave's user avatar
  • 13
0 votes
1 answer
25 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&...
Dave's user avatar
  • 13
1 vote
1 answer
80 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 ...
yummy's user avatar
  • 338
0 votes
1 answer
27 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 ...
hillard28's user avatar
1 vote
1 answer
53 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*...
user9871234's user avatar
1 vote
1 answer
76 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
2 votes
0 answers
72 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
3 votes
1 answer
97 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,460
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 - ...
Dave's user avatar
  • 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 ...
Carinha logo ali's user avatar
7 votes
0 answers
140 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
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 $|\...
lelouch_l8r4's user avatar
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$...
eitan.sh21's user avatar
0 votes
1 answer
62 views

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

I recently encountered the following question on an exam, and I struggled to solve it. I hope to get some insight here. Question: Is the ordered set of rational numbers $\langle \mathbb{Q}, < \...
eitan.sh21's user avatar
4 votes
0 answers
53 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
51 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,460
4 votes
1 answer
81 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,340
0 votes
0 answers
31 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
  • 414
1 vote
1 answer
78 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
  • 375
2 votes
0 answers
61 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
  • 569
0 votes
0 answers
25 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
  • 17k
1 vote
1 answer
50 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
  • 23k
2 votes
1 answer
49 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
  • 23k
2 votes
1 answer
51 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

1
2 3 4 5
86