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

1
vote
1answer
37 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
60 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
180 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
60 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
70 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
53 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
55 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
30 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
108 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
47 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
36 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
48 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
25 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
90 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
75 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
166 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
78 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
66 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
95 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
65 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
74 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
123 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 ...
2
votes
3answers
69 views

Name of an axiom

What's the name of the following axiom: Let $A$ and $B$ be sets of real numbers, and $(\forall a\in A\text{ and }\forall b\in B)a \leq b$. Then $\exists c\in\mathbb R$ such that $(\forall a\in A\text{ ...
4
votes
2answers
36 views

Definition of ordered ring/field

One way to define an ordered ring is as a ring with a total order $\leq$, satisfying $x\leq y\implies x+z\leq y+z$; $0\leq x$ and $0\leq y\implies 0\leq xy$. Does it hurt to replace 1. with the ...
3
votes
2answers
64 views

Directed sets to describe a topology with nets.

I'm studying some things related to ultrafilters on metric and topological spaces and trying to prove theorem in a general setting, so the following question came to my mind. Let $S$ be a ...
0
votes
0answers
28 views

How to formalize a lattice in a graph

Given directed a graph: G = (V, E). How to use algebra symbols to express a lattice in G? where reachability stands for partial order, i.e. in the lattice ...
6
votes
2answers
74 views

Gallian: is it true that the well-ordering principle can't be proven from properties of arithmetic?

I just started reading Gallian's Abstract algebra and on page 3 it says "An important property of the integers...is the so-called Well Ordering Principle. Since this property cannot be proved from the ...
0
votes
1answer
92 views

Hasse diagram question about relations

I have the following Hasse diagram below, the question is given specific generalised quantifiers I have to list the subsets of {a,b,c,d} which the quantifier corresponds to. I have completed the ...
4
votes
3answers
160 views

Munkres Section 10: How are these order types different?

Let $\mathbb{Z}^+$ denote the set of all positive integers in the usual order, let $n$ be a positve integer, and let the following sets have the dictionary order: $\{1, \ldots, n \} \times ...
1
vote
0answers
59 views

Generalized semilattice morphism

Join-semilattice morphism from a join-semilattice $\mathfrak{A}$ to a join-semilattice $\mathfrak{B}$ is a function $\alpha$ conforming to the formula $\alpha(X\sqcup Y) = \alpha X\sqcup\alpha Y$ ...
2
votes
1answer
48 views

Difficulty understanding “antichains”

I'm having a difficulty understanding the concept of "antichains". An antichain in a poset $P$ is a subset $C \subseteq P$ such that no 2 elements are comparable I understand the definition, ...
0
votes
0answers
12 views

Can we distinguish direct from transitive partial orders

If I have a set L and a partial order ≤ defined on L, and (L, ≤) is a lattice. We know that ≤ is transitive, i.e. if l1 ≤ l2 and l2 ≤ l3 then l1 ≤ l3. Well. I ...
3
votes
2answers
42 views

How to prove that if R is a partial order then also $R^{-1}$ is also a partial order?

My guess was to divide the problem into 3 cases: prove that $R^{-1}$ is reflexive, antisymmetric and transitive. To prove that $R^{-1}$ is reflexive, I did: If $R$ is reflexive, that follows that ...
0
votes
0answers
30 views

Does this combinatorial object have a name?

I have come across the need to with subsets of meet-semilattices. Specifically, my setting is that I need posets that have a meet operation that is unique when defined, but is not necessarily defined ...
1
vote
2answers
41 views

Prove the relation on $\Bbb N \setminus \{0,1\}$ is a partial order

I'm a bit new to this material and trying understand some problem I'm solving Let $R$ be a relation on the set set = $ \{ N \setminus \{ 0,1\}\} $ that's defined like this: $aRb$ if there is an ...
0
votes
0answers
46 views

Are the face posets of CW-complexes Eulerian?

Suppose we had a CW-complex $X$ with decomposition $X_{i}$ Is its face poset, consisting of cells and covers generated by the attachment of cells to one another, an Eulerian poset? What would be the ...
3
votes
2answers
98 views

Are the Hyperreals complete?

Since $^*\mathbb{R}$ does not form a metric space then it can not satisfy the Cauchy conditions for completeness. However, my intuition is telling me that it would satisfy conditions of completeness ...