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
0answers
39 views

Subbase for a topology defined by a family of closed sets?

Let $X$ be a set and $\mathcal{T}$ the smallest/weakest/coarsest topology containing some family $\left\lbrace C_i\right\rbrace_{i\in I} $ of sets declared to be closed. This is well-defined since ...
0
votes
1answer
27 views

Dimension of a LOTS in $\mathbb{R}^2$

Equip $\mathbb{R}^2$ with the lexicographic order $(x_1,y_1) < (x_2,y_2)$ iff $x_1 < x_2$ or $x_1 = x_2 \Rightarrow y_1 < y_2$. Consider the induced order topology generated by the subbase ...
0
votes
1answer
31 views

Proving that $\sim$ is an equivalence relation

I have the following theorem I need to prove: Let $R$ be a quasi-order relation on a set $X$, and let $\sim$ be defined by $$x\sim y \;\;<=>\;\;(x,y)\in R\;\;\text{and}\;\;(y,x)\in ...
1
vote
0answers
28 views

Can a partially ordered set always be partitioned by its chains?

I would like any references that discuss how to partition a partially ordered set into subsets such that each subset is a chain in the partial order. For example, I am thinking that any partial order ...
1
vote
1answer
30 views

Understanding comparability in a partially ordered sets with Hasse diagrams

I'm doing a section on directed graphs and Hasse diagrams right now on partially ordered sets, and I'm trying to understand what it means for two elements in a Hasse diagram to be comparable. For ...
4
votes
1answer
48 views

Is there a totally ordered set we can map any other totally ordered set to?

Are there any totally ordered sets $O$ with $|O|\ge|\mathbb N|$ such that for each totally ordered set $S$ with $|S|\le|O|$ there is function $f_S\colon S\mapsto O$ such that $\forall_{x,y\in S}x\le ...
4
votes
1answer
80 views

Reduction of Factoring to Order Finding

Theorem Let $N$ be a general odd number, which written as its prime factorisation is $N = {p_1}^{\alpha_1} {p_2}^{\alpha_2} \dots {p_s}^{\alpha_s}$. If $x$ is chosen uniformly at random from ...
0
votes
1answer
29 views

Do all possible subsets of a partially ordered set map to every element of its MacNeille completion?

Every partial order can be completed with respect to arbitrary meets and joins as a complete lattice by embedding it into its MacNeille completion. My question is the following: does this mean that we ...
2
votes
1answer
68 views

Geometric definitions of infinity

There are several definitions of "infinite set" that are common in set theory. For instance, a set $S$ is finite if there is a bijection between a natural number $n$ and $S$; it is infinite ...
3
votes
1answer
33 views

Is this a valid way of proving the well ordering principle?

The well ordering principle states that every non-empty subset of $\mathbb{N}$ must have a first element (i.e. a minimum). For my proof, I suppose there exists a set $\varnothing \neq S \subseteq ...
0
votes
2answers
13 views

Defining left shift on orderings

The question I propose is this: For an indexing set $I = \mathbb{N}$, or $I = \mathbb{Z}$, and some alphabet $A$, we can define a left shift $\sigma : A^{I} \to A^{I}$ by $\sigma(a_{k})_{k \in I} = ...
0
votes
1answer
26 views

With Axiom of Choice, if $\langle A,\prec\rangle$ is well ordered then A has no subset of order type $\omega^*$

The question is raised when I look at this question which have been asked three years ago. I want to know if the other side of the question is still true or to be more specific :- With Axiom of ...
0
votes
2answers
37 views

Characterization of pre-orders

Let $X$ be an arbitrary set, and $\leq$ be a pre-order on $X$. Does there always exist $u:X\to \Bbb R$ such that $x'\leq x''$ iff $u(x') \leq u(x'')$? If this is not true in general, is that true ...
1
vote
0answers
39 views

Prove that a definition in set theory is sound

I have a problem to show that the following definition is sound. Definition: Let $\Theta_1$ and $\Theta_2$ be order types. We say $\Theta_1 \prec \Theta_2$ If there are order sets $\langle ...
1
vote
0answers
12 views

On the definiton of clone of relations

I am reading A short introduction to clones and I am stuck at this definition ($A$ is a set and $R_A$ the set of finitary relations on $A$) Definition A subset $R\subseteq R_A$ is called a clone of ...
0
votes
0answers
30 views

partially ordered set 2

What the meaning 'directed' ,'cofinal' ,'filtering',and 'chain'.Its about of partially ordered set.And please give me any example? A preordered set $(I, \leq)$ is directed if every finite subset $F$ ...
0
votes
1answer
35 views

partially ordered set

What is the meaning of: $A(x) := \{y ∈ X : x ≤ y\}$ $(x ≤ x$ or $x ∈ A(x)$ for all $x ∈ X)$ $(A ◦ A ⊂ A$, i.e., $x ≤ y, y ≤ z ⇒ x ≤ z$ for $x, y, z ∈ X)$ in the sentences: A preorder or ...
0
votes
0answers
37 views

Upper bound and lower bound(partial order)

I come across a graduate level introduction to real analysis course. In the lecture, the professor firstly define a set A, which is a subset of a partial order set X, for which the relation R1 is ...
1
vote
2answers
39 views

Find the order of this matrix on the group $(GL_{2}(\mathbb{C}),\cdot)$.

I have to calculate the order of the matrix \begin{equation} A= \left( {\begin{array}{cc} i & 0\\ -2i & -i\\ \end{array} } \right) \end{equation} on $(GL_{2}(\mathbb{C}),\cdot)$. ...
1
vote
1answer
47 views

