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

3
votes
3answers
54 views

Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice)

I am interested in proving the titular claim: Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice) My approach: Let $R$ be a well-founded relation. We ...
0
votes
0answers
27 views

Betweenness question

Could someone help me solve these betweenness questions? I am really struggling with this unit. Here is an additional link to my class notes ...
0
votes
0answers
19 views

Linear order question? [on hold]

I am working on some homework and can someone assist me with these linear order problems? Additional content: http://www.math.utk.edu/~dydak/460Su15/Files/zCh55FullPage.html Here is a link with some ...
1
vote
0answers
5 views

Properties of infimum and supremum w.r.t. conic orders, in particular positive semidefinite matrices

Given a convex cone $\mathcal{K}\subseteq \mathbb{R}^n$, we can define a partial order $\leq_\mathcal{K}$on $ \mathbb{R}^n$ by setting $$x\leq_\mathcal{K} y \Leftrightarrow y-x\in \mathcal{K}.$$ For ...
6
votes
1answer
187 views

definition of ordered vector space

An ordered vector space is the pair $(V , \leq)$ where it satisfies the following: For all $x,y,z \in V, \lambda \geq 0$, i) $x \leq y \Rightarrow x+z \leq y+z$ ii) $x \leq y \Rightarrow \lambda ...
1
vote
1answer
20 views

Example of $\omega$-complete poset that is not chain complete

An $\omega$-complete poset is a poset in which every countable chain has a join. A chain complete poset is a poset in which every chain has a join. Have you an example of a (non-countable) poset that ...
1
vote
2answers
26 views

A simple way to know whether a well-ordered set has a subset of a certain type

Following my last question, Does $\Bbb R-\Bbb Q$ have a well ordered subset of type $\omega\cdot\omega$, I would like to have better tools to look at a set and know what order types can it have. I ...
1
vote
1answer
18 views

Linear continuum poset with succ and pred

Is there a poset of continuum cardinality that satisfies conditions: it is linear there is a minimum element there is a maximum element each element (apart from maximum) has a successor each element ...
0
votes
1answer
38 views

The order isomorphism theorem without Replacement

In $\sf ZF$, there is the following theorem: Theorem: For any well-ordered set $\langle A,\prec\rangle$, there is a (unique) order isomorphism $F$ from $\langle\alpha,\in\rangle$ to $\langle ...
-1
votes
1answer
38 views

What's the name of this type of a set?

So I have a set $\{i_1,i_3,i_5\}$. What do we call the following set? Is there a standard name for it? $\emptyset, \{i_1\}, \{i_1,i_3\}, \{i_1,i_3,i_5\}$. Note that we do not have $\{i_3,i_5\}$ in it ...
1
vote
1answer
25 views

Prob. 9, Sec. 10 in Munkres' TOPOLOGY, 2nd ed: How to verify transitivity for anti-dictionary order?

Let $A$ denote the set of all the sequences of positive integers each of which ends in an infinite string of $1$s. For any two elements $x, y \in A$, let's define $x < y$ if there is some positive ...
3
votes
1answer
55 views

What's so special about the grounded poset of cardinality $2$?

By a grounded poset, I mean a poset $P$ with a bottom element $0_P$. Arrows between grounded posets are monotone mappings that preserve the basepoint. This gives a self-enriched category; lets call it ...
1
vote
1answer
36 views

is an order isomorphism between X and Y also an order embedding from X into Y?

is an order isomorphism between X and Y also an order embedding from X into Y? Please assume that X and Y are both well-ordered sets. I think the answer is yes.. but am not 100% sure. Thanks in ...
0
votes
2answers
35 views

order isomorphism between two intervals, where both have minimum and maximum elements

Note to viewers of this question: My apologies for the late night typos. The answers that I got from James et.al. were great, but targeted to definitions that were in error due to my typos. So those ...
2
votes
2answers
49 views

Finding subgraph in DAG in which all nodes are smaller than all others

I think my problem might be one of terminology, so let me explain what I am trying to do. Given a direct acyclic graph $G$ interpreted as a partial order, I want to find a subgraph $S$, so that ...
7
votes
2answers
97 views

Well ordering agreeing with ordinal ordering on a cardinal

This is an exercise from Kunen book - Set theory, an introduction to independence proofs. Let $\kappa$ be an infinite cardinal and $\triangleleft$ any well-ordering of $\kappa$. Show that there is an ...
1
vote
0answers
130 views

Assume n is an even integer. For an odd integer m, a sequence of m sets S1,…,Sm ⊆ [n] is a graceful chain of length m if…

Assume $n$ is an even integer. For an odd integer $m$, a sequence of $m$ sets $S_1, \dots, S_m \subseteq [n]$ is a graceful chain of length $m$ if: $S_1 \subset S_2 \subset \dots \subset S_m$ For ...
3
votes
2answers
149 views

order isomorphism maps $f < g$ to $Tf < Tg$?

