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

15
votes
7answers
10k views

Example of Partial Order that's not a Total Order and why?

I'm looking for a simple example of a partial order which is not a total order so that I can grasp the concept and the difference between the two. An explanation of why the example is a partial ...
3
votes
0answers
130 views

Infinite set ordered like a “infinite tree”

Obviously I don't need to say that I'm still a newbie, so I'll try to explain my question with some pics too. I have a infinite set $T$ I have a visual idea of how this set is ordered, but I don't ...
4
votes
1answer
345 views

Exclude operation symbols in signature

We probably know what a signature is, it contains a set $\sigma_{op}$ (the operation symbols), $\sigma_{rel}$ (the relation symbols) and a function $ar:\sigma_{op}\cup\sigma_{rel}\rightarrow\mathbb ...
4
votes
2answers
83 views

Semi-formal language

I want use semi-formal language to describe the following four points. (1) The group axioms with signature $\{*\}$ (2) The property "linear order" with signature $\{<\}$ The following properties ...
5
votes
1answer
2k views

Strict partial order

I know what is a partial order: for example the power set of a set or the natural numbers. But a strict partial order is a set with a binary relation $R$ so that $R$ is transitive, irreflexive (not ...
2
votes
1answer
71 views

“Lexicographic order” without priority, but with ties, how to define / what's the name?

I'm searching for an ordering principle which combines two (or more) preorders, akin to the lexicographic order, but not quite: I'm looking for an ordering principle that does not priorities, but ...
3
votes
1answer
274 views

Dense linear orderings isomorphism [duplicate]

First of all the definition: A dense linear order is a $\{<\}$-structure in which the following formulas are valid: Question: How can I prove that any two countable DLO's (dense linear order) ...
1
vote
1answer
93 views

Projecting external points to a circle: Distance order preserving?

Given a circle, and a set of points $A$ that lie external to the circle; I perform the following simple operation: I compute the point of intersection of the i) circle and the ii) line joining each ...
0
votes
1answer
30 views

Finding an ordered set

Find a partially ordered set $A$ so that for every member a in $A$, there is $b∈A$ such that $b<a$ but for infinitely many members of $A$, there does not exist $c\in A$ such that $a<c$. Thanks. ...
1
vote
1answer
41 views

Finding a partially ordered set

Find a partially ordered set $A$ so that for every member $a$ in $A$, there is $b\in A$ such that $b<a$ and there exist just finitely many members bigger than $a$. Thanks.
1
vote
2answers
85 views

Partially ordered set, maximal and minimal

Show there exist partially ordered sers with more than one maximal element and /or more than one minimal element. This is not a Homework question so completeness is appreciated.
0
votes
1answer
919 views

Subset of a partially ordered set: Least upper bound and greatest lower bound.

Let $(A, \leq)$ be a poset and $B \subseteq A$. I need to show i) B may have at most one least upper bound in A ii) B may have at most one greatest lower bound in A.
0
votes
1answer
145 views

order preserving function over Poset

I have a DAG (Directed Acyclic Graph) $G$ represents the dominance relation between solutions. A path from $x$ to $y$ means $y\succ x$ ($y$ dominates or better than $x$) where the absence of such a ...
3
votes
1answer
53 views

Do the pth powers of $p$-norms define the same partial ordering on the set of all probability distributions for all $p>1$?

Consider the $p$-th power of the Schatten $p$-norm $||q||_p$ of a probability distribution $q$ , ie, the function $\sum_j q_j^p$, where $\sum_j q_j = 1$ and $q_j \geq 0$. For fixed $q$ and $p>1$ ...
0
votes
2answers
513 views

Help on total ordering and partial ordering

Hi guys my final exam is coming up, and I am given a few practice problems and I don't get how to do these questions on total ordering and partial ordering. Here are the question and here is how I did ...
8
votes
7answers
1k views

Give an example of a simply ordered set without the least upper bound property.

