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

2
votes
1answer
17 views

Well-ordered family of open sets.

Let $X$ be a second countable space. I $\textbf{A}$ is a family of open set well-ordered by inclusion prove that this family is numerable. I have the following idea: Let $\textbf{B}$ be a ...
1
vote
2answers
29 views

A question about the cardinality of a set of functions with finite support where the domain of each function has cardinality aleph-null.

Suppose that $M$ is a well ordered set with at least two elements and that $L$ is a well ordered set with the same cardinality as the natural numbers. Let $[L, s.f, M]$ be the set of all functions ...
0
votes
1answer
25 views

Dilworths Theorem proof doubt

This is the proof I am talking about http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf When you take a maximal chain C in P and then obtain antichains in P\C, if the size of the ...
0
votes
0answers
17 views

Diffrence between chaotic and Orderd Equations/systems

what is the difference between chaotic and Ordered Equations ? if the first one means that the system behaviour is not predictable , why we just call it stochastic process , and using random ...
0
votes
3answers
46 views

Correctness of proof that every positive rational with square $>2$ is an upper bound for those with square $<2$

I would like to know whether my proof makes sense or not, and if not where should it be corrected. Let $E=\{x \text{ is rational }: x>0 \text{ and } x^2<2\}.$ Claim: Every member of $F=\{x ...
1
vote
1answer
40 views

Every subgroup of a cyclic group is characteristic (using lattice theory).

I want to show for $n\in\Bbb N$, which is not square-free, that every subgroup of $Z_n=\langle x\;|\;x^n\rangle$ is characteristic. But I want to show it in a convoluted way. Every automorphism ...
1
vote
4answers
116 views

Are $1+ω$ and $ω+1$ isomorphic?

In set theory, $1+ω$ is defined as the ordinal number of ordinal sum of sets $\{a\}$ and ℕ. Also $ω+1$ is defined as the ordinal number of ordinal sum of sets $\Bbb N$ and $\{a\}$. You know what the ...
1
vote
1answer
41 views

Let $L$ and $L'$ be lattices. Prove that $L \times L'$ is also a lattice.

Can someone please verify my proof or offer suggestions for improvement? Some preliminaries: Let $A$ and $B$ be two posets. $A \times B$ is the poset on the cartesian product of $A$ and $B$ such ...
1
vote
0answers
27 views

Prove that $P$ is a lattice (details inside)

Can someone please verify my proof or offer suggestions for improvement? There may be answers to the same questions elsewhere, but I need help with my proof in particular. Show that if $P$ is a ...
1
vote
1answer
12 views

Let $P$ be a finite poset. Show that the number of order ideals equals the number of antichains.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there are similar questions posted elsewhere, but I need help with my proof in particular. Some preliminaries: ...
2
votes
0answers
22 views

Let $P, Q, R$ be finite posets. Prove that $P^{Q+R} \cong P^Q \times P^R$.

Can someone please verify my proof and offer suggestions for improvement? I feel that my proof might have been a little hand-waving in showing that $\varphi$ is a bijection, and I feel that it is not ...
0
votes
2answers
41 views

Is the function $x \mapsto \max\{f(x),g(x)\}$ always an automorphism if $f$ and $g$ are?

Consider a totally ordered set $X$ and a pair of automorphisms (i.e., order-preserving bijections) $f,g$ of $X.$ Then the function $$h:x \in X \mapsto \max\{f(x),g(x)\} \in X$$ is an order-preserving ...
0
votes
0answers
22 views

Any projection of a complete semilattice is a homomorphism

Let $\langle D, \leqslant \rangle$ be a poset. A mapping $\psi \colon D \to D$ is called a projection (or kernel operator) if it satisfies the following conditions: $\psi(x) \leqslant x$, $x ...
0
votes
0answers
16 views

Ingredients for Proving that a set is bounded below

I am having a hard time to really understand the definition of bounded below. The definition states : Let S be a nonempty subset of real numbers, we say S is bounded below if there is a c ∈ ℝ ...
1
vote
1answer
33 views

“Szpilrajn extension theorem” in Wikipedia

In this link: http://en.wikipedia.org/wiki/Szpilrajn_extension_theorem in the section "lemma". The author construct a partial order $T$ on a set $X$ which extends another partial order $R$ in the ...
0
votes
1answer
28 views

Homework | Prove Relation is Partial Order

I have been stuck on this question for quiet a bit of time. I'm not sure how to prove a relation $R$ is a partial order of $X$. Let $\mathbb{Z}$ be the set of integers and consider the set $X = ...
1
vote
0answers
36 views

A total order induce by a partial order

I have the following problem: Let $(A,\leq)$ a poset. Prove that there exist a total order $\leq^ *$ on $A$ such that if we have $a\leq b$ we can conclude $a\leq^*b$. (Hint: Use the Zorn Lemma) ...
1
vote
1answer
22 views

Understanding the notation of a response to a question about extending partial orderings.

I found a question and two answers that both are very complete but I cannot understand the meaning behind some of the symbols that are used. They are different from what I am familiar with. The ...
0
votes
1answer
30 views

Let $A$ be a partially ordered set in which every chain has an upper bound, and let $a \in A$. Then $A$ has a maximal element $u$ such that $u \ge a$.

Let $A$ be a partially ordered set in which every chain has an upper bound, and let $a \in A$. Then $A$ has a maximal element $u$ such that $u \ge a$. I'm trying to solve this by way of ...
1
vote
1answer
14 views

Proof Verification, any partially ordered set contains a maximal totally unordered subset (antichain).

I wrote a simple proof and I want to verify it. I simply argued that the set of all totally unordered subsets forms a partially ordered set, ordered by inclusion. Every chain in this partially ...
2
votes
1answer
96 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
-1
votes
0answers
20 views

Ordered field - Adding inequalities (Looking for a proof)

In an ordered field, it is allowed to add two inequalities. Where can I find a detailed proof?
0
votes
0answers
15 views

Proof of a variation of Hausdorff maximality principle

Let ($A$, $\le$) be a partially ordered set and let $B$ be a totally ordered subset of $A$. Prove that $A$ has a maximal totally ordered subset $C$ such that $B \subset C$. I'm trying to prove this ...
0
votes
1answer
34 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
28 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 ...
3
votes
0answers
36 views

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

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
66 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
43 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
44 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
37 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
vote
2answers
45 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
183 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
46 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
45 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 ...
2
votes
2answers
67 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 ...