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

maximum and maximal elements

Let B = {(2,4), (4,0), (4,3), (7,3)}. B has the order like the product order of $\mathbb{N} \times \mathbb{N}$ . Then, why B hasn't maximum and why the maximal elements are (2,4) and (7,3)?
1
vote
1answer
27 views

Infinite chain contains a chain order-isomorphic to either the positive integers or the negative integers.

I came across this statement and it is very intuitive to me. I am looking for more information such as a name associated with this theorem or even a more general theorem. Does such a name or more ...
2
votes
0answers
33 views

Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [on hold]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
10
votes
1answer
64 views

Is there a nice well-behaved order isomorphism between the real algebraic numbers and the rationals?

Via Cantor's back-and-forth method we know that the linearly ordered set of all rational numbers and the linearly ordered set of all real algebraic numbers are isomorphic. But from the point of view ...
1
vote
2answers
16 views

order-isomorphism can send chain to other chain

exercise 7.20 in Goldrei: Let $a_1<\cdots<a_n,c_1<\cdots<c_n$ be rationals. Show that there is an order-isomorphism $f:\mathbb{Q} \to \mathbb{Q}$ such that $\forall i: f(a_i)=c_i$. ...
0
votes
1answer
36 views

Definition of Jordan–Dedekind chain condition

Let $(X,\le)$ be a lattice. Which is the correct definition for Jordan-Dedekind condition: 1) all maximal chains in $X$ have the same cardinality. 2) for any interval $I$ in $X$, all maximal chains ...
1
vote
3answers
36 views

The Mini-Max theorem for lattices

I'm asking for help on an exercise in Davey and Priestleys's Introduction to Lattices and Orders. For those with the book, the exercise is specifically 2.9. Let $A=(a_{ij})$ be an $m\times n$ ...
0
votes
0answers
22 views

Is there accepted notation and/or terminology for the smallest cover of $S$ with cells from $P$?

Let $X$ denote a set. Then for $S \subseteq X$ and $P$ a partitioning of $X$, define $P \diamond S$ as the smallest cover of $S$ with cells from $P$. Explicitly: $$P \diamond S = \bigcup\{Q \in P ...
0
votes
0answers
17 views

Equivalence between the linear order of cardinal numbers and the axiom of choice

It is said here (paragraph History) that the Cantor-Bernstein theorem can be obtained easily from the linear order of cardinal numbers, and that the latter is equivalent to the axiom of choice. How ...
2
votes
2answers
35 views

Is it still possible for their to exist a well-ordering on the reals such that there is always a least next element?

Let $a \leq b$ be a well-ordering on $\Bbb{R}$. And suppose for any $a_n \in \Bbb{R}$ there exists another element $a_{n+1} \in \Bbb{R}$ such that under the given ordering $(a_n, a_{n+1})$ is empty. ...
4
votes
0answers
34 views

Self-duality in a lattice

Is there any finite self-dual lattice $(X,\le)$ such that there is not any self-duality $f:X\to X$ such that $f\circ f = 1_X$? Let $f,g:X\to X$ be a self-dualities. Then $f^{-1}\circ g$ is an ...
3
votes
1answer
24 views

Partitioning a totally ordered set into three subsets according to the order

Consider a set $S$, and a total order $R$ over that set. Part (a) Given some element $e \in S$, explain why it is possible to partition $S$ into the following three sets: $$S_1 = \{ x \in S ...
0
votes
1answer
35 views

Proving that a poset can be expressed as a union of subchains.

Let $L$ be a finite partially ordered set where the maximum size of an antichain is $n$. I need to prove that $L$ can be expressed as a union of $n$ subchains. Here is my attempt: $L$ must have at ...
-1
votes
0answers
28 views

Find the Fixed points

Let $L=\mathcal P(\mathbb N)$ be a complete lattice of subsets of $\mathbb N$. Find the smallest and the greatest Fixed Point: 1) $F(X)=\left\{ x \mid x+1\in X \right\}$ 2) $F(X)=X \setminus \left\{ ...
1
vote
2answers
44 views

Proving that a convex subset of a chain is the intersection of a lower segment and an upper segment of a chain.

The book I am using is very naive so AC is assumed. Call a subset $S$ of a chain $L$ a lower segment if: $x \in S$ and $a < x$ implies $a \in S$. An upper segment is defined equivalently. Call a ...
1
vote
2answers
40 views

Find the Fixed points (Knaster-Tarski Theorem)

Let $L=\mathcal P(\mathbb N)$ be a complete lattice of subsets of $\mathbb N$. a) Justify that the function $F(X)=\mathbb N \setminus X$ does not have a Fixed Point. I don't know how to solve this. ...
1
vote
1answer
14 views

Equivalence between different definitions of transitive closure

