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
20 views

show sets are or aren't bounded in an linear ordered set

Let $X$ be a linearly ordered set, and $A\subset Y\subset X$. Can it happen that $A$ is bounded in $X$, but not in $Y$? Can it happen that $A$ is bounded in $Y$, but not in $X$? I'm ...
0
votes
2answers
41 views

Is there a strict superset of the reals with total order?

The ordinals immediately come to mind, but I am mainly interested if there are new elements bounded between two real numbers $[a,b]\subseteq\mathbb{R}$ that can be added to the reals while preserving ...
0
votes
1answer
18 views

How to estimate the similarity of two DAGs

Given two DAGs $G_1(V,E_1)$ and $G_2(V,E_2)$ over the same vertex set $V$. Is there any well-studied measures to check the similarity between $G_1$ and $G_2$? I know the definition of similar is too ...
0
votes
1answer
31 views

Difference between cofinal map and cofinal

In this note I read, the cofinal map is defined as, Let $\mathbb D´$ and $\mathbb D$ be two directed sets, $f: \mathbb D´ \to \mathbb D$ is a cofinal map, if $M$ is cofinal in $\mathbb D´$, then ...
1
vote
1answer
52 views

Ordered set and ordered field

To be clear, let me use "$=$" to mean the same element in a set, and "$\sim$" to mean neither "$>$" nor "$<$" in an order. In an ordered set even if $x\ne y$, we can still set $x\sim y$, right? ...
0
votes
1answer
53 views

Order topology on a subset may be weaker (but never stronger) than the subspace topology

If $X$ is a linearly ordered set, the topology $\mathcal{T}$ generated by the sets $\{x:x<a\}$ and $\{x:x>a\}$ ($a \in X$) is called the order topology. Suppose $Y$ is a subset of $X$, show ...
0
votes
1answer
42 views

Characterisation of the order topology on a linearly ordered set

If $X$ is a linearly ordered set, the topology $\mathcal{T}$ generated by the sets $\{x:x<a\}$ and $\{x:x>a\}$ ($a \in X$) is called the order topology. If $a, b \in X$ and $a<b$, there ...
0
votes
0answers
27 views

Prove that $\mathscr F^+ = \mathscr J^+$ and $a \in \mathscr J^+$ iff there exists a filter

