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
0answers
34 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
29 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
61 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
34 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
32 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
60 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
0answers
31 views

Order Embeddings

Let (S,<=) be an (partially) ordered set and A a subset of S with the inherited order, namely, <= /\ AxA Thus, A is order embedded in S. When S isn't a lattice and A is a lattice would would ...
0
votes
1answer
34 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 ...
1
vote
0answers
65 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
44 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
32 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 ...
0
votes
2answers
55 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
23 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
95 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
70 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$, ...
1
vote
1answer
49 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 ...
0
votes
0answers
13 views

Which properties inherited when combining a set of strict orders

Assume having a set of irreflexive, transitive and total orders $R_1,R_2,…,R_n$. Let $R$ be an ordering resulted from combining them. Regardless of the combination strategy, what is known about the ...
1
vote
1answer
27 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 ...
1
vote
1answer
36 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
111 views

non-prime maximal ideal in a complemented lattice

Is there a complemented lattice, which has a non-prime maximal ideal?
1
vote
2answers
104 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
29 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
35 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
79 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 ...
0
votes
0answers
42 views

Prove after seeing $k$ comparisons, there is no total order with $k+1$

Let $X=\{x_1,x_2,\dots,x_m\}$ be a set of $m$ values. Let $Z=\{\succ_1,\succ_2,\dots,\succ_{m!}\}$ be the set of all possible strict total orders over $X$. A comparison $c_{(i,j)}$ is a test between ...
0
votes
0answers
39 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$. ...
1
vote
0answers
23 views

Positive domains

I define a positive domain to be a quintuple $(S, +, *, 0, 1)$ where $0$ and $1$ are distinct, $(S, +, 0)$ and $(S, *, 1)$ are commutative monoids, $0$ annihilates $*$, $*$ is distributive over $+$, ...
0
votes
2answers
73 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 ...
4
votes
2answers
39 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 ...
6
votes
1answer
201 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
183 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 ...
2
votes
1answer
64 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 ...
2
votes
0answers
64 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
86 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
81 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
75 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
33 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
46 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 ...
1
vote
1answer
63 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
80 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 ...
3
votes
1answer
53 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
51 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)$ ...
5
votes
1answer
59 views

Existence of non-commutative ordered ring

Does there exist a totally ordered ring which is non-commutative? I have searched the web, but I have not found any examples.
5
votes
2answers
63 views

Countability of a certain set

Suppose $S$ is a totally ordered set such that for any $x,y\in S$ there are finitely many elements between them. Does it follow that $S$ is (at most) countable? It seems like the answer should be ...
4
votes
4answers
142 views

How long does a sequence need to be to be guaranteed to have a monotonic subsequence length k?

The sequence 7, 2, 4, 1, 4, 8 has an increasing subsequence length four (2, 4, 4, 8) and a decreasing subsequence length three (7, 4, 1). It has other monotonic (increasing or decreasing) subsequences ...
-1
votes
2answers
57 views

Is a Lattice just a linearly ordered set?

The definition of Lattice I was introduced to recently was a poset for which every two elements had a supremum and infimum. Doesn't this just mean that the poset is a chain and tus a linearly ordered ...
1
vote
1answer
51 views

How many complete theory extend theory T are there?

$Т$ - theory of signature $\{\le\}$, defined by the axioms А1-А5: А1: $\forall x(x=x)$ А2: $\forall x,y\big((x\le y\land y\le x)\to x=y\big)$ A3: $\forall x,y,z\big((x\le y\land y\le z)\to x\le ...
1
vote
1answer
20 views

Does the closure of the set of all irreducible elements always equal the whole set?

Let $X$ denote a set and $\mathrm{cl}$ denote a finitary closure operator on its powerset. Call $x \in X$ irreducible iff for all $A \subseteq X$ we have that if $x \in \mathrm{cl}(A)$, then $x \in ...
2
votes
2answers
104 views

structure of the hypernaturals

I want to understand the structure of the hypernaturals a little better. Let me recall the ultraproduct construction of the hypernaturals. On the set of all sequences of $\mathbb{N}$, we define an ...
-1
votes
1answer
22 views

partially order

$( A,\le)$ and $(A',\le')$ are partially ordered sets. A map $\phi : A \to A'$ is called order preserving from $(A, \le)$ to $(A', \le')$ if for all $x, y \in A : x \le y \implies \phi(x) \le' ...