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

4
votes
1answer
112 views

Is the class of countable posets well-quasi-ordered by embeddability?

The question is in the title. Here "$P$ embeds into $Q$" means there is a function $f : P\to Q$ such that for all $p,p'\in P$, $p \le_P p'$ if and only if $f(p) \le_Q f(p')$. A well quasi order $W$ ...
-2
votes
2answers
192 views

Well-ordered sets, properties of an element that is not largest in the set

Can anyone please help me in this question: $(X,\leq )$ is a well-ordered set. $\forall x\in X$, either $x$ is the largest element of $X$ or there exists $y\in X$ such that (i) $x<y$ and ...
1
vote
3answers
991 views

well ordered and totally ordered set [duplicate]

Can anyone please help me in this? Prove that every well ordered set is a totally ordered set. To start this proof will this be sufficient: Let $x_1, x_2 \in X.$ Let $A=\{ x_1, x_2 \}$. If ...
6
votes
2answers
585 views

The order type of the rationals.

Herewith another mind-numbingly naive question from a reader of philosophy. My question concerns the order type of the rational numbers. Omega squared seems a natural first choice, but obviously ...
0
votes
1answer
97 views

Are all atoms of the lattice of filters principal filters?

Are all atoms of the lattice of filters (ordered by set-theoretic inclusion) principal filters? Note that atoms of this lattice are not ultrafilters (ultrafilters are atoms of the dual lattice).
0
votes
1answer
28 views

Both atoms and co-atoms in a lattice

Is there an example of a lattice (or just a poset) for which both atoms and co-atoms are useful?
2
votes
3answers
82 views

A basic question on the definition of order

In the first chapter of Rudin's analysis book "order" on a set is defined as follows : Let $S$ be a set. An order on $S$ is a relation, denoted by $<$, with the following two properties : (i) If ...
14
votes
2answers
285 views

The preorder of countable order types

Consider the set $\mathcal{O}$ of order types corresponding to all posets of cardinality at most $\aleph_0$. The set $\mathcal{O}$ is a preorder under embeddability of its elements (note that some ...
1
vote
1answer
67 views

Partially ordered set Question : $R$ relation on $\mathbb {N}$ iff $n\in \{1,5,5^{2},\dots,5^{k}\}$ , $x=n\cdot y$

I`m trying to prove that this relation is partially ordered set: $R$ relation on $\mathbb {N}$ iff $n\in \{1,5,5^{2},\dots,5^{k}\}$ and $x=n \cdot y$ the condition for partially ordered set are: ...
1
vote
1answer
97 views

number of antichains and number of downsets

This question is taken from the book Introduction to Lattices and Order by Davey and Priestley. Question 14 of Chapter 1. Definition : If $P$ is and ordered set and $Q\subseteq P$, then $Q$ is a ...
1
vote
2answers
177 views

Partially ordered set Question : $A=\{1,2,3,4,5,6\}$ ,$R =\mathcal P(A) \times \mathcal P(A) $

I`m trying to prove that this relation is partially ordered set: $A=\{1,2,3,4,5,6\}$ $R =\mathcal P(A) \times \mathcal P(A) $ $(B,C)R(D,E) \Longleftrightarrow (B \subset D) \vee ((B=D)\wedge(C ...
3
votes
0answers
168 views

Every subset of a poset has an inf implies every subset has a sup

P is a partial order with $\leq$, and L and U are the sets of all lower and upper bounds of A I already know that if every nonempty subset with a lower bound has an infimum, then every nonempty ...
8
votes
1answer
181 views

What kind of category is a cyclically ordered set?

Background: A preorder is a binary relation $\leq$ which is reflexive and transitive. We can write the transitive property as ${\leq}(a,b)\wedge{\leq}(b,c)\to{\leq}(a,c)$. There are additional axioms ...
2
votes
1answer
151 views

Completion of a linear order that is a dense subspace of a compact space.

Suppose $D$ is a linearly ordered space which is densely embedded in a compact Hausdorff space $K$. What can we say about the relation between $K$ and $\overline D$, the completion of $D$. Is one a ...
3
votes
0answers
57 views

How can we define “trivially orthogonal” groups?

In any lattice-ordered group, we say that two elements are orthogonal if their meet is 1. I've been thinking of groups who have only "trivial" orthogonal relations, i.e. $x\perp y\implies x=1$ or ...
2
votes
2answers
61 views

Order structure of asymptotics

Consider the set $A = \{\theta(f) \mid f : \mathbb{R} \rightarrow \mathbb{R},\;f\,\text{non-decreasing}\}$ where $\theta(f)$ denotes the set of functions which are asymptotically within a constant ...
2
votes
2answers
257 views

Prove that $\succeq = \bigcap L \left(\succeq \right)$ - understanding elementary order theory

Dear reader of this post, I am working on a elementary question on order relations. I would be very glad to receive some guidance since I think understanding this question is important for making ...
0
votes
0answers
43 views

Interval in Product Space

I am reading a paper now that refers to an "interval" in $\mathbb{R}^{[0,1]}$. But what does interval here refer to? Does this mean there is some ordering of the elements in $\mathbb{R}^{[0,1]}$? I am ...
4
votes
2answers
229 views

Dense sets and Suslin Lines

I'm studying Infinitary Combinatorics and need a hint for proofing that every Suslin Line has a $\omega_1$ dense set. I've tried to do something with the set of all subsets of the line of cardinality ...
4
votes
1answer
140 views

If $(W,<)$ is a well-ordered set and $f : W \rightarrow W$ is an increasing function, then $f(x) ≥ x$ for each $x \in W$

I could use a hand understanding a proof from Jech's Set Theory. Firstly, note that Jech defines that an increasing function $f : P \rightarrow Q$ is a function that preserves strict inequalities ...
0
votes
1answer
558 views

Show that a relation is a partial ordering

Show that the relation $R$ on $\Bbb N$ given by $aRb \text{ iff } b = a2^k$ for some integer $k\ge 0$ is a partial ordering.
1
vote
1answer
85 views

Show that the stabilizer is a prime subgroup

We define a subgroup $H$ as being convex if $g\in H\implies h\in H$ for all $1\leq h\leq g$. A convex subgroup $P$ is prime if for any two convex subgroups $X,Y$: $X\cap Y \subseteq P$ implies that ...
2
votes
0answers
116 views

Is there a nice characterization of posets induced by trees?

Define that a tree in $X$ is a set of ordinal-indexed sequences with codomain $X$ that is closed under the operations of restricting to an ordinal. (I do not know if this definition is standard.) ...
1
vote
1answer
43 views

Which sentences are preserved by equivalence of quasi-ordered sets?

Given a quasi-ordered set $(X,\lesssim)$, we can define that for $a,b \in X$ we have $$a \sim b \;\Leftrightarrow\; a \lesssim b \;\wedge\; b \lesssim a.$$ and thereby obtain a partially ordered set ...
10
votes
1answer
267 views

Is this a characterization of well-orders?

While grading some papers and thinking about a question related to well-orders (in particular, pointing a mistake in a solution), I came to think of a reasonable characterization for well-orders. I ...
1
vote
1answer
181 views

If $X$ is well-ordered set, how to prove that $\mathcal{P}(X)$ can be linearly ordered? [duplicate]

I'm having troubles solving the following exercise, proposed in T. Jech, 'Set theory' Exercises 5.4. Let $X$ is well-ordered set then $\mathcal{P}(X)$ can be linear ordered. [Let $X<Y$ if ...
0
votes
1answer
125 views

Show that the theory of densely linear orders and the theory of discrete linear orders are incompatible

I'm trying to prove that the theory of dense linear orders and the theory of discrete linear orders are incompatible by showing that their union is inconsistent. Does anyone know how to do this? Thank ...
4
votes
3answers
790 views

“Any finite poset has a maximal element.” How to formalize the proof that is given?

For fun, I'm reading The Mathematics of Logic, and the author gives the following theorem Theorem. Any finite poset has a maximal element. and a proof thereof. But, I can't figure out how to ...
0
votes
1answer
135 views

Filter properties: Downward directed set and finite intersection property

I have a list of questions concerning the properties of filters: (1) If a finite subset of a poset is downward directed is it necessarily closed under finite intersection? At the very least, if said ...
0
votes
1answer
198 views

The limit elements of well-ordered proper classes

For any well-ordered class $W$ with no maximum element, we can define a successor function $f_W : W \rightarrow W$ by asserting that $f_W(w) = \mathrm{min}\{x > w \mid x \in W\}.$ This allows us to ...
0
votes
1answer
46 views

Open intervals $(x-r;x+r)$ form a filter base on $\Bbb R$

Let $x \in \Bbb R$ and let $\bf B$ be the collection of open intervals $(x-r; x+r)$ where $r > 0$. $\bf B$ is a filter base on $\Bbb R$. Can someone please explain why $\bf B$ is a filter ...
2
votes
1answer
98 views

Are the closed ordinals (apart from $0$ and $1$) precisely the regular cardinals?

Given a partially ordered set $P$, a collection of partially ordered sets, call it $\mathcal{Q}$, and an arbitrary function $f : P \rightarrow \mathcal{Q},$ we can form a new partially ordered set ...
-1
votes
2answers
125 views

Well ordered sets [duplicate]

$(X,\le)$ is totally ordered. How do you prove that if every non empty countable subset of $X$ is well ordered then $(X,\le)$ is well ordered?
8
votes
3answers
452 views

Without appealing to choice, can we prove that if $X$ is well-orderable, then so too is $2^X$?

Without appealing to the axiom of choice, it can be shown that (Proposition:) if $X$ is well-orderable, then $2^X$ is totally-orderable. Question: can we show the stronger result that if $X$ is ...
2
votes
4answers
2k views

Infimum and supremum of the empty set

Let $E$ be an empty set. Then, $\sup(E) = -\infty$ and $\inf(E)=+\infty$. I thought it is only meaningful to talk about $\inf(E)$ and $\sup(E)$ if $E$ is non-empty and bounded? Thank you.
1
vote
1answer
65 views

Limit-preserving point-wise maximum

Let $F$ denote the set of monotonic functions in $N^{\infty} \rightarrow N^{\infty}$ (where $N^{\infty}$ includes 0 and $\infty$) ordered by the point-wise application of $\le$ i.e., for $f,g \in F$ ...
3
votes
3answers
143 views

Set $A$ has the cardinality of $\aleph_0$. Prove some properties of partial order $ \langle \mathcal P (A), \subseteq \rangle$.

I try to solve the following task: Set $A$ has the cardinality of $\aleph_0$. The truth is that in the partial order $ \langle \mathcal P (A), \subseteq \rangle$: (answer true or false) a) ...
4
votes
2answers
226 views

Good resource to learn transfinite induction and/or recursion?

I'm currently reading John H. Conway's On Numbers and Games, but without a good understanding of transfinite induction and/or recursion, progress is very slow. What's a good resource for learning ...
1
vote
1answer
120 views

Is there a topology with respect to which a poset is connected iff its topologically connected?

A poset $P$ is said to be connected iff for all $x,y \in P$ we can 'zigzag' from $x$ to $y$ in finitely many steps. That is, iff for all $x,y \in P$ there exists a finite sequence $a : n \rightarrow ...
1
vote
3answers
207 views

Functional equivalence relations between subsets using banking ordering?

How do I set up equivalence relationships for subsets of a set of integers, such that subsets are only equivalent if they possess the same elements (and use banking ordering described below)? I am ...
2
votes
1answer
67 views

identity element for partial orders

I am given (possibly total) order $\phi$ (represented as a directed acyclic graph), how can I construct an identity element $E_I$ for the order (i.e. $\phi$ $\otimes$ $E_I$=$\phi$)? let's assume ...
5
votes
1answer
107 views

Prove that $\dim(X,\succsim)\leq|X^2|$ - A starting point for a journey into order theory

During the last week I kept on thinking about what looked an easy problem at a first glance. Let $(X,\succsim)$ be a preordered set, and define $\mathcal{L}(\succsim)$ as the set of all complete ...
1
vote
0answers
67 views

Intuition behind prime subgroups

In any lattice ordered group, we say that a convex subgroup $P$ is prime if for any two convex subgroups $X,Y$: $X\cap Y \subseteq P$ implies that $X\subseteq P$ or $Y\subseteq P$. This is analogous ...
1
vote
1answer
30 views

Resource allocation with minimal differences

Let $N$ be a finite set. Let $\prec$ be a strict partial order over $N$. I am interested in designing a function $f : N \to \mathbb{R}$ such that: $\sum_{n_i \in N} f(n_i) = 1$ $\forall i,j : n_i ...
1
vote
0answers
65 views

Dimension of proset - the case of $\Delta_X$ and $X^2$

I juse met the defiition of dimension of proset and I found myself stuck on a question (actually I am having various troubles with it, so the one I am asking is only one part of the problem I found). ...
1
vote
1answer
22 views

Show $g^{-1} \wedge h^{-1}=(g\vee h)^{-1}$

Glass' Partially Ordered GroupsLemma 2.3.2 says: Let G be a p.o. group and $g,h\in G$. If $g\vee h$ exists, then $g^{-1} \wedge h^{-1}=(g\vee h)^{-1}$ Proof: If $f\leq g^{-1},h^{-1}$ then ...
0
votes
1answer
36 views

Show that $\langle G^+\rangle=G$ in a directed group

Lemma 2.1.8 of Glass' Partially Ordered Groups states: $G$ is a directed group if and only if $\langle G^+\rangle=G$ (where $G^+=\{x:x\geq1\}$) This doesn't make any sense to me. For example, ...
1
vote
2answers
45 views

Quasiorders and their associated partial orders

Consider a quasiordered set $Q$ (order relation $\lesssim$) and define an equivalence relation in the usual way. $$x \sim y \quad \Leftrightarrow \quad x \lesssim y \,\mbox{ and }\, y \lesssim x$$ ...
5
votes
2answers
190 views

An uncountable famliy in $2^\omega$ linearly ordered by inclusion without passing to $2^{\Bbb Q}$.

I was solving the problem of finding an uncountable, linearly ordered subset of $2^\omega$ ordered by inclusion. I was having a lot of trouble before I realized that I can substitute anything ...
4
votes
3answers
157 views

Which ordinals embed in $2^\omega$ ordered by inclusion?

Which ordinals can be embedded in the power set of $\omega$ ordered by inclusion? I see that $\omega\cdot\omega$ can (and therefore anything less than that): we can partition $\omega$ into $\omega$ ...