Do ordinal sets exist?

An ordinal is woset, where for all members $a$ in the set, $a$'s segment is $a$ itself. But, the definition of $a$'s segment is: $X_a=\{x\in X:x \subsetneq a\}$ But, given that definition, how can ...
1
vote
1answer
27 views

Basic question about partially ordered sets.

Let $(X,\le)$ be a partially ordered set. Let $x,y,z \in X$. Suppose $x \le y$ and $x \le z$. Then are $y$ and $z$ comparable?
0
votes
1answer
18 views

are these sets isomorphic?

$\le$ is less-than-or-equal relation. Is $\langle\Bbb Q\cap((0,1)\cup(4,5)),\le\rangle>$ isomorphic with $\langle\Bbb Q \cap ((0,1)\cup(4,5)\cup\{2,3\},\le\rangle$ ? They are both totally ...
5
votes
3answers
83 views

What is $\inf\emptyset$ and $\sup\emptyset$? [duplicate]

I was told that $\sup\emptyset=-\infty$ and $\inf\emptyset=\infty$, where $\emptyset$ is the empty set. This seems paradoxical to me as to how supremum can be less than infimum. Is there any proof for ...
0
votes
1answer
35 views

A question about well-ordered subsets of partially ordered sets

Let $S$ be an infinite partially ordered set. Is there a name for the smallest ordinal number which is not ordinally similar to any subset of any chain of $S$? Assume that we are working in ZF. If the ...
-2
votes
1answer
101 views

Real Analysis, using Zorns Lemma

Use Zorns lemma to prove that every finite totally ordered set has a unique minimal element. I know how to use induction to prove it but I am asked to use Zorn's lemma. what I have thus far: Let $X$ ...
3
votes
1answer
54 views

How do we approach a counting exercise from Enumerative Combinatorics (Prof. Stanley's book)?

I am baffled by the first question in the exercise of Chapter 3, Enumerative Combinatorics. I have no idea how to approach it. The question reads: [3] What is the connection between a partially ...
2
votes
1answer
50 views

How is induction related to a well founded set?

I read a proof that went along these lines: "Let $(X, \le)$ be a woset. Let $E$ be a subset of $X$ such that: the minimal element of $X$ is a member of $E$ for any $x \in X$, if $\forall_y[y \lt ...
1
vote
1answer
64 views

Finding the Order of a group and the Order of each element

I am working on a cryptography example problem. The problem is the following: For the group G = < Z26*, x> a) find the order of the group b) find the order of each element in the group c) Is ...
1
vote
1answer
19 views

proving order types to be different

I was reading 'Introductory real analysis' by Komogorov and Fomin and it mentioned in section 3.3 that "ordered sets with same power need not necessarily have same type of order" A counter example ...
0
votes
1answer
43 views

Injection from a Well-Ordered Set to $\mathbb{Q}$

Call a set $W \subset \mathbb{R}$ well-ordered if every non-empty $A \subset W$ has a minimum element. Prove that if $W \subset \mathbb{R}$ is well-ordered, then there is an injection from $W$ to ...
3
votes
3answers
66 views

A question about partially ordered sets and their subsets

I was reading about partially ordered sets and in the book, a theorem was proven. The theorem was that, given an poset, $(X, \le)$ there exists a set $Y$ of subsets of $X$ such that $(X, \le) \cong ...
1
vote
1answer
21 views

Lexicographic order on $\alpha^\beta$ is well-ordered

Suppose that $\alpha$ and $\beta$ are ordinals, and define the following order on $\alpha^\beta$, the set of all functions $\beta\to\alpha$ with finite support: $$f\,R\,g\iff\exists ...
2
votes
1answer
39 views

Find a formula that separate between structure

I have language $ L = \{ < \} $. I have the following structures: $|M| = \{ 1-\frac{1}{m} |m\in Z, m >1\} $ $|N| = \{ 1-\frac{1}{m} - \frac{1}{n} |m,n\in Z, m,n >1\} $ I need to find a ...
3
votes
1answer
40 views

Does any set admit a total order? [duplicate]

Is it true that any set $P$ can be endowed with a total order $"\leq" \subseteq P\times P$?
2
votes
1answer
29 views

Can the same element be greatest and least in a partially ordered set?

I have an exam soon, so I'm just looking at the previous exams and solving every problem I see. So the problem goes like this : $R$ is a partially ordered set(relation) on $A = \{1, 2, 3, 4, 5\}$ ...
0
votes
0answers
35 views

Longest Maximal Chain in a Poset

I'm trying to study posets as part of a larger algorithm I'm creating. At the advice of a colleague, I'm reading Enumerative Combinatorics by Richard Stanley, but despite the length of the chapter, he ...
1
vote
1answer
55 views

Consistent choice of elements in inverse directed system

Is there some theory related to this... Let $(\{X_\alpha\}_\alpha,f_{\alpha\beta}:X_\beta\rightarrow X_\alpha\}_{\alpha\preceq\beta})$ be an inverse directed system of non-empty sets resp. surjective ...
1
vote
1answer
57 views

finite sequences,linear order, lexicographic order, well order, cardinal

Let $\lambda$ be an infinite cardinal.Consider the lexicographic order on $\lambda^{< \omega}$. Why this order is not a well-order: how may an infinite long descending chain look like? Why every ...
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
40 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
26 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
39 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
51 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
25 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
15 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
38 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 ...