Questions tagged [order-theory]

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. Order theory is not about the order of a group nor the order of an element of a group or other algebraic structures.

Filter by
Sorted by
Tagged with
1 vote
1 answer
41 views

Show that a circular relation is not a partial ordering

I'm learning about partial orderings and need some help understanding the following statement. Say we have a relation, R, between the objects of finite set $S$: If every element in R is preceded by ...
user avatar
  • 517
2 votes
1 answer
52 views

Show that the definition of Scott topology is a topology

To verify the definition of a Scott topology is a topology, I still need to show that it's closed under intersection. Can someone help? Definition 1 (Scott topology). Let $(D,\leq)$ be a complete ...
user avatar
  • 29
3 votes
0 answers
71 views

A complete partially ordered set.

Please help me to understand the topic of order relations on the set. I can't understand what a complete partially ordered set is. I want to summarize how I understand the topic of order relations on ...
user avatar
0 votes
0 answers
13 views

Are there any theorems about the restriction of a partial order? [closed]

That is, by restricting the partial order on a subset, the order becomes complete.
user avatar
  • 175
3 votes
1 answer
57 views

The proof of Lemma 10.1 in Nik’s book about forcing

I’m an undergraduate student trying to teach myself set-theory. And I have some trouble understanding the density of a constructed set. In Lemma 10.1 of Nik’s book, it states: Let $G$ be a generic ...
user avatar
1 vote
1 answer
50 views

What is an example of a nonempty subset of $\mathbb{R}$ that is bounded above that does not contain its least upper bound?

What is an example of a nonempty subset of $\mathbb{R}$ that is bounded above that does not contain its least upper bound? This is an on-a-review sheet for my final. I thought the completeness axiom ...
user avatar
0 votes
0 answers
45 views

Are all incomparable elements in a set considered both maximal and minimal?

Say I have a set that has mixed comparable and incomparable elements. $$S_C = \{ 1, 2, 3 \}$$ $$S_I = \{🤗, 🐕\}$$ $$...$$ $$ S_n = S_C \cup S_I \cup ... $$ $$where...$$ $${\displaystyle \forall }S_j:...
user avatar
0 votes
0 answers
11 views

Set of measures on the simplex of matrices that take support on rank 1 matrices has a minimal element

Let $M=\{ A\in\mathbb R^{n\times m} : \forall i,j~A_{i,j}\geq 0,\sum_{i,j} A_{i,j} = 1 \}$ be the simplex of $n\times m$ matrices, it was shown in a previous question that the set $R$ of rank $1$ ...
user avatar
  • 3,965
0 votes
1 answer
40 views

Can lattices which are also linear orders be characterized equationally?

There is a definition of a lattice as an algebraic structure of type $\langle 2,2 \rangle$ which satisfies commutativity and associativity for both operations and the absorption laws connecting the ...
user avatar
  • 13.3k
0 votes
1 answer
32 views

Completeness of a theory that is not $\omega$-categorical

Let $T$ be the theory of linear orders with no endpoints and let $\mathcal{L}=\{<,c_0,c_1,\dots\}$ be the language that consists of a binary relation symbol and a countable amount of constant ...
user avatar
2 votes
0 answers
41 views

Question about $\omega$-categoricity

Let $T$ be the theory of linear dense orders with no endpoints and let $\mathcal{L}=\{<,c_0,c_1,\dots\}$ be the language that consists of a binary relation symbol and a countable amount of constant ...
user avatar
0 votes
0 answers
21 views

Chain of non-empty sets under inclusion has a non-empty set as a lower bound

I couldn't find anything related to that, even though I can imagine this has been asked already. Let us consider subsets of a given set $E$ with order $\subseteq$. Suppose we have a chain $C$ in $E$ ...
user avatar
  • 3,965
1 vote
1 answer
71 views

Cardinality of the set of strict total orders on $\mathbb{R}$

