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 alegbraic structures.

Filter by
Sorted by
Tagged with
0
votes
1answer
34 views

Which of the following are Hasse Diagrams?

My assumptions are, the first and the last diagrams are Hasse. Can someone please explain which one is a Hasse and why?
1
vote
1answer
96 views

Strict WQOs and Strict WPOs

The Wikipedia article on WQOs does not mention a strict version. I came across a particular relation, which I could only describe as a strict WQO, but I am wondering if my reasoning is correct and if ...
0
votes
2answers
33 views

Endomorphisms of cardinals

Let $\kappa$ be a cardinal. Viewing $\kappa$ as an ordered set, let $\operatorname{End}(\kappa)$ be the set of endomorphisms of $\kappa$: $$ \operatorname{End}(\kappa):=\{\ f:\kappa\to\kappa\ |\ (\...
0
votes
1answer
18 views

Find all maximal elements of B. Also find if they exist, the largest element of B, and the least upper bound of B.

Find all maximal elements of B. Also find if they exist, the largest element of B, and the least upper bound of B, where $R = \{(x, y) \in 2^\mathbb{N}\times2^\mathbb{N}\mid x\subseteq y\}, B = \{...
1
vote
1answer
66 views

How to demonstrate the finite height of a lattice?

I would like to ask you for help with a formal demonstration concerning the finite height of a lattice. My lattice is defined like this: is a lattice of vectors, each with exactly $n$ cells. In each ...
0
votes
1answer
49 views

Equivalence relation on a dense linear order to prove there is a rich model

Let $D$ be a dense linear order with $|D|=\kappa$. Is there a way to define an equivalence relation such that $\forall a,b \in D$ there are $\{c_k : k\in \kappa\}$ s.t. $a<c_k<b$ and $[c_i]\not=[...
1
vote
1answer
64 views

Rudin's definition of an ordered set

In Principles of Mathematical Analysis, Rudin defines an $\textit{order}$ on a set $S$ to be a relation denoted by $<$, with the following two properties: If $x, y \in S$ then one and only one of $...
1
vote
0answers
48 views

Show the relation “$\leq$” on $\mathbb{R}$ is a total order.

How can I show that the partial relation "$\leq$" on $\mathbb{R}$ is a total order. It seems obvious to me, but I cannot argue that. Can you show this result for real numbers? At a first step, ...
0
votes
2answers
65 views

Ordering Complex Numbers

I am currently writing a piece of code that will order complex numbers, however I am not sure how to order them. For example, if I am given the numbers: 6, 3+4i, -4, 1+i and 0, how would these be ...
2
votes
1answer
51 views

Show $\mathbb{N}^{\mathbb{N}}$ with lexicographic ordering has the least upper bound property (any nonempty bounded subset has a supremum).

I need to use this statement in a paper. I believe I've proved it, but I would prefer to simply cite it since the proof is unrelated to the rest of the paper and distracts from the main focus of the ...
0
votes
1answer
20 views

Is it possible to deduce a valid sequence given only a set of pairwise orderings?

I was wondering under what circumstances, given a set of pairwise orderings $S=\{O_1, O_2, \cdots, O_k\}$, what conditions $S$ must satisfy (given $n$ total elements) before the ordering determined is ...
0
votes
0answers
34 views

Prove that Multiset and relation $\preccurlyeq$ is a lattice ($\preccurlyeq$ is defined like $\leq$)

Multiset is a set that can have more than one of each member for example $\{1,3,3,9\}$ is a Multiset. Let $\mathbb{K}$ be the set of all multisets that has exactly $k$ members. ($k$ is a fixed ...
2
votes
1answer
37 views

Representations of non-distributive lattices

So, there are various theorems that show that you can represent a distributive lattice as some sort of lattice of sets (birkhoff, stone, priestley etc). Are there any theorems that provide ...
1
vote
1answer
49 views

Infinite modular lattices [closed]

A finite lattice $L$ is called modular if and only if its elements satisfy the following modular identity: For all $x,y,z\in L$ such that $x\leq z$, we have $x\vee(y\wedge z)=(x\vee y)\wedge z$. How ...
0
votes
1answer
37 views

Maximal element, I would like a suggestion to be able to prove it

Let $A$ and $B$ be partially ordered sets, and let $f:A\rightarrow B$ be strictly increasing function. Prove that if $b$ is maximal element of $B$ , then each of $f^{-1}( b)$ is a maximal element of $...
-1
votes
2answers
37 views

Give an example of a dense linear ordering [closed]

Can someone give an example of a dense linear ordering. I know what it needs to satisfy, but an example would be great for understanding.
2
votes
0answers
62 views

why is a ring ideal not called a filter

A ring ideal can be characterized by the two rules: $$(a\in I) \wedge (a ~ \textrm{divides} ~ b) \implies b \in I$$ $$ a,b \in I \implies \textrm{gcd}(a,b) \in I$$ (the usual definition states $a,b \...
0
votes
1answer
43 views

Are Index Sets always well ordered?

Are indexing sets always well-ordered? Since if we have an operation on a collection indexed by $\Gamma$, such as a sum $\sum_{\gamma\in\Gamma}a_\gamma$ or Tychonoff product $\prod\{X_\gamma:\gamma\in\...
1
vote
1answer
51 views

Definition: A (linear) order type $\alpha$ being dense in a (linear) order type $\beta$ - resolving a (seeming) contradiction?

I will use $\mathbf{\eta}$ and $\mathbf{\lambda}$ to respectively denote the order types of the rationals and the reals. In the book Linear Orderings, by Joseph Rosenstein (1982), he defines: ...
1
vote
1answer
35 views

Subset of $[n]$ without chain of leangth $5$ is of size $\leq \mathcal 2\Biggr(\binom{n}{(n-1)/2}+\binom{n}{(n-3)/2}\Biggl)$

Suppose $n$ is odd. Let $\mathcal P([n])$ denote the power set of $[n]$, that is, the $2^n$ subsets of $\{1,...,n\}$. We say that a family of sets $\mathcal F\subseteq \mathcal P([n])$ is nice if $\...
1
vote
0answers
30 views

An interesting way of partitioning with inner ordered combinations

Assume $ K $ labeled blocks $ s_1, s_2, \dots, s_K $ ($ s_1 < s_2 < \dots < s_K $) that arrive sequentially and need to be accomodated as they arrive in $ N $ containers (partitions with ...
1
vote
1answer
31 views

Dual Question: Uniqueness of Suprema and Definition of Bounded Set

In my book on elementary real analysis, there is a definition promptly on the third page of the book (in particular, before defining any topological concepts): ''Suppose $S$ is an ordered set and $E \...
0
votes
0answers
29 views

How can I find the connectivity graph of critical points of a function?

I have the following question. Since it is a bit hard to explain just by words, I added a figure. Suppose I know all the critical points of a function, and I would like to reconstruct a simple graph ...
2
votes
1answer
33 views

Number of chains in a symmetric chain decomposition

I need to show that the number of chains of length $n-2k$ in a symmetric chain decomposition of Boolean Lattice $B_n$ is $\binom{n}{k}-\binom{n}{k-1}$. But I have no idea how to do it. I also have a ...
0
votes
0answers
11 views

Spaces of Cones

In Machine Learning applications, Grassmanian and Stiefel Manifolds have exploded in popularity for studying Subspace or Orthonormal Basis valued optimization problems, among other things. I am ...
1
vote
1answer
50 views

Confusion about a definition in Bourbaki Algebra

I am currently reading Bourbaki Algebra and in section 2 of chapter one they define when two ordered sequences are similar as this: Two ordered sequence $(x_i)_{i \in I}$ and $(y_k)_{k \in K}$ are ...
3
votes
1answer
57 views

Do we only need Choice for higher order-statements (Zorn’s lemma as example)?

In this earlier post, I asked why the axiom of choice, which is an axiom in set theory, is used in areas that are not set theory, such as group theory. The answer was that, whenever choice is used, it ...
2
votes
1answer
66 views

Munkres Topology Chapter 1.3 Exercise 15

Does $[0,1] × [0,1]$ in the dictionary order have the least upper bound property? What about $[0,1] × [0,1)$ and $[0,1) × [0,1]$? Since both $[0,1]$ and $[0,1)$ have the least upper bound property, I ...
2
votes
2answers
40 views

Replacing a projective system with one indexed by an ordinal

Consider some complete concrete category where the underlying set of an inverse limit is the inverse limit of underlying sets. Very often, one has an inverse limit $\varprojlim_{n\in\mathbb{N}}(X_n,p_{...
1
vote
1answer
15 views

$P$ — partial preorder. $\theta(P)=\{(x, y)\in A^2 | (x, y) \in P \land (x,x) \in P \}.$ $\theta(P)$ is an equivalence relation: can't see symmetry.

Let $P$ be a partial preorder (which is a reflexive and transitive relation) on an arbitrary set $A$. Consider binary relation $\theta(P)=\{(x, y)\in A^2 | (x, y) \in P \land (x,x) \in P \}.$ My ...
0
votes
0answers
90 views

Equivalent forcing notions

Let $\mathbb{P}=(P,\leq)$ and $\mathbb{Q}=(Q,\leq)$ be forcing notions, i.e. partial order with a smallest element with the property that there are incompatible elements above each element. Let $h:P\...
-2
votes
5answers
142 views

Why doesn't this work as a counterexample to Cantor's diagonal argument?

(I actually thought this up while listening to a lecture on Goedel's [first] Incompleteness Theorem.) A rudimentary presentation of the diagonal argument: (I used the set of all binary sequences, ...
0
votes
2answers
20 views

A linearly ordered set without endpoints such that every closed interval is finite is isomorphic to set of integers.

Suppose $A$ is a linearly ordered set without maximum or minimum and every closed interval is a finite set. I want to show $A$ is isomorphic to the set of integers with the usual order. I know that ...
1
vote
1answer
42 views

Definable subsets of the order type $\mathbf\omega$, without use of paramaters.

Many will surely interpret this as a trivial question but I've found myself stuck on it for a while now. The structures in question are linear orderings and the signature consists of only the symbol $...
1
vote
1answer
20 views

Why are orders formalized by weak inequalities?

Partial orders are formalized by weak inequalities $\geq$ rather than strict ones $>$. We then add an additional axiom which says that $x\geq y\land y\geq x$ implies $x=y$. But it seems to me ...
0
votes
2answers
20 views

Clarification of partial order set definition

Consider the following definition of the set $\mathcal{X}$ where $\mathcal{S}$ is a partially ordered set. $$X\in\mathcal{X} = \{X\subseteq \mathcal{S} : x\in X\text{ and }y\succeq x\text{ imply }y\in ...
1
vote
1answer
48 views

If a poset is $\sigma$-centered, so what can we say about $P\times P$

We say that a poset $P$ is $\sigma$-centered if it can be partitioned into countably-many pieces so that each piece is finite-wise compatible. i.e. it is $\sigma$-centered if there exists a partition ...
1
vote
0answers
27 views

Filters on preordered sets vs filters on partially ordered sets

What is the advantage on defining filters on partially ordered sets versus defining them on preordered sets? Almost everywhere where I have seen filters they have been used in the setting of partially ...
1
vote
1answer
54 views

A partial order on $\mathbb{N}$ that is not total

In the text Modern Real Analysis by Ziemer there is a question that asks to use the "natural partial order" on $\mathcal{P}(\{1,2,3\})$ to obtain a partial order on $\mathbb{N}$. I have scratched my ...
0
votes
1answer
23 views

Question about infimum and supremum in a positive cone

A "lattice cone" $C$ is a cone such that $x\wedge y$ and $ x\vee y$ exist for $x,y\in C$. But how can a positive cone contain both the supremum and the infimum? Since the relation $$x\wedge y=x+y- ...
0
votes
1answer
62 views

Show that every ordered set with the well ordering has the least upper bound property

Here is a proof attempt: Let $S_a =\{x\in A:x \leq a\}$ (also known as a section of $A$). We firstly prove that $\forall a \in A$, $S_a$ has a supremum in $A$. Clearly, every $S_a$ is bounded above ...
0
votes
2answers
20 views

Sup of two ordinals in a limit

I am not sure if this is a dumb question, but if I have a limit ordinal $\xi$, given any two $\alpha,\beta <\xi$, is it possible to find an ordinal $\gamma$ such that $\alpha,\beta\leq\gamma<\...
1
vote
1answer
29 views

Dedekind cut corresponding to the limit of a Cauchy sequence

Let $a : \mathbb{N} \rightarrow \mathbb{Q}$ be a Cauchy sequence of rationals. Then is it correct to say that $$\lim_{n \rightarrow \infty} a_n = \{x \in \mathbb{Q} : \exists n \in \mathbb{N} : \...
0
votes
1answer
43 views

Are there subsets of $\mathbb{Q}$ with a finite number of upper-bounds?

Consider the poset $(\mathbb{Q}, \leq)$. Is there a subset of $\mathbb{Q}$ with a finite number of elements that are upper-bounds? I tried to prove this as follows: Suppose $K \subset \mathbb{Q}$, ...
0
votes
2answers
21 views

example of non order preserving bijection

I read that "the set of integers and the set of rational numbers (with the standard ordering) do not have the same order type, because even though the sets are of the same size (they are both ...
3
votes
4answers
133 views

How can an ordered pair be a set assuming there is no order in a set?

The following propositions, I think, are generally considered as true ( though they may not all have the same level of rigor). (1) In a set there is no order ( due to the extensionality axion) : $\{...
1
vote
1answer
28 views

Cycle notation for cyclic orders

Is there a convenient cycle notation for cyclic orders (https://en.wikipedia.org/wiki/Cyclic_order)? For example: Definition. A set of four elements $a, b, c, d$ of a cyclically ordered set is a 4-...
0
votes
0answers
50 views

Denoting sets (permutations,tuples?),

I'll use and example to explain my question: Example: Let there be two distinct types $a$ and $b$ and each type has equal number of sets. There are two sets of type $a$: $\{1,2\}$ and $\{3,4\}$. ...
0
votes
0answers
34 views

If a relation is neither Symmetric nor Anti-Symmetric, can it still be an order of some kind?

Say I have a relation that is Irreflexive and Transitive, but neither Symmetric nor Anti-Symmetric, can it still be a strict partial and / or strict total ordering? I realise this is an edge case, I ...
1
vote
0answers
58 views

Compatibility with multiplication of a cyclic order on a ring

Considering a linear order on the additive group of a ring is compatible with multiplication if: $a < b \implies ax < bx$ and $xa < xb$ for any positive $x$, we could define compatibility ...