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

9
votes
2answers
317 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
428 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
77 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
218 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
165 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
136 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
184 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
134 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
239 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
161 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
218 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
799 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
147 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
177 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
169 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
103 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
246 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
114 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
425 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 ...
1
vote
2answers
832 views

How is GLB and LUB different than the maximum and minimum of a poset?

As the subject asks, how is the greatest lower bound different than the minimum element in a poset, and subsequently, how is the least upper bound different than the minimum? How does a set having no ...
2
votes
1answer
46 views

Can infinite joins/meets be viewed as special cases of a limit with respect to some topology?

Let $L$ denote a complete lattice. Is there a topology on $L$ such that infinite joins and meets can be viewed as a special kind of "limit"?
1
vote
1answer
69 views

Two topologies generated by a partially ordered set - are they equal? Are they $T_0$?

Let $P$ denote a partially ordered set, and consider two topological spaces with carrier $P$. The topological space whose closed sets are generated by the upsets and downsets of $P$. The ...
3
votes
1answer
127 views

Is every discrete topological space orderable?

I apologize for asking a question in topological terms when it's not really about topology, but here goes: If $S$ is a set, is it always possible to totally order $S$ so that every non-minimal ...
5
votes
3answers
261 views

Determine if the following is a partial order, and if so, is it a total order?

I'm having trouble figuring out how I can solve this... I've never been good with formal proofs. $$(\mathbb{R},\preceq), a\preceq b\iff a^{2}\leq b^{2}$$ I can easily see that it's Reflexive: ...
1
vote
2answers
111 views

inf and min in partial order

Assume $P$ is a partial order. Does it holds that $\inf (\inf(a,b), \inf(c,d)) = \inf(a,b,c,d) $? My guess is that it holds. But I don't know how to check it. Also what if instead of $\inf$ I use ...
2
votes
1answer
134 views

Constructing an order-preserving function between two strict p.o.s that is not one-to-one.

Out of Winfried Just and Martin Weese's Set theory book: Give an example of strict partial orders $\langle X,<_x\rangle$ and $\langle Y,<_y\rangle$ and of a function $\tau : X \to Y$ that is ...
0
votes
0answers
194 views

From point-wise to essential supremum of a set of real-valued measurable functions

I want to prove some property about essential suprema and I think I can show them for the pointwise supremum $\sup S$. The problem is, that the sets involved are uncountable and thus, the point-wise ...
6
votes
1answer
74 views

What are ideals in a complete lattice?

If I have a complete lattice $L$, what conditions do I need for $I\subseteq L$ to be an ideal? In a general lattice the conditions are: $I$ is a lower set; $I$ is closed under (finite) joins. For ...
0
votes
2answers
49 views

Why am I getting that minimal elements are equivalent to the minimum?

I have these two definitions, about minimals and minimums in an order relation: $b$ is minimal in $B<=>¬\exists:(x \in B \land x \prec b)$ and also equivalent to $ \forall x,[(x \in B \land x ...
2
votes
1answer
120 views

Total Ordering and relation

Consider the relation $<$ on $\mathbb{Q}$ defined by: $(m, n) < (j, k) \iff jn-mk \in \mathbb{N}.$ Where $m, j \in \mathbb{N}$ and $n, k\in\mathbb{Z}$ I want to show that $<$ is a total ...
0
votes
1answer
103 views

Theorem unique bijection between two well-ordered sets satisfying certain conditions

I have some problems understanding the proof of the following theorem. Given two well-ordered sets $(X, \le _X), \ (Y, \le _Y)$ there exists exactly one partial function $f(X, Y)$ such that: 1)$f: \ ...
1
vote
1answer
195 views

Width of a product of chains

Write $E_k = (\{0, \ldots, k-1\}, \leq)$ the total order on $k$ elements. If $(A, \leq_A)$ and $(B, \leq_B)$ are two posets, the product poset is $(A \times B, \leq_{A \times B})$ with the order ...
1
vote
2answers
407 views

Infimum/Supremum of an intersection of subsets of a vector space.

Consider a collection of subsets $A_i$ of an ordnered vector space or field. I am trying to find out, under what (minimal) conditions the following holds. $\inf \bigcap_{i\in I}A_i \le \sup_{i\in ...
2
votes
2answers
128 views

Embedding ordered number fields into $\Bbb R$

Consider a number field $K$ equipped with a total order $\le$. Is there always a field homomorphism $\phi:K \rightarrow \Bbb R$ which respects the total order, i. e. with $\phi(x)>\phi(y)$ for ...
3
votes
1answer
133 views

Robertson-Seymour fails for topological minor ordering? (I.e., subgraphs and subdivision)

The Robertson-Seymour theorem says that the set of isomorphism classes of finite graphs, with the minor ordering ($G \le H$ if $G$ is a minor of $H$) is a well partial ordering (it is well-founded and ...
1
vote
1answer
115 views

Atomic Boolean lattice is weakly atomic

The book "Introduction to Lattices and Order" says at Exercise 10.12 that an atomic Boolean lattice is weakly atomic. Could you tell me why it holds?
2
votes
1answer
58 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
1
vote
2answers
180 views

Is the topology generated by the open intervals of a partially ordered set necessarily T_0?

Let $X$ denote a set and consider a collection $C \subseteq \mathcal{P}X$. Let $\mathcal{T}$ denote the set of all topologies $T$ on $X$ such that $C \subseteq T$. Then $\bigcap \mathcal{T}$ is a ...
2
votes
1answer
118 views

Standard notation for the the collection of all *minimal* elements of the set of all upper bounds?

Let $(P,\leq)$ denote a poset and suppose $X \subseteq P$. Then the minimum element of the set of all upper bounds of $X$ can be denoted $\operatorname{sup} X$, or $\bigvee X$. Is there a similar ...
5
votes
2answers
264 views

Motivation for a new definition of the derivative using the concept of average velocity

As everyone knows, for a function $ f: \mathbb{R} \to \mathbb{R} $ and a point $ a \in \mathbb{R} $, we say that the derivative of $ f $ at $ a $ equals $ L $ if and only if $$ \lim_{x \to a} ...
6
votes
3answers
168 views

Incomparable subsets of real numbers with usual order relation

Consider linear order $(R,<)$, would there be two sub-orders $(X,<), (Y,<)$ of it such that $X,Y$ are uncountable, which are incomparable in the following sense: There does not exist order ...
1
vote
1answer
388 views

How to understand the duality between Dilworth's theorem and Mirsky's theorem?

Dilworth's theorem states that for any partial order, the size of the largest antichains is the size of the smallest chain partitions. Mirsky's theorem states that for any partial order, the size of ...
3
votes
1answer
449 views

Isomorphism from $\mathbb{R}$ to $(-1,1)$

There are many bijective functions that map $\mathbb{R}$ to $(-1,1)$, in particular: $$f\left(x\right)=\frac{e^{2x}-1}{e^{2x}+1}$$ (Of course there are others, such as ...