A strict total order on $\mathbb{R}$ is a relation $R \subseteq \mathbb{R} \times \mathbb{R}$ such that: $\forall x \in \mathbb{R}, (x,x) \not \in R$ $\forall x,y,z \in \mathbb{R}, (x,y) \in R \text{ ...
user avatar
  • 469
0 votes
0 answers
28 views

Proof that every Cauchy sequence converges in a complete Stonean Algebra

I'm working through Jech, Thomas J., Abstract theory of Abelian operator algebras: an application of forcing, Trans. Am. Math. Soc. 289, 133-162 (1985). ZBL0597.03030. and I fail to write a proof of ...
user avatar
0 votes
0 answers
25 views

Is there a name for this weakening of the notion of a well-founded partial order?

Suppose that $\langle P, \leq, \bot \rangle$ is a partially ordered set with least element $\bot$ which satisfies for all $p \in P$ there is a $q \in P$ such that $\{ r \in P \colon r \leq q \} $ is ...
user avatar
  • 3,505
2 votes
1 answer
103 views

prove that $(0,1)\cap \mathbb{Q}$ is order-isomorphic to $(-\pi,\pi)\cap \mathbb{Q}$

it's a part of my set theory HW. the definition of order-isomorphic in the course: if $(X,\leq),(Y,\leq)$ are orderly sets than $X \simeq Y$ if there is exist $f:X \to Y$ bijecton surjectiove and if $...
user avatar
0 votes
0 answers
35 views

How to prove that a surjection from a dense set to another dense set extends to a surjection?

I am studying the book Discovering Modern Set Theory: The Basics but I am stuck in one important lemma. Let $\langle A_0,\leq_0 \rangle$ and $\langle A_1,\leq_1 \rangle$ be dense, complete linear ...
user avatar
  • 117
0 votes
0 answers
15 views

Random variables with same mean and different variance

This is the follow up from question. Suppose $X$ and $𝑌$ with the same distribution, $E[X]=E[Y]$ and $𝑉𝑎𝑟(𝑋)<𝑉𝑎𝑟(𝑌)$. I know that the argument such that $X$ first-order stochastic dominate ...
user avatar
0 votes
1 answer
55 views

Universally embedding total order = $\eta_\xi$ set?

In Alling's "Foundations of Analysis on Surreal Number Fields," he writes If $X$ is an $\eta_\xi$-set and if $Y$ is a [totally] ordered set of power not exceeding $\aleph_\xi$, then there ...
user avatar
0 votes
0 answers
17 views

Some question about lattice rank.

I found this equation while looking at the "Rank of a partially ordered set" "A lattice with a rank function ρ is (upper) semi-modular if:ρ(x)+ρ(y)≥ρ(x∨y)+ρ(x∧y)" (https://...
user avatar
  • 1
0 votes
0 answers
71 views

element in longest chain and longest antichain

In an arbitrary finite poset, is there necessarily an element that is both in the longest chain and in the largest antichain? I think it is true. Longest chain contains an element of every largest ...
user avatar
  • 1
2 votes
1 answer
44 views

Reading off semi-lattice diagram

I'm reading a chapter about mereology (in a handbook of linguistics), and I have some questions. A prepring is available here (p. 519). The symbol $\leq$ is to be interpreted as non-strict parthood, ...
user avatar
3 votes
1 answer
58 views

Semilattice whose Subsets are All Closed -- does it have a special name?

Context: self-education. I am currently getting my head round semilattices. My understanding is that a semilattice $(S, \odot)$ is a semigroup whose operation $\odot$ is both commutative and ...
user avatar
  • 4,048
0 votes
1 answer
22 views

How do you prove that a formally constructed total ordering is unique?

Seth Warner's Modern Algebra Exercise $14.22$ gets us exploring the properties of semilattices, in particular join semilattices. Context: self-education. The specific question that has been given is: ...
user avatar
  • 4,048
0 votes
0 answers
21 views

Natural order on function set?

Let $X$ and $Y$ be finite, ordered sets. Is there a best, natural order on the set $Y^X$ of functions $X \to Y$? The best I can think to do is to use the order on $X$ to identify each $f:X \to Y$ as ...
user avatar
  • 6,365
0 votes
0 answers
22 views

Two elements forming least upper bound together

There is a particular notion that I faintly remember reading about either here on StackExchange or elsewhere concerning an alternative to the idea of a least upper bound in partially ordered set, ...
user avatar
  • 2,098
0 votes
0 answers
45 views

How to linearly order the set of all subsets of real numbers?

I wondered if there are linearly ordered sets of any cardinality. As I understand it, there are. But I want to see at least one concrete example of a linearly ordered set which cardinality is greater ...
user avatar
0 votes
1 answer
57 views

Prove that the following relation is a preorder on the set of metrics for $X$ that compatible the topological inclusion

Let be $X$ a set. So if $\delta$ and $\rho$ are two metrics on $X$ then we say that $\delta\preceq \rho$ if for any $\epsilon\in\Bbb R^+$ exists $\nu_\epsilon\in\Bbb R^+$ such that $$ \delta(x,y)\le\...
user avatar
2 votes
1 answer
27 views

A mapping of two sequences with no overlaps and partial assignments

I want to characterize a correspondence mapping of two sequences $\psi : A \rightarrow B$ for an article that I am writing. I need help describing the function class. I think this is an injective, ...
user avatar
4 votes
1 answer
87 views

Is the theory of linear dense orders with distinct endpoints complete?

I'm trying to solve some problems about elementarily equivalent structures. For example, I know that the structures $\langle\mathbb{Q},<\rangle$ and $\langle\mathbb{R},<\rangle$ are elementarily ...
user avatar
-1 votes
1 answer
23 views

Constrain ordering such that there is always a choice left

Given some sets $X_1, \cdots, X_n$ I want to define some ordering < of these sets such that if I select an element in $X_i$ it can not be selected in any future $ X_i < X$ but for any $X_i<\...
user avatar
  • 1
0 votes
0 answers
68 views

Prove ordered decreasing and ordered bounded sequence in ordered Banach space converges with respect to norm

Let $(X,\|\cdot\|_X,\preceq)$ be a ordered normed vector space which is at least infinite-dimensional and $K$ a convex cone. We define the ineqaulity as the following: $x\preceq y :\Leftrightarrow y-x ...
user avatar
  • 17
0 votes
0 answers
14 views

Construction of order-preserving map on Bourbakian poset

Given an order preserving map $$f:\alpha\to P$$ with $\alpha$ an ordinal and $P$ a Bourbakian poset, I'm trying to construct an order preserving map $$g: P\to P$$ whose fixed points are precisely the ...
user avatar
0 votes
1 answer
59 views

Set Theoretic definitions of a Universe question

I have questions (in bold) regarding the set theoretic definitions of a universe. It's my understanding a universe is a class of the form: $$U(X) = \cup_{i=1}^\infty S_i$$ $$S_0 = X$$ $$S_{n+1} = S_n \...
user avatar
  • 939
0 votes
0 answers
20 views

Constructing a measure on a product space of ordered sets

Let $X$ and $Y$ be linearly ordered sets equipped with their interval topologies. Let $\mu$ and $\nu$ be finite positive Borel measures on $X$ and $Y$, respectively. If $I ⊆ X$ and $J ⊆ Y$ are each ...
user avatar
0 votes
0 answers
23 views

Are the odd integers cofinal in the integers with the usual order?

I think the definition I read of cofinal says there must always be an element of the subset which is greater than any given element. The odd numbers have this property, so they're cofinal, right? ...
user avatar
0 votes
0 answers
32 views

$\gamma<\theta$ iff $\gamma\in\theta$

I'm struggling with my homework: Let $\gamma,\theta$ be order types. Then, $\gamma<\theta$ iff $\gamma\in\theta$. I already proved that if $\gamma\in\theta$, then $\gamma<\theta$. To do the ...
user avatar
  • 105
1 vote
0 answers
24 views

Prove that if W is an initial segment of X×Y then there exists an initial segment V in Y such that X×V is an initial segment of X×Y containing W

Given a ordered set $(X,\preceq)$ for any $\xi\in X$ we call the set $$ I_\xi:=\{x\in X:x⪱\xi\} $$ the initial segment of $\xi$. Now if $(X,\preceq)$ and $(Y,\precsim)$ are two ordered sets then it is ...
user avatar
1 vote
1 answer
50 views

Can we uniquely define for arbitrary, real-valued, finite sequence $X$, infinitely many pairs (real-valued $f(X)$, rank order of elements of $f(X)$)?

For an arbitrary sequence $X$ of $n$ distinct real numbers, can we uniquely and exhaustively define a set of infinitely many pairs of the form: $[f_{j},$ order$(f_{j}(x))]$, where $f_{j}$ is a real-...
user avatar
0 votes
0 answers
19 views

How to construct an increasing $\aleph_1$ sequence of real numbers. [duplicate]

We have $\aleph_1\leq |\mathbb{R}|$. Do we know if there exists an increasing $\aleph_1$ sequence of real numbers? (That is, a set $\{a_\theta\in\mathbb{R}:\theta<\omega_1\}$ such that $a_{\theta_1}...
user avatar
0 votes
1 answer
39 views

I seek for a short and rigorous way to extend an embedding of a partial order into $\mathbb{Q}$

Let $(X,\leq ) $ be a partial order and $A$ be a proper subset of $X$ and $t\in X\setminus A$. Knowing that there exists an order-preserving map $\varphi :A\rightarrow \mathbb{Q}$ whose range is ...
user avatar
  • 187
0 votes
0 answers
42 views

How to proof that [reversing the lexicographic order] corresponds to [set-complement] on k-combinations (without repetition)

The combinations $\sigma$ of $K$ elements of a set of size $N$ can be ordered lexicographically $\,(<_{\text{lex}})\,$ such that we have $$\forall\left(i,j\in\left[1,i_{\text{max}}\right]\right)\,.\...
user avatar
0 votes
0 answers
35 views

Is there a general poset representation that specializes to power set lattices in case of finite boolean algebras?

I read here that every finite, complemented, distributive lattice is isomorphic to a power set lattice. Is there a general order preserving mapping from a poset $P$ to a set inclusion poset $S$, such ...
user avatar
  • 123
0 votes
1 answer
27 views

Is the equality-free theory of linear orders the same as the equality free-theory of linear preorders?

This is a natural follow-up to my question, here:In first-order logic without equality, is the theory of partial orders the same as preorders?. My current question is, consider first-order logic ...
user avatar
  • 13.3k
3 votes
1 answer
114 views

Ordinals without set theory?

I'm interested in whether ordinal numbers can be described by a first-order theory without presupposing ZFC or any particular set theory. Such a theory might look like Peano arithmetic, but ...
user avatar
  • 4,878
4 votes
1 answer
91 views

Order theory from categorical point of view

On p. 12 of Introduction to Lattices and Order by Davey and Priestley, the authors give a 1-paragraph description of Category Theory, and then write: We do not have sufficient need to call on the ...
user avatar
  • 13.3k
2 votes
2 answers
61 views

Quick way of drawing Hasse diagrams of posets

When drawing a Hasse diagram, I have seen that you can draw a bigraph for the poset and remove the reflexive and transitive edges of the poset. However, doing this for a poset with many elements can ...
user avatar
  • 465
0 votes
0 answers
44 views

Finding restriction of the ultraproduct that behaves like $\mathbb{Z}$

Let $\mathcal{A}= \prod_{n \in \mathbb{N}} \mathcal{A}_n /\mathcal{U}$, where $\mathcal{A}_n=(\{0, 1, \dots, n\},<)$ and $\mathcal{U}$ is a non-principal ultrafilter of $\mathbb{N}$. Can we find ...
user avatar
0 votes
0 answers
34 views

Name of property: $\phi (x)\geq x$ [duplicate]

Let $X$ be a preordered set and $\varphi : X\to X$ a function (can assume monotone if useful for the answer). Does the property of $\forall x\in X: \varphi (x) \geq x$ have a standard name?
user avatar
3 votes
1 answer
93 views

A property of partitions of the real numbers

Let a strict linear order $C = (V, <)$, be an irreflexive and transitive relation < defined on $V$, and call a section of $C$ a partition of $V$ into two sets $A, B$, such that $x < y$, ...
user avatar
  • 1,363

1
2 3 4 5
76