Let $W$ be an arbitrary, non-empty set and let $R$ be an arbitrary binary relation on $W$. Define the transitive closure of $R$ as $R^+ = \bigcap \{ R' \; | \; R' \text{ is a binary transitive ...
4
votes
1answer
182 views

A reflective subcategory of the category of inverse semigroups.

The Question. I'm reading Lawson's "Inverse Semigroups: The Theory of Partial Symmetries" and I've hit something I don't understand. It's claimed on page 34 of my copy that The category of ...
-1
votes
1answer
44 views

Maximal Element vs Greatest Element [closed]

Disclaimer: This thread is written in Q&A style. The answer is provided below. Let $A$ be a poset. If $a$ is a greatest element then $a$ is a unique maximal element. Is the converse true as ...
1
vote
2answers
40 views

Well-ordering principle and negative integers

The Wikipedia article on the Well Ordering Principle defines it [1] as: "The well-ordering principle states that every non-empty set of positive integers contains a least element." And it defines ...
0
votes
1answer
46 views

Why we use ANY in the definition of a maximal element?

I am confused about the following definition: "a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S." I do not understand ...
5
votes
1answer
44 views

In a lattice, does $x \vee y \leq x\vee z$ and $x \wedge y \leq x\wedge z$ imply $y\leq z$?

Let $L$ be a lattice and $x,y,z\in L$. If $y \leq z$, then clearly $x\vee y \leq x\vee z$ and $x\wedge y \leq x\wedge z$. Now I wonder about the reverse direction. In general, $x\vee y \leq x\vee z$ ...
0
votes
1answer
32 views

About definition of lexicographical order

Def. let be $\preceq_A$ a total order, $(a_1,a_2,...,a_n),(b_1,b_2,...,b_n) \in A^n$, $(a_1,a_2,...,a_n) \leq^d (b_1,b_2,...,b_n)$ if one and only one of the following holds is true: $$a_1 \prec_A ...
-1
votes
0answers
37 views

Is an o-minimal structure equivalent to a totally ordered set?

Is the notion of o-minimality synonymous to a totally ordered set? Both notions seem to emanate from Tarski although he may not have discussed o-minimality explicitly...
2
votes
2answers
58 views

Why do 42 and 30 have the same structure in the diagramm of Hasse?

I have an exam coming up tomorrow and there's just one more question more to prepare. I would be so gratefull if anyone could help. It´s about the relations of dividers. By the help of the diagram of ...
0
votes
0answers
51 views

Is this connected relation?

My task is to check if this is preference relation (connected and transitivited) $$ f \succeq g \Leftrightarrow \forall x\in [0,1] f'(x) \leq g'(x) $$ My solution is: that this relation is not ...
1
vote
0answers
29 views

A partial order with more properties than would be expected

Consider the relation: $$\langle x_1,x_2\rangle\prec\langle y_1,y_2\rangle\iff x_1,x_2,y_1,y_2\in\Bbb N\wedge x_1y_2<x_2y_1.$$ This is usually used for defining the (positive) fractions $\Bbb ...
0
votes
2answers
57 views

How to define an isomorphism between $^\omega\omega$ and $\omega^\omega$?

Let $^\omega\omega$ be the set of all functions $x: \omega \to \omega$. Define $A = \{x \in ^\omega\omega \; | \; x \text{ has finite support}\}$, where by "finite support" I mean that the set $\{x(n) ...
1
vote
0answers
52 views

Order Preserving Isomorphism

If abelian group G has an archimedean order then there is an order preserving isomorphism $\phi$ of G onto a subgroup of $\mathbb{R}$. Here we can say that G is archimedean totally ordered abelian ...
1
vote
1answer
69 views

Bijection from $\mathbb{R}^n$ to $\mathbb{R}$ that preserves lexicographic order?

Is there a bijective mapping $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ that preserves lexicographic order? That's to say, we'd need to have $f(x_1, \dots, x_n) \leq f(y_1, \dots, y_n)$ iff ...
-1
votes
1answer
44 views

Existence of certain uncountable closed sets in the order topology

This is a proof-verification request. Let $\Omega$ be the set of countable ordinals, $\omega_1$ the first uncountable ordinal, and $\Omega^*=\Omega\cup\{\omega_1\}$. Remarkable properties of these ...
3
votes
0answers
39 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
2
votes
1answer
21 views

Does a discrete semilattice of finite width have finite number of points between any pair of elements.

Let $(S,<)$ be a countably infinite semilattice such that: 1) $S$ is no-where dense - i.e. there does not exist a subset $T$ such that for all $a,b\in T$ with $a<b$, there exists $c\in T$ with ...
3
votes
1answer
31 views

Non-monotonic functions on ordered sets

I'm trying to prove that if $~~(A,<_A)~~$ and $~~(B,<_B)~~$ are linearly ordered sets and $~~f: A \rightarrow B~~$ is non-monotonic function than there exist points $~~a,b,c\in A~~$ such that ...
1
vote
1answer
42 views

comparing two sets in set theory

I have two sets A and B and this condition holds: $\forall x \in A , y \in B: x \leq y$ Is there any standard term to describe the relation of A and B? something like $A \leq B$? Thanks for your ...
3
votes
1answer
44 views

Undistinguishable elements in posets

Given a finite partially ordered set $P = (V, <)$, I say that $x$ and $y$ in $V$ are indistinguishable in $P$ if for all $z \in V \backslash \{x, y\}$, I have $z < x$ iff $z < y$, and $x < ...
3
votes
1answer
86 views

Definition in Kunen

In Kunen's second edition of set theory he gives the following definition Let $(\mathbb{Q},\leq_\mathbb{Q},\mathbb{1}_\mathbb{Q})$, and $(\mathbb{P},\leq_\mathbb{P},\mathbb{1}_\mathbb{P})$ be forcing ...
3
votes
2answers
60 views

Is a complete flag well-ordered?

Given a vector space $V$, a collection $\mathcal{F}$ of subspaces of $V$ is called a flag of $V$ if $\{0\}\in\mathcal{F}$ $V\in\mathcal{F}$ $\mathcal{F}$ is a chain Furthermore, a flag ...
4
votes
1answer
83 views

How to make an order isomorphism

Two linear orders $A$ and $B$ have starting points $a_0$ and $b_0$, and have cofinalities $\omega_1$. Let $(a_\alpha )_{\alpha<\omega_1}$ and $(b_\alpha )_{\alpha<\omega_1}$ be cofinal ...
1
vote
1answer
51 views

How to determine distribution

I hope you will be patient with the inarticulate question of a non-mathematician. It's hard to get an answer when you don't even know how to ask the question. But here goes... ...Actually, I have two ...
2
votes
3answers
148 views

Name the property $f(x) \ge x$

It's a really one of the simplest properties you could imagine for a function. But I haven't been able to find a name for it. What do you call a function $f$ with the following property: $$f(x) \ge ...
0
votes
1answer
57 views

Lower bounded lattice to complete lattice

My problem is to show that any lower-bounded lattice satisfying the maximal condition is a complete lattice. Let's call the lattice $L$. I'm having some trouble with this. I have tried to look at it ...
2
votes
0answers
155 views

Profinite completion of a partial order

In Johnstone's Stone Spaces it is proved that the category of profinite partial orders is (equivalent to) the category of ordered Stone spaces (also called Priestley spaces) and that the obvious ...
2
votes
4answers
109 views

Suprema always exist $\iff$ Infima always exist

Let $X$ be a poset (or only preordered or even just equipped with a plain relation). Is it true that suprema always exist iff infima always exist: $$\left(\forall A\subseteq X: \sup A\text{ ...
2
votes
1answer
35 views

Proof that order-isomorphisms are bijective

I'm reading the Davey and Priestley's Introduction to Lattices and Order. On page 3, it is said that order-isomorphism is necessarily bijective. I thought we could easily prove the claim given the ...
0
votes
1answer
67 views

Set theory, seems like a difficult question (Choice Function)

So, I don't know if this certain type of set has a name in English. If it has, I'll be glad if someone will edit my post. Definition: Let $A$ be a set and $f: P(A)\setminus \emptyset \rightarrow A$ ...
0
votes
1answer
48 views

Defining principal elements of every poset. Is this a new idea?

Fix an arbitrary complete lattice $\mathfrak{A}$ with order $\sqsubseteq$. I call elements $a,b\in\mathfrak{A}$ intersecting and denote $a\not\asymp b$ iff there is a non-least element ...
0
votes
1answer
22 views

Cardinality of partial orders on $\mathbb R \times \mathbb R$

Let the set $A$ be defined: $A=\{X \subseteq \mathbb R \times \mathbb R: X$ is a partial order $\land \max X \in \mathbb Z \land min X \in \mathbb Z \}$ What's the cardinality of $A$?
0
votes
1answer
24 views

If an infinite well-ordered set has initial segments of finite cardinality only, is the set isomorphic to $\mathbb N$?

Let $A$ be an infinite well-ordered set. Every initial segment of $A$ is finite. Is $A$ isomorphic to $\mathbb N$? What's the way to think about it? Should I build an explicit isomorphism? What ...
0
votes
2answers
27 views

Understanding first and minimal elements

Give an example of a set with partial order, that has a single minimal element but no first element. The example that was given is $\mathbb Z \cup \{2.5\}$, with relation $<$. I can't see why the ...