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
1answer
11 views

Order between probability measures: sets full below

Consider a product space $X = \{0,1\}^\mathbb{Z}$ and the space of probability measures on $X$, $\mathcal{M}(X)$. We say that for any two $a, b \in X$, $$a \prec b \iff a_x \leq b_x \, \, \, \, \, ...
-2
votes
1answer
60 views

Any well-ordered set contains $\mathbb Z_+$ as an initial segement

An ordered set $A$ is well ordered if every nonempty subset of A has a smallest element. Prove the following Theorem: If $X$ is an infinite well-ordered set, then either (1) $X$ has the order type ...
0
votes
0answers
23 views

Show that a relation is a partial order with lubs and glbs of all pairs

I came across this question while doing my discrete mathematics and couldn't understand it completely. The question is as follows: Let $(N, ≤) $ be the set of natural numbers with the relation $ m ≤ ...
3
votes
0answers
58 views

Can all non-archimedean groups be written as a product of archimedean groups?

We say that a partially ordered group $(G,\cdot, \geq)$ is Archimedean if for any $g,h >1\in G$ there exists some n such that $g^n > h$. All the non-archimedean groups I know of can be written ...
0
votes
1answer
44 views

Any total order on $X$ is maximal element

Let $X$ be a non-empty set and $R$ be the set of partial orders on $X$. (1) Show that $R$ is partially ordered by inclusion $\subset$. (2) Show that any total order on $X$ is a maximal element in ...
0
votes
2answers
27 views

On the definition of Scott Continuity

I somewhere encountered the concept of "Scott Continuity" as follows. Let $P,Q$ be partially ordered sets; a function $f:P\to Q$ is Scott continuous if it preserves directed suprema, i.e. for all ...
1
vote
1answer
19 views

In the context of posets, is the notion of “compatible” elements a standard notion?

Let $P$ be a poset and let $x$ and $y$ be elements of $P$. I have occasionally seen books define a notion of "compatible" elements in a poset, so that $x$ and $y$ are compatible iff $\exists a \in P$ ...
1
vote
1answer
22 views

Extend an acyclic relation to an ordering

I am pre-studying a course (Discrete Mathematics) that I will be taking come fall quarter this October. We are using the textbook Invitation to Discrete Mathematics and I am having trouble starting to ...
1
vote
1answer
24 views

What is the supremum of {36,72} in this Hasse-diagram?

In this Hasse-diagram is sup({36,72})={72} or is it non-existent? I think it might be {72} because {72} seems to be the upper bound of {36,72}. Then again, {72} seems to be the only upper bound, so ...
1
vote
0answers
14 views

Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
0
votes
0answers
19 views

Automorphism of $(\mathbb{R}, <)$ that takes a finite set of reals to a set of naturals

I was working on another of Enderton's logic book exercises (specifically, exercise 20 (b) from section 2.2, p. 102), and, as part of the exercise, he asks us to show that, for any finite set of real ...
1
vote
1answer
21 views

Alternative definition for order-embedding

I realize that the traditional definition for an order-embedding f is that $a_1 \sqsubseteq a_2 \iff f(a_1) \sqsubseteq f(a_2)$ However, is it also fair to say that if $(A, \sqsubseteq)$ is a ...
3
votes
0answers
32 views

If a linearly ordered set $L$ has the property that every order-preserving injection $L \rightarrow L$ is expansive, is $L$ necessarily well-ordered?

Given a poset $P$, call a function $f : P \rightarrow P$ expansive iff $f(x) \geq x,$ for all $x \in P$. Now suppose a linearly ordered set $L$ has the property that every order-preserving injection ...
2
votes
1answer
34 views

Is $\{1,2\}\times [0,1)$ a linear continuum in the dictionary order?

In Munkres' Topology, it's stated that if $X$ is well-ordered set then $X \times [0,1)$ is a linear continuum in the dictionary order. Let us suppose that, $X=\{1,2\}$ and that $\mathord{<} ...
1
vote
1answer
77 views

How many possible DAGs are there with $n$ vertices

I am have $n$ vertices and trying to enumerate all possible DAGs $\theta$ over $n$. How many DAGs are there? For example when $n=2$, there are 3 possible DAGs and when $n=3$ I tried the following: ...
2
votes
1answer
86 views

For any $n \in \mathbb{N}$ there exists a minimal element in the set $ \{ x\in \mathbb{N}\mid n< x \}$

