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

0
votes
1answer
18 views

If I have $N_k\subset \Bbb N$ a finite subset of $k$ elements, what is the justification to saying I can relable it's elements so they are ordered?

If I have $N_k=\{l_1,l_2,...,l_k\}\subset \Bbb N$ a finite subset of $k$ elements, what is the justification to saying I can relabel $l_i$ into the elements $p_j$ where $p_a<p_b \forall a<b\leq ...
1
vote
2answers
34 views

Orders with no anti-symmetry requirement?

A ordered/partially ordered set is required to satisfy the $x \leqslant y$ and $y \leqslant x$, $\implies x=y$ (antisymmetry) axiom. Are there any viable theories where this condition is weakened? ...
6
votes
1answer
106 views

Is there a non-trivial countably transitive linear order? [on hold]

A linear order $<$ on a set S is countably transitive iff, whenever A and B are order-isomorphic countable subsets of S, there is an order-automorphism of S which maps A onto B. Does such an order ...
1
vote
1answer
21 views

Representing numbers by quasilexicographic ordered strings, formula for size of conversion between different alphabets

Let $X_r = \{ 0, 1, \ldots, r-1 \}$ and $X_b = \{ 0, 1, \ldots, b-1 \}$ be two finite alphabets with order's given by their numerical value. Consider the quasilexicographic (or shortlex) order on ...
2
votes
2answers
29 views

Order-preserving map between $X^*$ and $\mathbb N$ for some finite set $X$

Let $X = \{ 1, \ldots , r \}$ be $r$ symbols with $1 < 2 < \ldots < r$ and define on the set of all finite sequences $X^*$ the lexicographic ordering as given here on Wikipedia. Is it ...
1
vote
1answer
16 views

Lattices and Hasse diagrams

I would like to know which is the exact difference between lattices ans Hasse diagrams. In some cases, such as when lattices are used to represent maximal and minimal ideals, it seems to me that both ...
2
votes
2answers
43 views

Proof that any finite subset of a lattice has a supremum.

Let $C\subseteq D$ where $C = \{c_{1}, c_{2},\ldots, c_{n}\}$ and $D$ is a lattice. I believe that this supremum is $((c_1 \vee c_2)\vee c_3)\vee \ldots \vee c_n)$ (sorry about the notation). However ...
8
votes
2answers
86 views

Is the following a characterization of $\Bbb Q\cap\cal C$, where $\cal C$ is the Cantor set?

Let $A$ be an ordered set, with the following properties: $A$ is countable $A$ has a least and greatest element Between any two points with successors are points without successors; between any two ...
0
votes
2answers
23 views

Define a relation $D_n$ on $S$ by $xD_ny$ if and only if $x\mid y$. Determine if it's a poset.

Here is the question I am currently working on (screenshot): I'd appreciate some suggestions/guidance for part (a), proving that $D_n$ is a partial order. Reflexive: Let $x \in \mathbb{Z}$ ...
1
vote
1answer
59 views

Prove $\mathbb Q( \sqrt2)$ has only two orderings

I'm having trouble showing that there are only two unique orderings of $\mathbb Q$ restricted to square root of two. I can show that the rationals are ordered, but I can't seem to figure out how to ...
1
vote
0answers
15 views

Explain the compactness relation for elements of dcpos and also in a category if objects

The way below relation is used to define compact elements in a dcpo. Can someone explain compactness and an object way below itself. Also, when we abstract this relation to categories, where the ...
2
votes
1answer
38 views

Example of a Well-Ordered Class that is not Proper

I am currently studying well-ordered classes in the context of NBG set theory and I am trying to find a well-ordered class that is not proper. Here is the relevant definition of the terminology ...
4
votes
1answer
50 views

Any two countable atomless Boolean algebras are isomorphic

How to prove that Any two countable atomless Boolean algebras are isomorphic. This is an exercise of Jech - Set theory book for which I have some difficulty.
10
votes
5answers
391 views

Foundation of ordering of real numbers

This might be a silly question, but what is the mathematical foundation for the ordering of the real numbers? How do we know that $1<2$ or $300<1000$... Are the real numbers simply defined as ...
3
votes
1answer
35 views

Size of Totally Ordered Set with Countable Predecessors

Assume Choice. Let $S$ be a set, and $\trianglelefteq$ be a total order on $S$. If for all $s \in S$, the set $\{t:t\trianglelefteq s\}$ is countable, what are the possible cardinalities of $S$? ...
2
votes
1answer
25 views

$X$ connected in the order topology $\Rightarrow$ every $A\subset X$ that has an upper bound has a supremum

I have to prove $X$ connected in the order topology (w.r.t. a linear order <) $\Rightarrow$ every $A\subset X$ that has an upper bound has a supremum My attempt: Reason by contradiction: ...
0
votes
1answer
24 views

Filters and filter bases in order theory

Hi I would like to confirm the following ideas regarding filters in order theory: By definition I have that a filter is a subset of a poset $(P, \leq)$ which satisfies: $\mathcal{F}$ is non-empty. ...
3
votes
2answers
56 views

Showing $\lg(n!) = \Omega(n\lg n)$

I saw this equation in "Introduction to Algorithm" 3th edition in page 58 : $$\lg(n!) = \Theta(n\lg(n))$$ If $\lg(n!) = \Omega(n\lg(n))$ and $\lg(n!) = O(n\lg(n))$ then we can prove that. I can ...
3
votes
1answer
52 views

Order for sets in the real line

Consider the sets $[0,1]$ and $[1,2]$. I want to say that $[1,2]$ is greater than $[0,1]$. Is there a set order such that $$A \geq B \quad \text{if} \quad \inf A \geq \sup B.$$ What is the name of ...
0
votes
1answer
22 views

$R$ well-founded relation and $\forall y$, $\{x:xRy\}$ is finite implies $\forall y$, $\{x:xR^t y\}$ is finite (where $R^t$ is the transitive closure)

I am interested in proving the titular claim: $R$ well-founded relation and $\forall y$, $\{x:xRy\}$ is finite implies $\forall y$, $\{x:xR^t y\}$ is finite (where $R^t$ is the transitive closure) ...
1
vote
1answer
50 views

Topology on partially ordered set

Let $(X, \leq )$ be a partially ordered set. How would you define a topology on $X$ such that the closed sets are precisely the order-closed sets? Where $B \subset X$ is order-closed if ...
3
votes
3answers
65 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 ...
1
vote
0answers
7 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
192 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
24 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
29 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
19 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
40 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
41 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
26 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
56 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
37 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 ...
1
vote
2answers
45 views

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

Note to viewers of this question: I made two attempts to construct an isomorphism between [0,1) and a larger interval. My original posting had some typos that made the two answers I received hard ...
2
votes
2answers
57 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
112 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
132 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
164 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
11 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
44 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
15 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
53 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
24 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
61 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
25 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
64 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
28 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
1answer
40 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 ...