Let $\mathscr F$ a filter and let $\mathscr J = \mathscr F^c$ be an ideal dual to $\mathscr J$. Denote $\mathscr F^+ = \{a : (\forall x \in \mathscr F)[a \land x \neq 0]\}$ and $\mathscr J^+ = \{a:a ...
0
votes
0answers
13 views

A finite subset of an ordered set contains an $\inf$ and $\sup$ [duplicate]

Let S be an ordered set. Let A ⊂ S be a nonempty finite subset. Then A is bounded. Furthermore, inf A exists and is in A and sup A exists and is in A. Hint: Use induction. How do I use induction to ...
1
vote
1answer
31 views

Are the maps f(n)=3n and h(x) = the greatest natural number ≤ x residuated?

I have issues with proving the next things: Let $P = ⟨N,\le⟩$ the poset of the natural numbers with the standard order. Consider the map $f : N → N$ defined by $f(n) = 3n$. Is $f$ residuated? Let $P ...
1
vote
0answers
17 views

Exponentiation on order types

How is exponentiation defined on order types? We know that $2^\omega=\omega$. What is $2^{\omega^*}$? Is it $\omega^*$? $\eta$? $\lambda$? I'm guessing $\eta$, but I'm not sure. $\omega$ is the ...
2
votes
1answer
39 views

Are $((0,1]\cap\mathbb Q)\times\mathbb Q$ and $\mathbb Q \times([0,1)\cap\mathbb Q)$ order isomorphic?

The ordering here isn't specified but I assume it's lexicographic. I think the answer is yes. My reasoning is the following: Neither sets have a least or a greatest element because the second ...
1
vote
0answers
58 views

Universal set for linearly ordered sets of given cardinality

It is easy to see that every infinitely countable linearly ordered set embeds into Q (rational numbers) with its linear order.("Linear order"="total order". All embeddings are assumed to preserve ...
4
votes
2answers
190 views

Understanding proof of Hartogs’ Theorem on Set Theory

I'm trying to understand the proof of the Hartogs’ Theorem on page 100 of this book. My especific question is: If we have for each set $A$ $$\mathrm{WO}(A)=\{ (U,\leq_{U}) \, | \, U\subseteq A \, ...
0
votes
1answer
46 views

Condition to be a prewellordering.

I'm trying to do the problem 7.17 on th book Notes of Set Theory of Moschovakis. First I will define what is a prewellordering: A prewellordering on a set $A$ is any relation $(\lesssim) ⊆ A×A$ ...
1
vote
1answer
38 views

Example of a map between two lattices such that the map is an order embedding but not a lattice embedding

Is there an example of a map $h$ between two lattices such that $h: L_1 \rightarrow L_2$,that is order embedding from $L_1$ to $L_2$ but not an embedding when they are taken as algebras? I would ...
1
vote
1answer
61 views

Question about maps in partially ordered sets

I am struggling with a proof related to the mapping of posets. Let $P_1$and $P_2$ are posets, and $f$ an order preserving map from $P_1$ to $P_2$. $$g(Z):= f^{-1}[Z]$$ $g$ goes from the set of all ...
2
votes
2answers
194 views

Prove that every totally ordered set has a well-ordered cofinal subset

I thought this was easy until I realized that for a set to be well-ordered, EACH of it's non-empty subsets must have a least element. Let $A$ be a non-empty totally ordered set. Let $x_0$ be some ...
2
votes
1answer
61 views

What is the relationship between the cofinality and well orders?

Suppose $A$ is an infinite linear order with cardinality $\kappa$, and take the family $\langle A_{\alpha}: \alpha < \kappa \rangle$, define like this: $$A=\bigcup_{\alpha < \kappa} ...
1
vote
0answers
74 views

Partial order of a finite set is an intersection of a finite number of linear orders of this set

I am trying to prove that every partial order of a finite set is an intersection of a finite number of linear orders of this set. Can this be proved using these observations: a partial order has a ...
0
votes
1answer
55 views

Equivalent forms of axiom of choice

I'm currently reading Dugundji's Topology book. Exercise 2 of section 2 in page 58 gives 4 equivalents of Zorn's lemma. I'm only interested in a) and c) (I won't copy the whole thing cause it's too ...
1
vote
1answer
22 views

Determine which of these sets is a lattice

I'm currently reading Dugundji's Topology's book. Exercise 4 in chapter 2 says (omitting a part that is irrelevant to the question) A partially order set is a lattice if each pair of its elements ...
3
votes
2answers
56 views

Are $[0,1]\times[0,1]$ and $[0,1]$ order isomorphic?

The ordering on the first set is reverse lexicographic and the order of the second set is the usual ordering of reals. My intuition tells me that the answer is no. The only isomorphism between those ...
0
votes
2answers
31 views

Total order function property

This may have been asked before but it's difficult to search for. Suppose that $|A|=n$ and that $R$ is a total order on $A$ (not a strict order). Define $g:A \to I_n$ by $$ g(a) = |\{x \in A ~|~ ...
0
votes
0answers
19 views

Least finite linear orders with same theory in monadic second order logic.

Today I want to ask a relaxed version of my last question. So if somebody finds a solution to that question he will immediately get a solution for this question here. Question. Let $m<\omega$ ...
2
votes
0answers
42 views

When do finite linear orders have the same theory in MSO?

Let $\mathfrak A$ and $\mathfrak B$ be finite linears orders and $m<\omega$. Then we have $$\mathfrak A \equiv^m_{FO}\mathfrak B \quad\text{iff}\quad |A|=|B| \,\, \text{or}\,\, |A|,|B|\ge 2^m-1.$$ ...
1
vote
2answers
124 views

Counterexample to the Hausdorff Maximal Principle

The Hausdorff Maximal Principle states: Every partially ordered set $\left(X,\leqslant\right)$ has a linearly ordered subset $\left(E,\leqslant\right)$ such that no subset of $X$ that properly ...
1
vote
1answer
48 views

Mathematical structures with a canonical partial order

I like order theory very much, and am always excited to discover mathematical structures that can be intrinsically endowed with a partial order. "Easy" examples are $T_0$ topological spaces (with $x ...
1
vote
1answer
26 views

Is it an axiom that the inequalities are translation-invariant or can we prove it?

I was thinking about the inequalities on the set of real numbers. To me and everyone else, it's been taught that an inequality is translation-invariant, i.e.: $x < y \implies x + c < y + c ...
2
votes
1answer
58 views

Order preserving injection from first uncountable ordinal to the real numbers

Can there be an ordering preserving (1-1) map $f \colon \langle\aleph_1,\in\rangle \rightarrow \langle\mathbb R, \lt\rangle$? I remember that if $f$ is order preserving then consider the following ...
2
votes
2answers
37 views

Largest, smallest, LUB and GLB of the relation $\leq$on $ \left\{\frac{2n + 1}{n + 1} \mid n \in \mathbb{N}\right\}$

I have to fin the largest, smallest, lower/least upper bound (LUB) and greatest lower bound (GLB) element of the relation $\leq$ on the following set: $$S = \left\{\frac{2n + 1}{n + 1} \mid n \in ...
0
votes
1answer
51 views

Number of upward closed subsets

I am looking for an algorithm of some sorts that can produce the total number of upward closed subsets in a partial ordered set. Let $\langle P,\leq\rangle$ be a (finite) partial ordered set, then an ...
2
votes
1answer
26 views

How to sort 4 (or more) values with non-piecewise functions?

This question was inspired by this: Finding a non-piece wise function that gives us the $i$'th largest number. My question is how to do this for four or more values. In other words, given 4 ...
4
votes
1answer
91 views

Order type of real analytic monotonic functions ordered by eventual domination

Let $\mathcal F$ be the set of all functions $\mathbb R^+\to\mathbb R$ that are: real analytic on $\mathbb R^+$, monotonic on $\mathbb R^+$, and having derivatives of any order that are also ...
0
votes
1answer
79 views

If $R$ is a strict partial order prove that is asymmetric

Suppose $R$ is a relation on a set $A$, and $R$ is asymmetric if: $\forall x \in A$ $\forall y \in A$ $((x, y) \in R \rightarrow (y, x)\not \in R)$ The first point of the exercise was to demonstrate ...
1
vote
2answers
41 views

Similarities when adding a new point to a poset.

I'm trying to solve the problem 7.3 of the book Notes on Set Theory written by Moschovakis. Basically, I have to prove that for every poset $P$ we have $\mathrm{Succ}(P)=_o P+_o [0,1)$, were ...
3
votes
3answers
62 views

Why $B=\{\frac{1}{n} \mid n \in \mathbb{Z^{+}}\}$ does not have a smallest element?

I am studying from some slides where there's written that $B=\{\frac{1}{n} \mid n \in \mathbb{Z^{+}}\} = \{1,1/2,1/3,1/4, \mid\}$ does not have a smallest element but it does have a g.l.b (infimum) ...
1
vote
2answers
31 views

Minimals in partially ordered sets

In a subset $Y$ of a partially ordered set $(X, \leq)$ a minimal element is an element $a \in Y$ such that $(\forall y \in Y)\ y \leq a \Leftrightarrow y = a$ However in this diagram ...
1
vote
2answers
168 views

A question about $\aleph_1$-dense sets and the basis problem for uncountable linear orderings

I have a question which I have been unable to find a reference for and which I explain as follows: Recall that a set of reals $X$ is $\kappa$-dense if between any two real numbers there are exactly ...
2
votes
1answer
49 views

Lattice of interval

I would like to create a lattice of intervals of integers, but I don't know how to 'draw'(Hasse diagram) it. An interval looks like: [1,4] or ]-Inf,3] for example. I'm having difficulties deciding ...
0
votes
1answer
33 views

partial order, sets

Please help to solve the following: The set is partially ordered with respect to the “less than or equal to” relation, ≤, for real numbers. In following case, determine whether the set has a ...
0
votes
0answers
24 views

Are there general conditions under which minimal generating sets can be expected to exist?

There exist algebraic structures $X$ with no minimal generating set. For example, $\mathbb{Q},$ viewed as an Abelian group. There also exist algebraic structures whose every generating set includes ...
2
votes
2answers
80 views

Subsets of the rationals order isomorphic to transfinite ordinals

Let $\langle\mathbb Q,\lt\rangle$ be the set of rational numbers with the usual $\lt$ ordering. Find subsets $A$ and $B$ of $\mathbb Q$ which, with the usual ordering, are order isomorphic to the ...
3
votes
0answers
29 views

For which countable successor ordinals $\alpha$ is the reverse order isomorphic to the ideals of a PID ordered by inclusion?

Let $\alpha$ be a countable successor ordinal and $\alpha^{\mathrm{op}}$ the reverse order. For which $\alpha$ is there a commutative principal ideal ring $R$ such that the ideals of $R$ form a chain ...
1
vote
2answers
71 views

Does Green's $\mathcal{J}$-relation define a total order on the equivalence classes?

In a semigroup $S$ we define $a\le_\mathcal{J} b$ iff $a=xby$ for some $x,y\in S^1$. Defining $a\equiv_\mathcal{J} b$ by $a\le_\mathcal{J} b$ and $b\le_\mathcal{J} a$ gives a partial order on ...
1
vote
2answers
50 views

Basic question on set ordering

I have some difficulties with a question from Jech's book (Introduction to Set Theory). Any help would be appreciated. Give examples of a finite ordered set $(A, \leq)$ and a subset $B$ of $A$ so ...
5
votes
1answer
103 views

Is there a universal mapping property satisfied by the disjoint union of totally ordered sets?

It is proved in another post that the product and coproduct do not exist in the category of totally ordered sets (except in some trivial cases). (In this post I will only consider the category TOrd, ...
5
votes
1answer
66 views

Scott continuity on powerset

I am looking for the name of the class of functions $f:\mathcal P(A)→\mathcal P(A)$ that are monotone and that are characterised by their image on finite subsets, i.e. the functions $f$ satisfying the ...
1
vote
3answers
80 views

Origin of min/max notation

Here I am referring to the notation $x \wedge y = \min \{ x,y \}$ and $x \vee y = \max \{ x,y \}$. These seem to reference the corresponding usages in logic, where $\wedge$ means "and" and $\vee$ ...
4
votes
1answer
125 views

Statements comparable with Axiom of Choice in ZF

Let $AC$ denote any fixed statement of the Axiom of Choice in $ZF$. Consider the set of statements $\phi$ in the language of $ZF$ such that either $ZF+\phi$ proves $AC$ or $ZF+AC$ proves $\phi$. The ...