Problem from V. Zorich Analysis textbook: For any $n \in \mathbb{N}$ there exists a minimal element in the set $ \{ x\in \mathbb{N}\mid n< x \}$ namely $\min\{x \in \mathbb{N}|n<x\}=n+1$* ...
0
votes
1answer
20 views

If a poset is Dedekind-complete, is its opposite necessarily Dedekind-complete?

Call a poset $X$ Dedekind-complete iff for all non-empty sets $A \subseteq X$, the following are equivalent. $A$ has an upper bound $A$ has a least upper bound. Supposing $X = (X, \leq)$ is ...
2
votes
1answer
59 views

Constructing order embeddings between Boolean algebras from embeddings from their finite subalgebras

Suppose that $A$ and $B$ are two complete atomic Boolean algebras and $R$ is a relation between $A$ and $B$ with the following property: If $Rab$ and $A^\prime$ is a finite Boolean subalgebra of ...
0
votes
2answers
54 views

Prove that the binary relation “is a subset of” is a…

Prove that the binary relation "is a subset of" is a partial order (POSET)? Should I try to prove this in reference to the power set of a general set? When is this relation a total order?
1
vote
1answer
18 views

An accessible example of a preorder that is neither symmetric nor antisymmetric

For a project I am working on, I need an example of a preorder (reflexive and transitive relation) that is neither symmetric (like an equivalence relation) nor antisymmetric (like less than or equal ...
0
votes
1answer
28 views

Is it Preference relation?

I need to check if the relation $ \succeq ( \space \succeq \space \subset X × X, \space X=VB[0,1] ) $ define as below $$ f \succeq g \Longleftrightarrow Var(f+g) \geq Varf $$ is preference ...
2
votes
2answers
59 views

A question about the cardinality of a set of functions with finite support where the domain of each function has cardinality aleph-null.

Suppose that $M$ is a well ordered set with at least two elements and that $L$ is a well ordered set with the same cardinality as the natural numbers. Let $[L, s.f, M]$ be the set of all functions ...
3
votes
1answer
24 views

Well-ordered family of open sets.

Let $X$ be a second countable space. I $\textbf{A}$ is a family of open set well-ordered by inclusion prove that this family is numerable. I have the following idea: Let $\textbf{B}$ be a ...
1
vote
1answer
40 views

Dilworths Theorem proof doubt

This is the proof I am talking about http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf When you take a maximal chain C in P and then obtain antichains in P\C, if the size of the ...
0
votes
0answers
18 views

Diffrence between chaotic and Orderd Equations/systems

what is the difference between chaotic and Ordered Equations ? if the first one means that the system behaviour is not predictable , why we just call it stochastic process , and using random ...
1
vote
4answers
123 views

Are $1+ω$ and $ω+1$ isomorphic?

In set theory, $1+ω$ is defined as the ordinal number of ordinal sum of sets $\{a\}$ and ℕ. Also $ω+1$ is defined as the ordinal number of ordinal sum of sets $\Bbb N$ and $\{a\}$. You know what the ...
0
votes
3answers
47 views

Correctness of proof that every positive rational with square $>2$ is an upper bound for those with square $<2$

I would like to know whether my proof makes sense or not, and if not where should it be corrected. Let $E=\{x \text{ is rational }: x>0 \text{ and } x^2<2\}.$ Claim: Every member of $F=\{x ...
1
vote
1answer
47 views

Every subgroup of a cyclic group is characteristic (using lattice theory).

I want to show for $n\in\Bbb N$, which is not square-free, that every subgroup of $Z_n=\langle x\;|\;x^n\rangle$ is characteristic. But I want to show it in a convoluted way. Every automorphism ...
1
vote
1answer
42 views

Let $L$ and $L'$ be lattices. Prove that $L \times L'$ is also a lattice.

Can someone please verify my proof or offer suggestions for improvement? Some preliminaries: Let $A$ and $B$ be two posets. $A \times B$ is the poset on the cartesian product of $A$ and $B$ such ...
0
votes
1answer
36 views

maximum and maximal elements

Let B = {(2,4), (4,0), (4,3), (7,3)}. B has the order like the product order of $\mathbb{N} \times \mathbb{N}$ . Then, why B hasn't maximum and why the maximal elements are (2,4) and (7,3)?
1
vote
0answers
28 views

Prove that $P$ is a lattice (details inside)

Can someone please verify my proof or offer suggestions for improvement? There may be answers to the same questions elsewhere, but I need help with my proof in particular. Show that if $P$ is a ...
1
vote
1answer
13 views

Let $P$ be a finite poset. Show that the number of order ideals equals the number of antichains.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there are similar questions posted elsewhere, but I need help with my proof in particular. Some preliminaries: ...
2
votes
0answers
23 views

Let $P, Q, R$ be finite posets. Prove that $P^{Q+R} \cong P^Q \times P^R$.

Can someone please verify my proof and offer suggestions for improvement? I feel that my proof might have been a little hand-waving in showing that $\varphi$ is a bijection, and I feel that it is not ...
1
vote
4answers
385 views

Infimum and supremum of the empty set

Let $E$ be an empty set. Then, $\sup(E) = -\infty$ and $\inf(E)=+\infty$. I thought it is only meaningful to talk about $\inf(E)$ and $\sup(E)$ if $E$ is non-empty and bounded? Thank you.
0
votes
2answers
43 views

Is the function $x \mapsto \max\{f(x),g(x)\}$ always an automorphism if $f$ and $g$ are?

Consider a totally ordered set $X$ and a pair of automorphisms (i.e., order-preserving bijections) $f,g$ of $X.$ Then the function $$h:x \in X \mapsto \max\{f(x),g(x)\} \in X$$ is an order-preserving ...
2
votes
1answer
100 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
0
votes
0answers
17 views

Ingredients for Proving that a set is bounded below

I am having a hard time to really understand the definition of bounded below. The definition states : Let S be a nonempty subset of real numbers, we say S is bounded below if there is a c ∈ ℝ ...
1
vote
1answer
35 views

“Szpilrajn extension theorem” in Wikipedia

In this link: http://en.wikipedia.org/wiki/Szpilrajn_extension_theorem in the section "lemma". The author construct a partial order $T$ on a set $X$ which extends another partial order $R$ in the ...
0
votes
1answer
29 views

Homework | Prove Relation is Partial Order

I have been stuck on this question for quiet a bit of time. I'm not sure how to prove a relation $R$ is a partial order of $X$. Let $\mathbb{Z}$ be the set of integers and consider the set $X = ...
1
vote
0answers
40 views

A total order induce by a partial order

I have the following problem: Let $(A,\leq)$ a poset. Prove that there exist a total order $\leq^ *$ on $A$ such that if we have $a\leq b$ we can conclude $a\leq^*b$. (Hint: Use the Zorn Lemma) ...
1
vote
1answer
25 views

Understanding the notation of a response to a question about extending partial orderings.

I found a question and two answers that both are very complete but I cannot understand the meaning behind some of the symbols that are used. They are different from what I am familiar with. The ...
0
votes
1answer
30 views

Let $A$ be a partially ordered set in which every chain has an upper bound, and let $a \in A$. Then $A$ has a maximal element $u$ such that $u \ge a$.

Let $A$ be a partially ordered set in which every chain has an upper bound, and let $a \in A$. Then $A$ has a maximal element $u$ such that $u \ge a$. I'm trying to solve this by way of ...
1
vote
1answer
16 views

Proof Verification, any partially ordered set contains a maximal totally unordered subset (antichain).

I wrote a simple proof and I want to verify it. I simply argued that the set of all totally unordered subsets forms a partially ordered set, ordered by inclusion. Every chain in this partially ...
-1
votes
0answers
22 views

Ordered field - Adding inequalities (Looking for a proof)

In an ordered field, it is allowed to add two inequalities. Where can I find a detailed proof?
0
votes
0answers
15 views

Proof of a variation of Hausdorff maximality principle

Let ($A$, $\le$) be a partially ordered set and let $B$ be a totally ordered subset of $A$. Prove that $A$ has a maximal totally ordered subset $C$ such that $B \subset C$. I'm trying to prove this ...
0
votes
2answers
72 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 ...
14
votes
2answers
226 views

The preorder of countable order types

Consider the set $\mathcal{O}$ of order types corresponding to all posets of cardinality at most $\aleph_0$. The set $\mathcal{O}$ is a preorder under embeddability of its elements (note that some ...
1
vote
1answer
29 views

Infinite chain contains a chain order-isomorphic to either the positive integers or the negative integers.

I came across this statement and it is very intuitive to me. I am looking for more information such as a name associated with this theorem or even a more general theorem. Does such a name or more ...
3
votes
0answers
39 views

Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [closed]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
1
vote
1answer
72 views

Bijection from $\mathbb{R}^n$ to $\mathbb{R}$ that preserves lexicographic order?

Is there a bijective mapping $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ that preserves lexicographic order? That's to say, we'd need to have $f(x_1, \dots, x_n) \leq f(y_1, \dots, y_n)$ iff ...