Suppose $C(X)$ is the set of functions $f:X \rightarrow \mathbb{R}$. A bijection $T:C(X) \rightarrow C(Y)$ is called order isomorphism if $f \leq g$ if and only if $Tf \leq Tg$. $f \leq g$ means ...
0
votes
1answer
38 views

Order isomorphism between $(-\infty,0)$ to $(0, \infty)$

Is there an explicit order isomorphic function between $(-\infty,0)$ to $(0, \infty)$? There should be one, because both are order isomorphic to $\mathbb{R}$, but I can't think of one.
0
votes
0answers
9 views

Generalizing a theorem about filters on a boolean lattice

Let $\mathfrak{A}$ be a bounded distributive lattice with binary meet and join $\sqcap$ and $\sqcup$. I will denote $\partial F = \{ X\in\mathfrak{A} \mid \forall Y\in F: X\sqcap Y\ne \bot \}$ where ...
1
vote
2answers
43 views

Uniqueness of completion of dense totally ordered sets

Let $(P, <)$ be a dense totally ordered set. Then there exists a complete totally ordered set $(C, \prec)$, such that: $P \subseteq C$. If $p,q \in P$ then $p<q \iff p \prec q$. $P$ is dense ...
1
vote
1answer
41 views

Is every compact totally ordered space homeomorphic to a subset of $[0,1]$?

Let $(X,\leq)$ be a totally ordered set such that, equipped with the order topology, $X$ is compact. Is then $X$ homeomorphic to a closed subset $A \subseteq [0,1]$? A way to ask this question ...
0
votes
0answers
13 views

An alternate definition of ideals

A filter on a poset if by definition its nonempty subset $F$ such that it does not contain the least element and $A, B \in F \Leftrightarrow \exists Z \in F : (Z \le A \wedge Z\le B)$ for every ...
2
votes
1answer
51 views

Trichotomy implies totality of partial order

Theorem: A partially ordered set is totally ordered if it obeys the law of trichotomy. Things I know: A relation on some set $A$ is said to be a partially ordered set if the relation is reflexive, ...
1
vote
1answer
20 views

Intersection of two filters on a poset

Fix a poset. A filter on the poset is its nonempty subset which is both a down-directed set and an upper set. Conjecture Intersection of two filters is also a filter. I have proved this conjecture ...
1
vote
1answer
60 views

Regarding chains and antichains in a partially ordered infinite space [duplicate]

I've been given this as an exercise. If P is a partially ordered infinite space, there exists an infinite subset S of P that is either chain or antichain. This exercise was given in the Axiom ...
1
vote
2answers
24 views

unclear why subset of a lexicographic ordered set of strings is said NOT to have a least element.

I am watching an excellent series on Discrete Mathematical Structures from IIT At the 47:33 mark of the video the instructor constructs a set of strings as ...
4
votes
1answer
61 views

Generalization of metric spaces?

Usually we define a metric on a space $X$ to be a map $X\times X\to\mathbb{R}$ that satisfies a few axioms. $\mathbb{R}$ has of course a total order. What if we instead have a metric $X\times X\to A$ ...
0
votes
1answer
27 views

Prob. 5, Sec. 4.1 in Kreyszig's functional analysis book: A finite partially ordered set has a maximal element

Let $M \neq \emptyset$ be a finite partially ordered set. Then how to show that $M$ has at least one maximal element? My effort: If $M$ has only one element, then that element is (vacuously) the ...
2
votes
0answers
33 views

When is an ordered space scattered?

There is a concept of scattered in both order theory and topology. A topological space $X$ is scattered if every nonempty subspace has an isolated point. A linearly ordered set $( X , < )$ is ...
1
vote
1answer
40 views

Does $\mathcal{P}(\alpha)$ have maximal well-founded subsets?

Let $\alpha$ denote an ordinal. Then clearly, the powerset $\mathcal{P}(\alpha)$ has well-founded subchains that are maximal with respect to this condition (of being well-founded subchains), since ...
0
votes
1answer
39 views

Proving minimum implies minimal

