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
148
votes
2
answers
39k
views
Is there a known well ordering of the reals?
So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $R$ , if every subset has a least element. My ...
- 4,045
71
votes
5
answers
104k
views
What does "curly (curved) less than" sign $\succcurlyeq$ mean?
I am reading Boyd & Vandenberghe's Convex Optimization. The authors use curved greater than or equal to (\succcurlyeq)
$$f(x^*) \succcurlyeq \alpha$$
and curved ...
- 811
65
votes
8
answers
75k
views
Example of Partial Order that's not a Total Order and why?
I'm looking for a simple example of a partial order which is not a total order so that I can grasp the concept and the difference between the two.
An explanation of why the example is a partial ...
- 769
64
votes
1
answer
2k
views
How to find a total order with constrained comparisons
There are $25$ horses with different speeds. My goal is to rank all of them, by using only runs with $5$ horses, and taking partial rankings. How many runs do I need, at minimum, to complete my task?
...
- 355k
57
votes
7
answers
35k
views
difference between maximal element and greatest element
I know that it's very elementary question but I still don't fully understand difference between maximal element and greatest element. If it's possible, please explain to me this difference with some ...
- 1,161
46
votes
6
answers
35k
views
Infimum and supremum of the empty set
Let $E$ be an empty set. Then, $\sup(E) = -\infty$ and $\inf(E)=+\infty$. I thought it is only meaningful to talk about $\inf(E)$ and $\sup(E)$ if $E$ is non-empty and bounded?
Thank you.
- 5,440
44
votes
3
answers
13k
views
Every partial order can be extended to a linear ordering
How do I show that every partial order can be extended to a linear ordering?
I think that I manage to prove that claim for finite set, how can I prove it for infinite set?
Thank you.
- 2,071
40
votes
5
answers
45k
views
A finite set always has a maximum and a minimum.
I am pretty confident that this statement is true. However, I am not sure how to prove it. Any hints/ideas/answers would be appreciated.
- 2,037
32
votes
5
answers
34k
views
What is the difference between max and sup?
I am studying KS (Kolmogorov-Sinai) entropy of order q and it can be defined as
$$
h_q = \sup_P \left(\lim_{m\to\infty}\left(\frac 1 m H_q(m,ε)\right)\right)
$$
Why is it defined as supremum over ...
- 913
31
votes
6
answers
3k
views
Embedding ordinals in $\mathbb{Q}$
All countable ordinals are embeddable in $\mathbb{Q}$.
For "small" countable ordinals, it is simple to do this explicitly.
$\omega$ is trivial, $\omega+1$ can be e.g. done as $\{\frac{n}{n+1}:n\in \...
- 1,610
29
votes
2
answers
5k
views
Why do people accept the axiom of choice given the well ordering principle?
We know without any doubt that the axiom of choice implies (in fact is equivalent to) the well ordering principle.
The well ordering principle can't be true! If we take the open interval $(0,1)$ for ...
- 887
29
votes
2
answers
2k
views
Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?
I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago. Reading the wikipedia article linked above, I ...
- 98.4k
28
votes
6
answers
7k
views
Is the set of real numbers the largest possible totally ordered set?
Because I find any totally ordered set can be "lined up" in a straight line, I'm guessing that the set of all the real numbers is the biggest totally ordered set possible. In the sense that any other ...
- 4,233
28
votes
1
answer
4k
views
What is the order-type of the set of natural numbers, when written in alphabetical order?
We are all familiar with the standard nomenclature for the smallish
natural numbers, such as
one, two, three, ..., one hundred, one hundred one, ..., fifteen
thousand two hundred forty-nine.
I ...
- 44.4k
26
votes
4
answers
29k
views
what is total order - explanation please
sorry for the dumbest question ever, but i want to understand total order in an intuitive way,
this is the defition of total order:
i) If $a ≤ b$ and $b ≤ a$ then $a = b$ (antisymmetry);
ii) If $a ≤...
- 3,720