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

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 ...
2
votes
0answers
68 views
+50

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

Maximal Element vs Greatest Element [on hold]

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
34 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
45 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
39 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
29 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
33 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
57 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
22 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
28 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
55 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
51 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 ...
0
votes
0answers
55 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
43 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
35 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
20 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
40 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
41 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 < ...
2
votes
1answer
79 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
59 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
82 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
141 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
54 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
151 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
107 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
30 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
64 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
45 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
23 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
24 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
33 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
26 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
53 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
16 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
22 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
30 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
33 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
26 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
28 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
68 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
44 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
34 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
46 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
30 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
23 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. ...