Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
36 views

Infinite modular lattices

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 ...
2
votes
2answers
172 views

minimal embeddings of topological spaces into connected spaces

Defintions: Let $X$ be a topological space. 1) A connected space $Y$ is a minimal connected ambient (m.c.a for short) space for $X$ if there exists an embedding $i:X\mapsto Y$, and for every ...
1
vote
1answer
40 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 $...
0
votes
1answer
37 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
49 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: ...
0
votes
1answer
29 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
30 views

Give an example of a dense linear ordering [on hold]

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
49 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 \...
1
vote
1answer
30 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 $\...
-2
votes
0answers
38 views

What are some mathematical functions that are NOT commutative? [closed]

I'm searching for any and all functions whose result from an operation on a given set of positive integers is dependent on the ordering of the set. For instance using the sets; a, b, c, d b, a, c, d ...
1
vote
0answers
25 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
0answers
50 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 ...
0
votes
1answer
24 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
1answer
46 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
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
24 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
9 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 ...
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 ...
1
vote
1answer
36 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
0answers
84 views

Showing equality of 2 suprema in complete lattice

Let $(M,+,0)$ be a naturally ordered commutative monoid (i.e. such that the natural preorder is antisymmetric) such that $(M,\sqsubseteq)$ is a complete lattice. Then $(M,\sum^*)$ is a summation ...
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
2answers
37 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_{...
-2
votes
5answers
123 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, ...
1
vote
1answer
14 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
36 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\...
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
17 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
19 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
43 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 ...
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- ...
1
vote
0answers
23 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
50 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 ...
1
vote
0answers
77 views

Quadrants of a cyclically ordered group

I am trying to prove that if there are two different positive elements in a non-linearly cyclically ordered group, then every quadrant of the group is not empty. Is this a correct statement? ...
1
vote
0answers
204 views

Positive and negative elements of a cyclically ordered group

I am trying to prove A property of a cyclic order on a ring. In order to do it, I need the last two properties (lemmas 1.11 and 1.12) in this question. I separated them from the original theorem ...
22
votes
6answers
5k 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 ...
0
votes
1answer
41 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
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
26 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
0answers
68 views

Injective order preserving homomorphism $\phi$ of two ordered abelian groups satisfies $a<b\iff \phi(a)<\phi(b)$.

Exercise: Prove that every injective order preserving homomorphism $\phi$ of two ordered abelian groups satisfies $a < b \iff \phi(a) < \phi(b)$. Definition: A homomorphism $\phi \colon G ...
0
votes
2answers
19 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 ...
1
vote
0answers
131 views

Apex of a cyclically ordered group

Does it make sense to introduce the new definition? Definition 2.1. An element $\pi$ of a cyclically ordered group is an apex of the group iff $\pi = - \pi \ne 0$. Considering an element $x$ of a ...
3
votes
4answers
128 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
0answers
121 views

A property of a cyclic order on a ring

Is this property correct? If yes, is there a better way to prove it? If not, what would be an example of a ring that does not satisfy the condition? Theorem. In a ring with non-linearly cyclically ...
1
vote
1answer
26 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
48 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\}$. ...
1
vote
0answers
65 views

Natural cut of a cyclically ordered group

It is well known that a cyclically ordered set may have more than one cut. I am trying to prove that a cyclically ordered group cannot have more than one cut compatible with the group operation. Is ...
4
votes
0answers
78 views

Classifying the chains of orderable sets' power sets up to isomorphism

Recently, while trying to understand another result, I began to wonder about the following question: Given some orderable set $A,$ what (if anything) can we conclude about the order type or ...
1
vote
1answer
69 views

Problem on distributive lattice

As William Elliot noted, the initial statement was false. I changed it to a weaker one. Let $L$ be a distributive lattice, denote $lu(x)$ - a least upper bound of elements which cover $x$ (to be ...
0
votes
0answers
32 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 ...
11
votes
0answers
308 views

Order-preserving map of regressive functions on $\omega_1$

This questions has now been published in a journal, see update at the bottom. I posted the following question in March 2014 on MO. It did receive some attention, but the answer there remains ...