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.

learn more… | top users | synonyms

1
vote
2answers
45 views

Is there an (order-theoretic) version of bijectivity? But appropriate for lower adjoints.

Let $f : X \rightarrow Y$ denote a function. Then the following are equivalent. ($f$ is an isomorphism) There exists a function $g : Y \rightarrow X$ such that $$\forall x \in X, y \in Y \;\;\; f(x) ...
19
votes
4answers
7k views

What does “curly (curved) less than” sign $\succcurlyeq$ mean?

I am reading "Convex Optimization" by Stephen Boyd. He is using a curved greater than and curved less than equal to signs. $f(x^*) \succcurlyeq \alpha$ or $f(x*) \preccurlyeq \alpha$ Can someone ...
3
votes
1answer
87 views

Uncountable sets and interval topology

Let be an uncountable well-ordered set $(X,\leq)$. We suppose that exists some $x\in X$ such that $y < x$ for uncountably many values of $y$ and define $x_1$ as the minimum $x\in X$ such that $y &...
2
votes
0answers
133 views

Cones and partial ordering

A positive cone always induces a partial ordering on a vector space. I wonder if the converse holds, so is every partial ordering in a vector space induced by a positive cone, or in other words, is ...
2
votes
1answer
97 views

A well ordering on $\mathbb{R}$ and bigger sets

Consider the set of sequences $S = \{f:\mathbb{N}\to\mathbb{N}\}$, define an order on $S$ by the following: Based on the well-ordering of $\mathbb{N}$ and induction, either $f_1 = f_2$ or there is a ...
3
votes
2answers
919 views

Number of ways to interleave two ordered sequences. [duplicate]

Suppose we have two finite, ordered sequences $x = (x_1,\dots,x_m)$ and $y = (y_1,\dots,y_n)$. How many ways can we create a new sequence of length $m+n$ from $x$ and $y$ so that the order of elements ...
7
votes
1answer
163 views

Order-preserving injections of ordinals into $[0,1]$

The usual "matchstick" representation of an ordinal number can be thought of as an order-preserving injection of that ordinal into the interval [0,1]. For example, here's a representation of $\omega^2$...
3
votes
2answers
133 views

Collection of independent sets equal to downset?

I have been struggling with the following problem. Every set here is supposed to be finite. If we have a closure $\lambda$ on $X$, we define the collection of independent sets of $X$ as $$ I_\lambda ...
11
votes
2answers
219 views

Which of these constructions are left adjoints?

A groupoid can be regarded as a small category in which every arrow is an isomorphism A monoid can be regarded as a small category with only a single object A preorder can be regarded as a small ...
2
votes
1answer
46 views

Likeness of strictly well-ordered sets

The question itself: Given a strictly ordered set $\langle A, < \rangle$ (< merely symbolises some kind of an order in this case) which is dense, with a least and greatest elemnts that are not ...
1
vote
1answer
121 views

Which mathematician has argued that we should move from “set” to “order”?

I recall reading (on this very site, in fact) that there is a mathematician whom argues that we ought to switch from "set" to "order" in the foundations, so as to "recover duality" or some such. Does ...
0
votes
1answer
55 views

Elementary Properties of Order