In Theorem 27.1 in Topology by Munkres, he states "Let $X$ be a simply ordered set having the least upper bound property. In the order topology, each closed interval in $X$ is compact." (The LUB ...
2
votes
1answer
56 views

Not sure about this Hasse Diagram

I'm not sure how to draw Hasse diagram of this set $\{-2,-1,0,1,2\}$, $R = \{(a,b)\mid a\leq b\}$. My attempt is just a straight edge with the smallest vertex at the bottom and the greatest at the top ...
1
vote
1answer
1k views

Topological Sorting in Linear Order for Hasse Diagram

I have come across an exam review question that I am stuck on. The question states: Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram: This is ...
1
vote
1answer
221 views

How is the Power set without the original set a partial order?

This is a past exam question. Let S = {a,b,c} Define $\mathcal{P}(S)$ as the power set of S. Consider $\mathcal{P}(S)\setminus S$ Explain how this structure illustrates the concepts of partial ...
1
vote
2answers
1k views

Discrete Math - Hasse Diagrams

This is one of many questions of similar type I have to do for an assignment and im troubled with what to do. The question is as follows: Consider a relation R defined on the set A = {−7, −6, −5, ...
1
vote
1answer
147 views

how to combine different partial orders (Poset)

Given two posets $\prec_A$ and $\prec_B$ where $A\neq B$ and $A\cap B\neq \emptyset$, is there any way to combine them while preserving the exact information they exhibit - namely dominance relation ( ...
2
votes
1answer
157 views

Can a Partial Order be symmetric in addition to its properties?

For example,a relation,R defined on integers. $R = \{(a,b)\mid a^3=b^3\}$ Could this be partial order?
0
votes
0answers
103 views

Finite ordered sets and their isomorphism

This is a slightly strange question perhaps. How many ways are there to prove that if X and Y are two finite orders (total orders) on n elements, then X and Y are isomorphic? There is a direct proof ...
1
vote
1answer
60 views

Proof: $a<b$ and $ b<c$, then also $a<c$ (for partially ordered set of $M$)

I have the following question: If $\leq$ is a partially ordered set over $M$ and $a<b$ and $b<c$, then also $a<c$ holds. I'm a little confused, because I know that a partially ordered set ...
9
votes
2answers
322 views

How many ordinals can we cram into $\mathbb{R}_+$, respecting order?

I've been pondering the following question. How can we measure the amount of "space" above an element $p$ in a partially ordered set $P$? One way would be to try to cram the elements of ...
4
votes
2answers
67 views

Kinda well-orderedness.

Its not the case that $\mathbb{Z}$ is well-ordered (under the usual order). However, observe that Every non-empty subset of $\mathbb{Z}$ that is bounded below has a least element, and Every ...
2
votes
2answers
439 views

Drawing lattices

I would like to be able to draw the lattices of subgroups of certain groups. I thought it would be easy when I already know the structure, but I've never done it before, and it turns out it's harder ...
7
votes
1answer
140 views

Why should the union of such a family of sets have cardinality $\aleph_1?$

Let $\mathcal A$ be a family of infinite countable sets which is linearly ordered by inclusion and such that $\bigcup\mathcal A$ is uncountable. I have to prove that $|\bigcup\mathcal A|=\aleph_1.$ I ...
2
votes
1answer
79 views

Proof for a creating a partition of a countable set using chains in partial orders.

Definition: A partition of a set $A$ is a set of nonempty subsets of $A$ called the blocks of the partition, such that  every element of $A$ is in some block, and  if $B$ and $B'$ are different ...
1
vote
1answer
221 views

Preference Relation and Utility Function - Problem with inductive proof

I have a problem with an inductive proof of the following result. Theorem: If $X$ is a finite set, a binary relation $\succ$ is a preference relation iff there exist a function $u:X\rightarrow R$ ...
3
votes
3answers
166 views

What exactly is a lattice? And can somebody give an example of something that is not one?

Looking at the (very brief) definition in my textbook with no examples, I have the following: A poset $(A,\preceq)$ in which every two elements have a greatest lower bound in $A$ and a least upper ...
1
vote
2answers
139 views

Partition of lattice into symmetric chains

Let $C_1 \subsetneq C_2 \subsetneq C_3 \subsetneq \cdots \subsetneq C_k$ be a chain in the subset lattice $(2^{[n]},\subseteq)$. A chain is considered symmetric if $|C_1| + |C_k| = n$ and ...
2
votes
1answer
190 views

Trichotomy of well ordering

I'm trying to prove trichotomy of well ordering and I have a question concerning the proof of the following fact: given two well ordered set $(A,\triangleleft_A),(B,\triangleleft_B )$, then the ...
8
votes
1answer
137 views

Does there exist an ordered ring, with $\mathbb{Z}$ as an ordered subring, such that some ring of p-adic integers can be formed as a quotient ring?

I'm not sure if this might instead be MathOverflow material, but I'll give it a shot here first anyway. Does any ring $R$ exist that satisfies the following properties? $R$ is a totally ordered, ...
8
votes
3answers
243 views

Partial order Proof

Suppose that $<$ is a partial order on a set $A$. Prove that there exists a linear order $<'$ on $A$ such that for all $x,y \in A$, if $x < y$ then $x <' y$. Please someone give me ...
3
votes
1answer
162 views

A problem about compact order topological space

This problem is from terrytao.wordpress.com/books/analysis-ii,Errata to the second edition (hardcover),P.390,Exercise 13.5.8 .I have difficulty proving this,appreciate any help! Show that there ...
0
votes
1answer
221 views

The proper subset relation and strict partial order

The proper subset relation, $\subset$, defines a strict partial order on the subsets of $[1,6]$, that is $pow[1,6]$. (a) What is the size of a maximal chain in this partial order? Describe one. (b) ...
1
vote
1answer
812 views

Procedure for Max Function with identical random variables

I am studying for the P/1 actuarial exam, and I keep encountering one type of problem which I can't seem to solve and can't seem to find any generalized explanation for how to do it in my textbooks. ...
4
votes
1answer
138 views

Total orders making a family of functions non-decreasing

Suppose $S$ is a finite set and we are given a family of functions $(f_i:S\to S)_{i\in I}$. When can we find a total order $<$ on $S$ such that all the functions $f_i$ are nondecreasing? I am ...
0
votes
1answer
70 views

If every subset of a total order $(P,\leq)$ is isomorphic to an initial segment of $(P,\leq)$, then is $P$ a well-order?

I have to proof that "If every subset of a total order $(P,\leq)$ is isomorphic to an initial segment of $(P,\leq)$, then $P$ is a well-order". I already got the proof of the converse and this ...
7
votes
3answers
148 views

What structure does the space of functions into $X$ (or the cartesian exponentiation of $X$) inherit from $X$?

When dealing with a space $X$, that posses a lot of structure (complete lattice, complete metric space, vector space), what can be said about the cartesian exponentiation $X^Y=\{f \mid f:Y\rightarrow ...
2
votes
2answers
69 views

Finding the number of $2$-element chains of $B_n$

I'm trying to calculate the number of $2$-element chains and anti-chains of $B_n$, where $B_n$ is the boolean algebra partially ordered set of degree $n$. I understand that I want to take all of the ...
0
votes
1answer
182 views

Hasse diagram with maximal chain not counted in maximal anti-chain

Construct a post (Hasse diagram) that contains a maximal anti-chain of size $r$ and, after removing a chain $C$ of maximal size, it still contains an anti-chain of size $r$.
2
votes
1answer
171 views

Two questions of set theory: necessary and sufficient conditions for a subset of a poset to be centered, posets with noncentered linked subsets.

$(1)\hspace{4pt}$ Let $\left\langle X,\leq\right\rangle$ be a poset, and let $Y\subseteq X$ with $Y\ne\emptyset$. I’m trying to prove that $Y$ is centered—i.e., $Y$ is a filterbase on ...
0
votes
1answer
62 views

Showing that $\mathbb{C}$ under the lexicographic order does not satisfy $x,y>0\implies xy>0$

Identifying $\mathbb{C}$ with $\mathbb{R} \times \mathbb{R}$, we can consider the lexicographic order: we define $x_1 + iy_1 < x_2 +iy_2$ if either A) $x_1 < x_2$ or B) $x_1 = x_2$ and $y_1 ...
6
votes
1answer
106 views

A new(?) partial order on the set of continuous maps

Let $X,Y$ be topological spaces. Define a partial order on $\hom(Y,X)$ as follows: $f \leq g$ if $f^{-1}(U) \subseteq g^{-1}(U)$ for all open subsets $U \subseteq X$. Equivalently, $f(y)$ is a ...
9
votes
2answers
248 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
2
votes
3answers
115 views

Confused about preservation of well-quasi-orders

I don't understand preservation of well quasi-orders, here is what I have thought about: Definition A binary relation $R$ on $X$ is a quasi-order when it is reflexive and transitive. Definition A ...
3
votes
1answer
98 views

Existence of a minimal set of linear order that is equivalent to the given partial order

Let $\{(P, \leq_{\alpha})\}_{\alpha \in A}$ be a set of linear order on set $P$, $(P,R)$ be a partial order on the same set $P$. We say that the former is equivalent to the later, iff: $$\forall a, b ...
8
votes
3answers
430 views

Ordinal exponentiation - $2^{\omega}=\omega$

This is my understanding of ordinal arithmetic - two ordinals are the same as one another if there is an order-preserving bijection between them. So for instance $$1+\omega = \omega$$ because if ...