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
votes
0answers
23 views

What would this Hasse diagram look like?

Example 8.5.11 in Discrete Mathematics with Applications 5th Edition (Epps) shows finding a topological sorting for a set on the divides relation. (The complete example is shown below) My question : ...
0
votes
0answers
11 views

implications of pairs of elements generating Boolean subalgebras

I've read about two results which "are well-known", but I haven't found a proof and I haven't been able to prove them by myself yet. So I'd be thankful if someone could give me a hint where ...
0
votes
0answers
11 views

Relationship between two definitions of being a boolean subalgebra

I've come across two different definitions for subsets to be Boolean, so I'd appreciate if one could tell me if and how these are related: We call an orthocomplemented partially ordered set Boolean, ...
0
votes
0answers
15 views

relation between commutativity in orthocomplemented lattices and orthomodular posets

I'm confused about the definitions of elements to commute in orthomodular lattices and in orthomodular posets: In an orthocomplemented lattice $X$ we say that $x \in X$ commutes with $y \in X$ iff $x ...
0
votes
0answers
10 views

equivalent condition for elements of orthomodular posets to commute

I've been learning about orthomodular posets and thereby I've come across the statement that it is well-known tht in every orthomodular poset $L$ the condition that $a \in L$ commutes with $b \in L$ (...
2
votes
1answer
37 views

For every poset $(X,\le)$ there is a linear order $\preceq$ on $X$ which extends $\le$

Use the Compactness Theorem in order to show that for every partially ordered set $(X,\le)$ there is a linear order $\preceq$ on $X$ which extends $\le$, that is: for all $x,y\in X$ we have $x\le y \...
2
votes
2answers
55 views

Explicit map from countable subset of $[0,1]\subset\mathbb{R}$ to $[0,1]\subset\mathbb{Q}$

Let $A\subsetneq[0,1]$ be some countable set of real numbers. Since the rationals are dense in the reals and since all countable linear orders are embeddable into $\mathbb{Q}$, it seems to me that ...
2
votes
2answers
91 views

When does downward closure commute with supremum?

Let $A$ be a suplattices, and suppose we have a family $\{a_i\}_{i\in I}\subseteq A.$ Is $\bigcup_{i\in I}(\operatorname{\downarrow}a_i) = \operatorname{\downarrow} \sup_{i\in I}(a_i)$ in general? ...
1
vote
0answers
37 views
+50

Can every 2 player game be represented as a sum of rock-paper-scissors games and seed games?

I'm currently trying to formulate the following sentence rigorously: "Given any deterministic two player game (a game such that if two players play multiple times, the result is the same every ...
1
vote
1answer
47 views

Equivalent definitions for trees (as partial orders)

Definition. A tree is a partial order $(T,\le)$ which has a least element, and is such that for every $x\in T$, the set $$ \downarrow(x):=\{y\in T\mid y\le x\}$$ is well-ordered by the relation $\le$. ...
0
votes
1answer
15 views

Property of a semiring equipped with partial order relation

Let $R$ be a multiplicatively idempotent semiring with additive identity, and a partial order relation $\leq$ is defined on $R$. Then, for all $x$ in $R$, does the identity $x+2x=2x$ implies $x\leq ...
3
votes
1answer
32 views

Bounded subsets of uncoutable totally ordered set

As my username might possibly suggest, set theory and logic is not really an area of mathematics I know much about. But, there is this statement and apparent proof I was able to come up with, both of ...
0
votes
0answers
19 views

Metric in ordered space: clarifications?

As you surely know, a metric is a function that respects the three well known principles: identity of indiscernibles symmetry triangle inequality I now consider a totally ordered space S such as the ...
0
votes
2answers
56 views

What does being smaller that to a join means in a distributive lattice?

This is a follow up question to my previous question with more restrictions. It was answered negatively for arbitrary lattices, but mentioned that the result holds "only" in distributive ...
2
votes
1answer
39 views

What does being smaller that to a join means in a lattice?

This sounds like a very naïve question, but I couldn't find a correct argument to prove/disprove it rigorously. Suppose we have a a subset $A$ of a lattice (or any join-semilattice), and some $x\le\...
4
votes
1answer
63 views

Right adjoint of the inclusion of preorders into small categories

Let $\mathrm{Pre}$ denote the category of preorders, and $\mathrm{Cat}$ the category of small categories. Since every preorder is a category, and monotone map of preorders is a functor, we have the ...
1
vote
0answers
27 views

A total order on the set of all random variables [closed]

Consider the standard probability space on the reals, and let $\preceq$ be a total order on the set of all random variables $X$ on this space. That is, for any random variables $X$ and $Y$: 1: $X\...
2
votes
2answers
52 views

An equivalent condition for distributivity of a lattice

Let $(L,\land,\lor)$ be a lattice. Show that $L$ is distributive if and only if for all $x,y,z \in L$ holds $$(x \land y) \lor (x \land z) \lor (y \land z) = (x \lor y) \land (x \lor z) \land (y \lor ...
1
vote
1answer
72 views

Prove that the transitive closure of the relation $R \subseteq \mathcal{P(\mathbb{N})} \times \mathcal{P(\mathbb{N})}$ is a partial order

Consider the relation $R \subseteq \mathcal{P(\mathbb{N})} \times \mathcal{P(\mathbb{N})}$ where, for any $X \subseteq \mathbb{N}$ and $Y \subseteq \mathbb{N}$, $(X,Y) \in R$ if and only if there ...
0
votes
0answers
15 views

what does $1/n$ times the expected number of edges per vertex in a finite poset on $n$ points approach as $n$ goes to infinity?

Let $S_n$ be a maximal set of inequivalent posets on $n$ points (i.e., one with maximum possible cardinality). Let $E_n$ be the total number of edges in $S_n.$ Clearly $|S_n|$ and $|E_n|$ depend only ...
5
votes
1answer
134 views

A natural choice of 'maximal ordered subfield' of a field?

For any field $K$ of characteristic zero, its prime subfield $Q(K)$ has a natural ordering inherited from $\mathbb{Q}$. I am interested in finding out to what extent (if at all) this natural ordering ...
0
votes
1answer
59 views

Uniquely orderable subfields of $\mathbb{Q}_p$?

I have heard that, unlike $\mathbb{R}$, the field $\mathbb{Q}_p$ cannot be realised an ordered field. Is there any way to extend the natural ordering on $\mathbb{Q}$ to a larger subfield of $\mathbb{Q}...
6
votes
2answers
182 views

Are $\mathbb{R}$ and $\mathbb{Q}$ the only subfields of $\mathbb{C}$ with natural structure as ordered fields?

We know that $\mathbb{R}$ and $\mathbb{Q}$ have a unique structure as ordered fields with the usual order, and that $\mathbb{C}$ cannot be realised as an ordered field. Various non-trivial subfields ...
1
vote
1answer
29 views

Is the biconditional possible for this statement (instead of just a conditional)?

In one of the assignment of the "Introduction to Mathematical Thinking" course by professor Keith Devlin on Coursera, this statement was shown to be true: $\forall x \forall y \, [(x \leq y) ...
-2
votes
0answers
31 views

Show $(I(P),\vee,\wedge)$ is modular lattice where $I(P)$ is the set of all ideals in a ring $R$

Let $(P,+,\times)$ be the ring and $I(P)$ the set of all ideals in $R$. For any $I,J \in I(P)$ we define operation $$I\vee J=I+J= \{i+j: i \in I,j\in J \},\qquad I\wedge J=I\cap J$$ Show that $(I(P),\...
1
vote
1answer
41 views

If a field has unique ordering, must its subfields also have unique ordering?

Let $L$ be a field and suppose that there exists a unique total order $\leq$ on $L$ with respect to which $(L,\leq)$ is an ordered field. Now let $K$ be a subfield of $L$. Clearly $K$ is an ordered ...
1
vote
0answers
11 views

Linear Order on Polish spaces

Let $\preceq$ be a linear/total order relation on some set $X$. Clearly, in general we can't find a countable subset $Y \subset X$ such that for all $x \in X$ there exists a $y \in Y$ with $x \preceq ...
1
vote
1answer
47 views

Determine an infinite subset $X \subseteq \mathbb{Z}_{\gt 1}$ such that $S \cap (X \times X)$ is a total order on $X$

Let $R$ be a binary relation on $\mathbb{Z}_{\gt 1}$ such that $xRy \iff y=x^2$. Let $S$ be the transitive closure of $R$. The first problem was to describe $S$. I came up with $S=\{(x,y) \in \mathbb{...
1
vote
1answer
57 views

Why does the back and forth method fail to prove that, for each cardinality, any dense linear order without endpoints is unique up to isomorphism?

First of all I must say I'm not not very knowledgeable about set theory beyond the very basics, so please bear with me if I've made some obvious mistakes in my reasoninig. I've looked at and ...
1
vote
0answers
32 views

How to compute all equivalence classes of weight assignments to the vertices of a poset on n points that sum to m?

Note: the word compute should be emphasized here because the purpose of this question is to request an algorithm that I can implement in C. My current algorithm generates almost all of the weight ...
0
votes
2answers
50 views

About two definitions of a complete lattice. (“Introduction to Set Theory and Topology” by Kazuo Matsuzaka)

I am reading "Introduction to Set Theory and Toplogy" by Kazuo Matsuzaka (in Japanese). In this book, the definition of a complete lattice is the following: Let $M$ be a partially ordered ...
0
votes
0answers
10 views

If the strong min-max propriety holds, must there be a saddle point?

Let $W, Z$ be non-empty sets and $f:W \times Z \to \mathbb{R}$. As per the Weak Min-Max Theorem, we have $$\sup_z \inf_w f(w, z) \le \inf_w \sup_z f(w, z)$$ Now if $(w^*, z^*)$ is a saddle point of $f$...
0
votes
2answers
85 views

Is this partial ordering relation on $\mathbb{N}$ uniquely determined? [closed]

Is there more than one partial ordering $\leq$ on the set of natural numbers $\mathbb N$ such that $$\forall x,y \in \mathbb{N}: [x\leq y \implies x\leq S(y)],$$ where $S$ is the usual successor ...
2
votes
1answer
28 views

General definition of antilexicographic order on arbitrary indexed family of ordered sets

Just & Weese in their "Discovering Modern Set Theory, I The Basics" (1996) defines the lexicographic order on an aribtrary indexed family of ordered sets as follows: Let $(I, \preceq)$ ...
1
vote
0answers
14 views

Proof that Order Sum Addition is Associative

I am trying to work through some basic order theory so as to consolidate my shaky grasp of ordinal arithmetic. My source work "Discovering Modern Set Theory I: The Basics" by Winfried Just ...
0
votes
1answer
41 views

Confusion in the statement of Zorn's Lemma

The statement of Zorn's lemma in the book "Modern methods of mathematical physics: Vol $1$" by Simon and Reed reads as follows: Let $X$ be a nonempty partially ordered set with the property ...
1
vote
0answers
25 views

Prove that $a$ is minimum of $B$ in $R^{-1}$ if and only if $a$ is maximum of $B$ in $R$.

I'm trying to prove the following exercise, but Im a little bit confused: Let $R$ by a partial order in $A$. Let $B \subseteq A$ then it verifies that $a$ is minimum of $B$ in $R^{-1}$ if and only if $...
1
vote
0answers
189 views

What's wrong with this proof that $\mathbb{R}$ cannot be well-ordered?

I'm trying to figure out where I'm going wrong with the following proof that $\mathbb{R}$ cannot be well ordered (and thus, ZFC is inconsistent). It's based off a special case of the Erdős–Dushnik–...
1
vote
2answers
36 views

Is the growth of a function discrete?

The question is related to my previous post. We already know that $\log x\ll x\ll e^x$ as a growth of the function (how fast the function diverges). I wonder if there is a middle function $f$ such ...
3
votes
2answers
91 views

Existence of a non-trivial subgroup related by containment with the rest of subgroups

Let $G$ be a finite group. I am interested in finite groups having a non-trivial subgroup $H$ $(H\neq \{e\}, G$) such that $H' \subseteq H$ or $H \subseteq H'$ for every subgroup $H'\neq H.$ That is, ...
2
votes
2answers
64 views

Uncountable chains in an uncountable partially ordered set

Let $(S,<)$ be a partially ordered set such that $S$ is uncountable and has the property that for all $x\in S$ there exists a $y\in S$ such that $y<x$. Is it always true that $S$ contains an ...
1
vote
1answer
37 views

Existence of Total Order Compatible with Partial Order [duplicate]

I was reading Stong's Cobordism Theory, the following lemma to be precise. In the proof, he gives a total order on the set of non-dyadic partitions with the given partial order After some research, I ...
0
votes
1answer
28 views

Verifying Proof: If $L$ is a poset with a bottom element, and $\exists \sup(S)$ for every subset $S \subset L$, then $L$ is a complete lattice

I am currently working through Kaplansky for self study and was hoping to get some feedback on this proof. I would appreciate comments on clarity and legability as well. Claim: If $L$ is a poset with ...
1
vote
0answers
24 views

Constructive aspects of Dilworth's theorem for a class of finite Young's lattices

Dilworth's theorem partitions posets into the so-called chains and states that a poset of width $k$ requires only $k$ disjoint chains to decompose. It is an existential statement but constructive ...
0
votes
0answers
51 views

Proving $f:\mathbb{N}\to \mathcal{P}\{\mathbb{N}\}$ is order preserving

For $n\in\mathbb{N}$, suppose $p_n$ denote the set of all prime divisors of $n$. Define $f:\mathbb{N}\to \mathcal{P}\{\mathbb{N}\}$ by $f(n)=p_n$ for all $n\in\mathbb{N}$. Show that $f$ is order ...
0
votes
1answer
38 views

Are homomorphic pre-images of partial orders preorders?

Suppose we have a relation $R$ and a function $f$, along with a partial order $P$, such that if $f(x) P f(y)$, then $xRy$. It is easy to see that $R$ must then be a preorder (i.e. a reflexive and ...
0
votes
0answers
11 views

Integer Valued Lexicographically Ordered Matrices

I am interested in getting a better understanding of the matrices in the following set $$X_{m,n,k} = \left\{A =[a_{i,j}] \in \mathbf{N}^{m,n}: \text{ the rows of $A$ are lexicographically ordered and $...
3
votes
0answers
40 views

every collection $F = \{S_1, . . . , S_n\}$ of $n$ sets contains a sub-collection $S \subseteq F$ of at least $\sqrt{n}$ sets which is union-free

A family of sets $S = \{S_1, \ldots, S_m\}$ is union-free if $S_i \cup S_j \neq S_k$ for all $S_i, S_j , S_k \in S$. Show that every collection $F = \{S_1, \ldots , S_n\}$ of $n$ sets contains a sub-...
1
vote
0answers
23 views

Notation to distinguish “indifference” and “drawn from”

I am writing a paper in which I need to denote indifference (with respect to some preference ordering) as well as sampling from a distribution. Unfortunately, both are typically represented using the $...
2
votes
1answer
44 views

Is there a name for this ordinal set mapping?

I have an integer $N$. I am working with the set $\{1,...N\}$ and it's powerset $\mathcal{P}(\{1,...N\})$. I want to use define a function, $f$, on the sets $p\in\mathcal{P}(\{1,...N\})$ which ...

1
2 3 4 5
72