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

Prove that an infinite chain contains either a chain order-isomorphic to the positive integers

Prove that an infinite chain contains either a chain order-isomorphic to the positive integers or a chain order-isomorphic to the negative integers
2
votes
2answers
48 views

Is my proof here correct (basic real analysis/order theory question)?

I'm self-studying real analysis and came across a simple problem I was trying to solve (although I think this is more of an order theory problem): Let $A\subseteq \mathbb{R}$ so that $ε\:>0$ and ...
-2
votes
0answers
36 views

Prove that $f$ leaves some elements of $L$ fixed.

Let $L$ be a complete lattice, and let $f\colon L \to L $ be a function for which $a\leqq b$ implies $f(a)\leqq f(b)$. Prove that $f$ leaves some elements of $L$ fixed.
0
votes
0answers
20 views

Has anyone studied lattices of graphs organized by inclusion?

Suppose we have two directed graphs, A and B, each represented as a set of ordered pairs (x,y) of natural numbers, such that x and y represent vertices and (x,y) represents a directed edge from x to y....
1
vote
2answers
48 views

The notion of minimum in Leinster's book

On p.110 Leinster says that the minimum of $x,y\in \mathbb R$ satisfies $$\min\{x,y\}\le x,\ \min\{x,y\}\le y$$ and whenever $a\in\mathbb R$ satisfies $$a\le x, a\le y,$$ we have $a\le \min\{x,y\}$. ...
0
votes
2answers
30 views

Can a partially ordered set be complete?

I learned the definition a set being complete as below. An ordered set (X, =<) is said to be complete if for every non-empty subset of X which is bounded above (or below), there exists a supremum (...
0
votes
0answers
42 views

When can a total/linear-order be extended to a well-order

The axiom of choice tells us every set can be well-ordered and an easy exercise is that every partial-order can be extended to a linear-order and a linear-order on a set is a well-order iff any of the ...
-1
votes
1answer
28 views

Proving that if a family of sets $\cal{A} \ne \emptyset$ is totally ordered with respect to $\subseteq$ then $\bigcap\cal{A} \in \cal{A}$.

Assume that $\mathcal{A} \neq \emptyset$ is an arbitrary family of subsets of $X$, such that $(\mathcal{A}, \subseteq)$ is a total ordering. I want to prove that the intersection of all members of $\...
2
votes
1answer
41 views

Order topology on $\mathbb{N}$ is discret topology?

Let $\mathbb{N}=\{0,1,2,\dotso\}$ and $(\mathbb{N},<)$ with the usual ordering $<$. Let $\tau_<$ be the order topology with regards to $<$. Then $\tau_<$ is the discrete topology (...
-1
votes
1answer
30 views

Functional analysis, fixed point theory [closed]

In the theory of Riesz spaces, I am unable to understand a point. If $aRb$ and $cRd$ then it is necessarily true that $a+cRb+d$, where $R$ shows partial order relation. If this is not true, please ...
2
votes
1answer
43 views

Problems with proof of $\omega_1=\bigcup\{X_\xi|\xi\in\omega_1\}$

I have the proof of following lemma, which I do not really understand: Let $(X,<)$ be a well orderd uncountable set. Let $\omega_1=\{\xi\in X|X_\xi\,\,\text{countable}\}$ and $X_\xi=\{\alpha\in X|\...
5
votes
0answers
72 views

Summation methods ordered by strength

A summation method is a partial function from scalar sequences to scalars, i.e. an element of the set $\bigcup_{S \subseteq (\mathbb{N} \rightarrow \mathbb{C})} (S \rightarrow \mathbb{C})$. A ...
0
votes
0answers
46 views

Partial ordering with respect to being an initial segment or continuation according to Halmos

There is an exercise in "Naive Set Theory" by Halmos given as (Sec. 17, p. 68): A subset $A$ of a partially ordered set $X$ is cofinal in $X$ in case for each element $x$ of $X$ there exists an ...
0
votes
0answers
17 views

Software for computing mobius function of a poset

Is there any software available (possibly free) for computing mobius function of a finite partially ordered set (poset) and related things? For a definition of mobius function of a poset see this: ...
1
vote
2answers
31 views

Prove that there are $(n-1)!$ possible cyclic orders of $n$ objects

I'd like to prove that there are $(n-1)!$ possible cyclic orders of $n$ objects. I started with a proof by induction, but I am not sure if this is the right way to approach this problem. I showed ...
5
votes
0answers
89 views

Set of Ordinal Functions with singular cofinality

Is there a set $A$ of regular cardinals such that the partial order $(\prod A, <)$ has singular cofinality? Here $\prod A$ is the set of all ordinal functions on $A$ with $f(\kappa)<\kappa$ for ...
0
votes
1answer
26 views

Functions question - solving equation to find value of function [closed]

Let $f : \mathbb{R}\rightarrow\mathbb{R}$ be a function such that $f(0) = 1$ and for any $x$, $y\in\mathbb{R}$, we have: $$f(xy+1) = f(x)f(y) - f(y) - x + 2$$ Find $f(x)$.
2
votes
2answers
76 views

A “complete” ordered field of ordinals

First, a note regarding proper classes: One can construct a tuple of proper classes, for example with the Morse definition. Same goes for proper-class-sized algebraic structures, as in the field of ...
0
votes
1answer
35 views

Defining the Order of the Natural Numbers

Is there a way to give the regular partial order of the natural number directly from their definition through the Infinity Axiom? I have only ever seen the partial order of the natural number to be ...
0
votes
1answer
65 views

When is the maximal element guaranteed by Zorn's Lemma unique? [closed]

Zorn's Lemma states that any poset with the property that every chain has an upper has at least one maximal element. Are there necessary or sufficient conditions on the poset for the maximal element ...
0
votes
0answers
19 views

Length of the largest chain of a poset ordered by set inclusion.

If $E4$ is the set of all equivalence relations on $\{1,2,3,4\}$,and we define a poset as $(E4, \{(R1,R2) \in E4 \times E4 \mid R1 \subseteq R2\})$ then what would be the length of largest chain ...
0
votes
1answer
32 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
95 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
29 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
14 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
38 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
45 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
52 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
46 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
62 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
43 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
16 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
28 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
35 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
45 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
36 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
56 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
40 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
31 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
27 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
30 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
25 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
26 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
10 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
43 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 ...
2
votes
1answer
53 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
60 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
38 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_{...