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
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
0
votes
1
answer
63
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}, < \...
- 35
4
votes
0
answers
56
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, ...
- 41
1
vote
1
answer
52
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 ...
- 4,500
4
votes
1
answer
82
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$ ...
- 6,360
0
votes
0
answers
34
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 ...
- 414
1
vote
1
answer
81
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 ...
- 375
2
votes
0
answers
62
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 ...
- 585
0
votes
0
answers
26
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 ...
- 17k
1
vote
1
answer
51
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\...
- 23.1k
2
votes
1
answer
53
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 ...
- 23.1k