Need help with this question: Prove: Let $x = a_1, a_2...a_n$, and let $y$ be a product of the same factors, permuted cyclically. (That is, $y = a_k, a_{k+1}...a_na_1...a_{k-1}$. Then $ord(x)=ord(y)$...
1
vote
0answers
54 views

The null set as the underlying set of a relation structure

Can the null-set underly a relation structure? Can it underly a well-order? If so, would such a well-order have order-type $0$? (Can one even have an order-type of $0$?) My motivation for this ...
0
votes
1answer
42 views

Question about sets of well-orderings

I recently posted a question on here about sets of well-orders and isomorphisms between well-orders. I have a related question about order-type-comparison: if $W$ is any set of well-orders, doesn't ...
5
votes
1answer
112 views

Question about sets of well-orders and isomorphisms between well-orders

I was thinking about this problem in trying to better get a feel for and understand well-orders (I'm trying to learn some set theory) - right now, I'm not really hoping for anybody to supply me with a ...
0
votes
1answer
38 views

Could someone check this proof for me?

The problem (and a definition first): The following definition explained Let $U \subseteq \mathbb{N}$. We say that a function $x: \{0,1\}^U\to \{0,1\}$ is a $xor$ on the set $U$ if the following ...
0
votes
2answers
37 views

How many pairwise nonisomorphic dense subsets exist

in the completion of a linear order of cardinality $\kappa$? Can there be more than $\kappa$? To be more precise, suppose $L$ is a linear order of cardinality $\kappa$. Let $\overline L$ denote ...
1
vote
1answer
70 views

Interesting question with ordering integers

The numbers $1,2,3,...,101$ are written down in a row in some order. Is it always possible to cross out $90$ numbers in a way such that all $11$ numbers left will stay either in increasing or in ...
0
votes
1answer
54 views

Proof by contradiction: $c=\max (A) \wedge d=\max (B) \to \max (A \cup B ) \in \{c,d\}$

Let be $A,B \subseteq \Bbb{R}$, with $A \neq \emptyset $ and $B \neq \emptyset$ and $\Bbb{R}$ totally ordered by $\leq$, and $c,d \in \Bbb{R}$, with $c=\max (A)$ and $ d=\max (B)$. I must proof by ...
2
votes
0answers
91 views

Does the Riemann zeta function tell us about the order theoretic properties of the natural numbers?

The classical Möbius function $\mu(n)$ fulfills the multiplicative inversion formula, e.g. see this thread. Now I see in the theory of posets, they generalize the concept of that function, see ...
1
vote
1answer
68 views

What motivates the definition of “Periodic” group action

Consider a group $G$ acting on a set $\Omega$. For example, let $G=\{g\in A(\mathbb R):(\alpha +1)g=\alpha g+1\}$ for all $\alpha\in\mathbb R$, where $A(\mathbb R)$ are the order-preserving ...
1
vote
0answers
52 views

Monoid Ring of a Commutative Cancellative Ordered Monoid

Suppose $M$ is a commutative cancellative monoid with $0$ as the identity and $+$ as the operation, and $M$ is equipped with an order $\preceq$ defined by $$ m \preceq m' \text{ if and only if there ...
1
vote
2answers
94 views

Proving that Order for N is Anti-symmetric

I'm having trouble deriving the following fact from the basic properties of $+_{\mathbb{N}}$ and the definition: Definition. $\forall n, m \in \mathbb{N}: (n \geq m) \leftrightarrow (\exists a \in ...
0
votes
1answer
31 views

Order isomorphic but not Boolean isomorphic

Is there an example of Boolean lattices $(X,\le)$ and $(Y,\le)$ and a function $$f:X\to Y$$ such that for all $x,z\in X$ $$x\le z ~~~~ \leftrightarrow ~~~~f(x)\le f(z) $$ so that for some $a\in X$, $...
5
votes
2answers
126 views

Old exam question about well ordering on $\mathbb{R}$

I am not sure how to start tackling this question and would love a hint: Let $<$ the regular order relation on $\mathbb{R}$, and $<_w$ well ordering on $\mathbb{R}$. We define a coloring ...
2
votes
0answers
85 views

Do subhomomorphisms / subfunctors have a standard name, and where can I learn more?

Sorry for all the mistakes in the original! I think they're mostly fixed now. Thank you for your patience. Part 1. If $A$ and $B$ are models in $\mathrm{Pos}$ of an algebraic signature $\sigma$, ...
2
votes
1answer
72 views

Extracting subnets from nets.

Let $x_i:\Lambda_i\to X_i$ be a net in a topological spaces $X_i$ that converges to $a_i\in X_i$ where $i\in\{1,2\}$ Does there exist a poset $\Lambda$ and subnets of $x_i:\Lambda_i\to X_i$ of the ...
1
vote
1answer
41 views

Does irreflexivity guarantee acyclicity?

Assume $R$ to be an irreflexive, transitive relation over a set $X$. Let $G=(X,E)$ be its directed graph where $(x,\hat{x})\in E$ if $xR\hat{x}$ is true. I know irreflexivity means $xRx$ cannot ...
2
votes
1answer
55 views

Bernstein- Schroeder thm for ordered sets

Hi everyone the I know that the Bernstein- Schroeder Thm says that if we have two sets $A,B$, and there exists an injection $f: A\rightarrow B$ and $g: B\rightarrow A$, then there exists a bijection $...
2
votes
1answer
303 views

non-prime maximal ideal in a complemented lattice

Is there a complemented lattice, which has a non-prime maximal ideal?
1
vote
2answers
182 views

Exercise in well-ordered sets

Definitions: Given a subset $A$ of a non-empty well-ordered set $X$ we define the supremum as follows: $\text{sup(A)}:=\text{min}\bigg(\big\{\,y\in X \oplus\{ +\infty\}: \forall x\in A \;(x\le y)\, \...
1
vote
2answers
40 views

Example for $\mathbb{N} ^ \mathbb{N}$ linear order

I'm not really sure if something like $ \{1,2,3,...\} < \{2,2,3,...\} < \{3,2,3,...\}$ works. I don't ask about solution with transitive, antisymmetric and total proof, just for working ...
1
vote
2answers
172 views

How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
3
votes
2answers
117 views

The set of all the partial ordering of $X$ is a partially ordered set.

I have trouble with the following exercise. I don't understand it. Also I think that $x,y\in P$ should be $x,y\in X$. Could someone give an insight of the exercise and also some hint of how to solve ...
1
vote
0answers
49 views

Recovering Ordered Monoid Operation from the Order

I have a partially ordered set $(X, \preceq)$ with the following properties: $X$ has a minimum. I'll name it $1$. For every $x \in X$, the principal filter ${\uparrow} x$ is order isomorphic to $X$. ...
0
votes
2answers
109 views

What is the maximum number of comparisons needed to define a total order

Given a set of values $X=\{x_1,x_2,…,x_m\}$. I want to construct an irreflexive, transitive total order relation $>$ by doing pairwise comparisons among the values of $X$. From trail and error I ...
3
votes
2answers
40 views

disconnected ordered set

Is there a totaly ordered infinite set $A$ with the least element $a$ and the greatest element $b$ such that for any sequence $\{\alpha_n\}$ and $\{\beta_n\}$ in $A$ which satisfies $\alpha_n<\...
7
votes
1answer
256 views

Intuition behind proof and verification partially ordered sets

Hi everyone in the book that I read I have trouble to understand the argument of the proof at the below proposition. There is a lot of point which are left as exercises, which is great. One of these ...
2
votes
1answer
572 views

Exercise: Every non-empty subset of $X$ contains a minimum and maximum element and the converse

Hi everyone is my second exercise of posets. And find the following, the first part I think is not difficult at all. But for the converse I have some serious troubles to prove it. I have two questions:...
2
votes
1answer
87 views

What conditions on a totally ordered set imply that the closed intervals are connected?

It is well known that $[a,b]_\mathbb{R}$ is connected, while $[a,b]_\mathbb{Q}$ is not. I'm wondering, what conditions on a totally ordered set $T$ imply that for all $a,b \in T$, it holds that $[a,b]...
2
votes
0answers
159 views

Partially ordered set exercise

Hi everyone is my first time working with posets and I'd like to know if the solution of the next exercise is really correct or maybe there is some errors that I cannot see. Thank in advance. ...
1
vote
2answers
155 views

Either two sets have the same cardinality, or one has cardinality greater than the other

This is a problem (10.11) from Munkres, Topology, 2 ed. Problem: Let $A$ and $B$ be two sets. Using the well-ordering theorem, prove that either they have the same cardinality, or one has cardinality ...
0
votes
1answer
152 views

Relation between concept lattice and Dedekind–MacNeille completion

While trying to unify the (mostly linearly) ordered attributes from Statistical classification with the binary attributes from formal concept analysis, I came across an interesting section in the ...
3
votes
1answer
123 views

Does model theory extend to partial functions?

I have been reading a bit about effect algebras and d-posets recently, sets $M$ on which you have a single partial binary operation (partial here meaning partially defined, i.e. the domain of this ...
0
votes
1answer
34 views

Ordering tuples over (0,1)

To understand the natural ordering of $\{0,1\}^N$ I first thought about $\{0,1\}^3$ which has this Hasse diagram: There's something interesting going on in the second and third rows. In 3-D it ...
2
votes
0answers
71 views

Set Theory - Well Order (Lexiographical combination)

Question: Prove constructively that if $(A_{1},\prec_{1})$ and $(A_{2},\prec_{2})$ are two well-ordered sets then their lexicographical combination $(A_{1} \times A_{2},<_{1,2})$ is also well ...
2
votes
1answer
92 views

Are there any known uncountable transfinite increasing sequences of real numbers?

The real numbers are uncountable, so assuming the axiom of choice there is at least transfinite sequence of real numbers $r_0, r_1, r_2, ..., r_\omega, r_{\omega + 1}, ..., $ up to (and possibly ...
2
votes
1answer
99 views

Help to understand a proof (about filters)

Niels Diepeveen claims that he has proved the following theorem: Theorem Consider the cofinite filter $F$ on an infinite set. Let $K$ be a collection of ultrafilters such that $\bigcap K=F$. Then for ...
6
votes
2answers
100 views

Existence of totally ordered ring with zero divisors

Does there exist a totally ordered ring with zero divisors? I can't think of an example right now.
0
votes
1answer
226 views

Could the empty set be complete partial order?

According to the definition, $(S,\leq)$ is cpo when each totally ordered subset of $S$ has supremum. I'm sure $(\emptyset,\emptyset)$ is a total order, but I don't know whether $(\emptyset,\emptyset)$ ...