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
1answer
62 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
163 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
121 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
52 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
90 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
53 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
31 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
53 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
32 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 ...
0
votes
1answer
46 views

increasing subset of a partial order and characteristic function

Can someone help me understand this? Suppose that $\preceq$ is a partial order on a set $S$ and that $A\subseteq S$. If $\mathbf{1}_A$ is the indicator function then $A$ is increasing if ...
1
vote
3answers
27 views

Is (total-)order a weak version of countability?

One can easily see that countability also imposes or enables an ordering of the set. Now $\mathbb{R}$ is ordered but not countable. Is this ordering a weaker version of countability (at least in ...
1
vote
1answer
38 views

compactness and maximal elements

Let $C$ be a nonempty compact subset of $R^n$, with a certain partial order defined on it. I am trying to prove that $C$ contains a maximal element. My idea is: start with a certain element of $C$. ...
2
votes
1answer
54 views

Compactness and existence of Pareto-efficient cake partitions

I am trying to understand a fundamental statement in the theory of cake-cutting. BACKGROUND: There is a certain "cake" $C$ (a subset of $R^n$). The cake is divided among two agents, 0 and 1. Each ...
1
vote
1answer
35 views

Antisymmetric relation (“strong” vs “weak”)

Defining: "weak antisymmetric relation": $\forall a, b \left< a,b \right> \in R \land \left< b,a \right> \in R \Rightarrow a=b$ "Strong antisymmetric relation": $\forall a, b \left< ...
1
vote
1answer
36 views

Are surjective order-homomorphisms necessarily complete lattice homomorphisms?

Let $X$ and $Y$ denote complete lattice, and suppose $f : X \rightarrow Y$ is a surjective order-homomorphism. Does $f$ necessarily preserve arbitrary suprema, therefore being a complete lattice ...
1
vote
2answers
58 views

Order Type of $\mathbb Z_+ \times \{1,2\}$ and $\{1,2\} \times \mathbb Z_+$

I'm currently working on §10 of "Topology" by James R. Munkres. I've got a problem with task 3: Both $\{1,2\} \times \mathbb Z_+$ and $\mathbb Z_+ \times \{1,2\}$ are well-ordered in the ...
3
votes
0answers
38 views

Divisibilty as relation set on $(\mathbb N \setminus \{0,1\})$

So i have to see if $\prec$ is order relation where two elements $(a,b)$ and $(c,d)$ are in relation $\prec$ if $a|c$ and $2b^{2}+6b\leq2d^{2} + 6 d$. This relation is defined on set $(\mathbb N ...
1
vote
0answers
27 views

Principal order filters on a POSET

I have another problem, but in this one I have no idea how to start. Let be $(X,\leq)$ a POSET with a first element and gifted with the topology $\{ (a,\rightarrow) : a \in X \}$ (principal order ...
0
votes
2answers
43 views

Greatest lower and least upper bounds for a set of pairs

Had some trouble with this question in an exam recently, and wanted to make sure I reasoned correctly. The question was: $X$ is a set of pairs of real numbers $(x,y)$, with absolute values less than ...
1
vote
3answers
79 views

Is this proof legal?

Let $\left(P,\le\right)$ denote a poset. Statement: if every sequence $p_{1}\leq p_{2}\leq\cdots$ in $P$ stabilizes (in the sense that for some $n$ we have $k>n\Rightarrow p_k=p_n$) then every ...
1
vote
0answers
59 views

Why are frames called “frames”?

Definition: A frame $F$ is a suplattice such that for any $x_{i}, y\in F$ (for $i\in I$, $I$ a set), we have $$y\wedge\left(\bigvee_{i\in I}x_i\right)=\bigvee_{i\in I}(y\wedge x_i).$$ Why are ...
0
votes
1answer
46 views

Left & right adjoints in the context of complete lattices.

This is a follow-up question from this question of mine. In the same paper as the one mentioned in my previous post, it's stated that In the context of complete lattices, a monotone map has a ...
1
vote
1answer
60 views

Left & right adjoints in the context of posets.

Definition 1: A function $\theta: X\to Y$ between posets is monotone if whenever $x\le y$, we have $\theta (x)\le\theta (y)$. Definition 2: For any pair $f:A\to B$ and $g:B\to A$ of monotone maps, we ...
0
votes
1answer
35 views

Showing a set is well-ordered

Let $(C,S)$ be a well-ordered set. Let $d \notin C$. We define the set $D=C \cup \{d\}$ and the relation $S'=S\cup (C \times \{d\})$. Show the set $(D,S')$ is well-ordered. Any help would be much ...
1
vote
0answers
27 views

Are all preorders implication relations?

This question is for the people who know what consequence relations are. Just to clarify, a consequence relation C on L is a relation from the powerset of L, to L, that satisfies certain properties. ...
2
votes
1answer
35 views

Proving that $\overline{([a,b],\le)}=\overline{([c,d],\le)}$, i.e., the order types of two closed intervals are the same

Prove that for all $a,b,c,d : a\le b : c\le d$ we have 1.$\overline{[a,b]}=\overline{[c,d]},$ 2.$\overline{(a,b)}=\overline{(c,d)}$ 3.$\overline{[a,b)}=\overline{[c,d)}$ ...
1
vote
1answer
27 views

Show that If $C$ is a chain in $X$ then $f(C)$ is also chain in $Y$.

Let X and Y are poset and $f:X\to Y$ is increasing function. If $C$ is a chain in $X$, show that $f(C)$ is also chain in $Y$. Since C is chain for every $x,y \in C: (x,y)\to \left(x\leq y\bigvee ...
0
votes
1answer
47 views

How to prove that $x\leq f(x)$ if f order isomorphic?

Let X is a well ordered set and $f:X\to f(X)=Y\subseteq X$ is order isomorphic. For any $x\in X$ prove that $$x\leq f(x)$$ since X is well ordered, {x,f(x)}$\subseteq$X and $x\leq f(x) $ or ...
2
votes
2answers
110 views

Coding Forcing Notions by Ordinal Numbers: A Possible Approach to Shelah-Foreman-Magidor Conjecture

Forcing notions are partial orders. In some sense each partial order is a "combination" of some well-orderings and each well-orderings is isomorphic to a unique ordinal number. Thus in some sense a ...
1
vote
1answer
99 views

Prove/disprove questions on isomorphism and embedding between order types

About the notations: Let $\lambda, q, z, \omega$ be the order types of the reals, rationals, integers and natural numbers respectively. The sign $=$ means there's isomorphism and $\le$ means ...
0
votes
1answer
73 views

Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
1
vote
0answers
85 views

Have you seen this property of tolerance relations before?

Let $A$ be a set equipped with a binary reflexive and symmetric relation $\uparrow$ (such relations are often called tolerances, see also "Are there real-life relations which are symmetric and ...
1
vote
2answers
36 views

Is the series $\frac{1}{(n+1)^p}-\frac{1}{(n-1)^p}$ where 0<p<1 convergent or divergent?

Sorry for my bad English. I really suspect it is convergent. But I can't prove it. Since ${x^p}$ is not derivable at x=0, I can't using taylor expansion to find the order of infinitesimal, thus ...
4
votes
2answers
55 views

Is there a mistake in this question: $\forall a\in A: |\{x\in A:x\le a \}|=|\{ y\in B :y\le a \}|$?

Two ordered sets $(A,\le_A), (B,\le_B)$ and there's an isomorphic function $f:A\to B$ Prove $\forall a\in A: |\{x\in A:x\le a \}|=|\{ y\in B :y\le a \}|$ I think there's a mistake in this ...
0
votes
2answers
157 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
1
vote
1answer
123 views

Total function vs Partial function

I'm reading a lecture note in which the following functions ($fact_i : \mathbb{Z}_\perp → \mathbb{Z}_\perp$) for $i \in \mathbb{N}$ are NOT considered total: \begin{equation} fact_0(x) = \perp ...
1
vote
0answers
51 views

Prove/disprove questions on equivalence relations and ordered sets

If $R$ is an equivalence relation and a partial order over $A \neq \emptyset$ then every equivalence class contain at least one element. If $(A,\le)$ an ordered set, and $a\in A$ is a single ...
2
votes
1answer
47 views

If a net is too big, convergence tells us very little?

I'm just learning about nets. It occurs to me that sometimes $x_{\alpha} \to x$ doesn't tell us much at all. Consider the directed set $J:= \{(U,x)\in \mathcal{P}(X) \times X: x \in U \}$, $(U,x) ...
3
votes
2answers
166 views

Is every continuous function measurable?

In non-Hausdorff topology it is standard to define the Borel algebra of a topological space $X$ as the $\sigma$-algebra generated by the open subsets and the compact saturated subsets. Recall that a ...
1
vote
1answer
47 views

Describing orders on sets $\{1,2,3,4\}$ and $\mathbb N$ with minimal/maximal/maximum/minimum elements

Describe all the partial orders on $\{1,2,3,4\}$ where the set of minimal elements are $\{2,4\}$ and the set of maximal elements is $\{1,3\}$ Describe all the partial orders on $\{1,2,3,4\}$ ...
0
votes
0answers
32 views

Has anyone used the isomorphism with $\Bbb{N}_{\gt 0}$ as a monomial ordering?

Let $R[x_1, x_2, \dots]$ be a ring of formal polynomials in a countably $\infty$ number of indeterminates $x_i$, over a commutative ring $R$. The commutative monoid $X = \{ x^e = x_1^{e_1} x_2^{e_2} ...
2
votes
1answer
34 views

What is the meaning of $<$ in a preorder?

Let $(P,\le)$ be a preorder, i.e. $P$ is a set and $\le$ is a relation on it that is reflexive and transitive. In this context for myself I can find two interpretations for the symbol $<$ 1) ...
6
votes
1answer
89 views

Terminology in forcing

In the context of forcing one reads the relation $p \leq q$ in a poset $P$ as "$p$ extends $q$". A typical example is the poset $P$ of finite partial functions, where one defines $p \leq q$ when $q ...
1
vote
0answers
23 views

Has an order with this property a special name?

If $a$ is an element in a preorder then you can eventually go 'a step back' (and repeat this) in the sense of finding an element with $b\leq a$ and not $a\leq b$. Is there a special name for ...
0
votes
1answer
19 views

Every admissible ordering on a countably infinite monoid is induced by an isomorphism onto $(\Bbb{N}, \cdot)$.

Let $fg$ mean the functional composition of functions $f, g$. Let $M$ be a countably infinite, commutative, multiplicative monoid and let $f : M \to (\Bbb{N}_{\gt 0}, \cdot)$ be an isomorphism. ...
2
votes
1answer
30 views

Continuity and Leximin

Consider a relation $\geq$ over the set of real-valued vectors. We say that $\geq$ is continuous if for any positive integer $n$, and any $\pi\in\mathbb Z^n,u\in\mathbb R ^n$ we have that the sets ...
3
votes
2answers
42 views

All tree orders are lattice orders?

Say that a set is tree ordered if the downset $\downarrow a =\{b:b\leq a\}$ is linearly ordered for each $a$. In a comment, Keinstein says that such sets are also semi-lattices, provided they are ...
1
vote
0answers
32 views

Addition on well ordered sets not-commutative by showing $[0,1) +_o \mathbb{N} =_o \mathbb{N} \neq_o \mathbb{N} +_o [0,1)$

My goal is to show that addition on well ordered sets are non-commutative by showing that, $[0,1) +_o \mathbb{N} =_o \mathbb{N} \neq_o \mathbb{N} +_o [0,1)$ Some definitions (let A and B be ...
4
votes
4answers
68 views

Number of join-irreducible elements of a lattice: is it monotonic?

Let $\mathcal L$ be a sub-lattice of $\mathcal P(X)$, where $X$ is a finite set. Denote by $\mathcal I(\mathcal L)$ the set of union-irriducible elements of $\mathcal L$ (i.e. $A\in \mathcal ...
2
votes
0answers
33 views

Is every sub-lattice of $\mathcal P(X)$ isomorphic to a sub-lattice of $\mathcal P(X')$ containing a singleton set? [duplicate]

Let $X$ be a finite set. $\mathcal{P}(X)$ denotes the set of all subsets of $X$. Let $\Gamma$ be a sub-lattice of $\mathcal{P}(X)$, i.e. $\Gamma$ is a collection of subsets of $X$ closed under union ...