$$q\in T \text{ is a minimum element of }T\text{ means }(\forall x\in T\setminus\{q\}: q R x\\ q\in T \text{ is a minimal element of }T\text{ means }(\forall y\in T\setminus\{q\}): y !R q.$$ Those ...
0
votes
0answers
22 views

Are all locally finite total orders isomorphic to a subset of Z?

This seems to be an obvious fact. Does anybody know a printed reference? (A partial order is locally finite if all closed intervals are finite.)
1
vote
1answer
35 views

Choosing a $x \in$ $X$, with $X$ an infinte set, $<$ a well-ordering on $X$, such that $x < x'$ for only finitly many $x' \in X$

Let $X$ be an (countable or not) infinte set, $<$ a well-ordering on this set. Lately I read a proof in which was explicity stated to choose an element $x \in X$ such that there are infintly many ...
1
vote
1answer
21 views

Def. 4.1-1 in Kreyszig's functional analysis book: Any example of a subset of a poset with more than one upper bound?

Can we given an example of an element $m \in M$, where $M \neq \emptyset$ is a partially ordered set, such that $m$ is a maximal element of $M$, but $m$ is not an upper bound of any subset $W (\neq ...
0
votes
2answers
27 views

Upper Bounds Of Sub Sets

Prove/Disprove: Let $A\subseteq B\subseteq \mathbb{R}$ If $B$ is bounded from below so $A$ is bounded from below. $B$ is bounded from below $\rightarrow$ $x\leq B$. Let there be $z\in A$, ...
3
votes
1answer
35 views

Having trouble in understanding what subset of a poset means.

I am having a problem to visualise a subset of a poset. Let $S = \{a,b,c\}$. Then $\mathcal{P}(S) = \{\{\},\{a\}, \{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\} \}$. Now if I impose $\subseteq$ on ...
11
votes
6answers
2k views

Is there a real number which comes just after a particular real number?

This is like when we say that the integer which comes just after $2$ is $3$. Is there a real number which comes just after a particular real number? For example: Is there a number which comes just ...
10
votes
1answer
179 views

What is known about this well-ordering of the rationals in a finite interval?

Given any interval $I=(a,b) \subset \mathbb R^+$, we may order the rationals in $I$ with a denominator-first lexicographic order, as follows: First, we list, in increasing order of numerator, all $q ...
2
votes
2answers
68 views

minimal embeddings of topological spaces into connected spaces

Defintions: Let $X$ be a topological space. 1) A connected space $Y$ is a minimal connected ambient (m.c.a for short) space for $X$ if there exists an embedding $i:X\mapsto Y$, and for every ...
2
votes
2answers
41 views

A Chain of Subsets of $\mathbb{R}$ Without any Good Countable Subchain

Consider which $\bigl{(} A_i \bigr{)}_{i\in I}$ is a chain of subsets of $\mathbb{R}$. We say that a countable chain like $\bigl{(} B_n \bigr{)}_{n\in \mathbb{N}}$ is good if : for every $n\in ...
0
votes
1answer
25 views

Are these partial order or total orders?

I just want to know if the following are considered partially ordered sets or total set. Here is the definition: $\mathbb{R}^2$ : (a,b) R (c,d) iff $a\leqslant c$ and $b\leqslant d$ $\mathbb{R}^2$ ...
3
votes
1answer
66 views

Relationship between $S$ and $S^{-1}$

This is one of the problem I have been solving in Velleman's How to Prove book: Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that if $R$ is symmetric, ...
0
votes
0answers
43 views

Lexicographic order, $\mathbb{Z^+ \times Z^+}$ $\space \color{red}{ VS} \space $ $\mathbb{Z}$

Why $\mathbb{Z}^+\times \mathbb{Z}^+$ with $(a1,a2) \preceq (b1,b2)$ if $a_1 < b_1$ or if $a_1 = b_1$ and $a_2 \leq b_2$ is a well-order set but $\mathbb{Z}$ set is not a well-ordered one? I read ...
0
votes
0answers
29 views

Does total order imply linearisation

Suppose $X$ is a totally ordered set. Does this mean that $X$ can always be linearised? I mean can $X$ be always written in a linear order like $\mathbb{R}$ ? I came across this question when I was ...
2
votes
1answer
74 views

Characterizing affine subspaces order-theoretically

Let $V$ denote a real vectorspace and $\mathrm{Con}(V)$ denote the poset of convex subsets of $V$. The goal is to identify those elements of $\mathrm{Con}(V)$ that happen to be affine subspaces of $V$ ...
2
votes
1answer
63 views

What do we call well-founded posets whose elements have a unique height?

What do we call those well-founded posets $P$ with the property that for every $x \in P$, all maximal chains in the lowerset generated by $x$ have the same length? Examples: The set of all finite ...
1
vote
1answer
47 views

Zorn's lemma converse? (Context: Maximal proper subgroups)

So, in my qual prep class a pretty simple question popped up: "Prove that for any nontrivial finite group there exists a maximal proper subgroup." So of course, my natural inclination was to ...
2
votes
3answers
29 views

Order by inclusion

Given the set $E = \{a,b,c\}$, order the power set of $E$ (all subsets) by inclusion. I think the order would be $\varnothing$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a,b\}$, $\{a,c\}$, $\{b,c\}$, ...
2
votes
2answers
65 views

$|\alpha\times\alpha|=|\alpha|$ for infinite ordinal $\alpha$, definably

I am trying to prove Proposition 1.7 of http://math.bu.edu/people/aki/7.pdf: Proposition 1.7 (Halbeisen–Shelah). If $\aleph_0\le|X|$, then $|{\cal P}(X)|\not\le|{\rm Seq}(X)|$. In words, ...