Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 alegbraic structures.

0
votes
0answers
15 views

Understanding minimum/maximum and minimal'maximal elements in a partial order.

I don't understand, are "minimal/minimum/maximal/maxium" elements properties of a partial order or properties of base sets of partial orders? Given any partial order $(X,\leq)$ from what I can gather,...
0
votes
0answers
6 views

How to prove that for any nonempty set $A$, there exists a maximal partial order $\lambda$ with the axiom of choice?

The ``maximal partial order'' means for any partial order $\alpha\in\mathscr{B}(A)$, $\lambda\subseteq\alpha$ implies $\lambda=\alpha$. It is obvious if we apply the well-ordering theorem or Zorn's ...
3
votes
1answer
28 views

Linearly ordering the power set of a well ordered set with ZF (without AC)

As the title says, my question is, how one can use only ZF-theory to prove that the power set of A, whereby (A, <) is a well-ordering, can be linearly ordered?
0
votes
1answer
19 views

Proving that exists equivalence relation $r$ in set $A$ such that $ |A \setminus r| = n$

I am trying to show that if $|A| = m$ and $0\neq n \le m $ then exists equivalence relation $r$ in set $A$ such that $ |A \setminus r| = n$. Could someone help me deal with it?
6
votes
1answer
50 views

Drawing balls from an urn or counting certain posets

A colleague of mine was curious about the number of possible start-configurations in a game. The game itself is not known to me, but the question which he formulated as urn problem was interesting. ...
0
votes
0answers
16 views

Amalgamation base, extending Galois type

Here on the page 12 the Observation 1.11 5) says If $M\leq_{\frak K} N$ are from ${\frak K}_{\lambda}$, $M$ is an amalgamation base and $p\in S(M) \;\underline{\text{then}}$ there is $q\in S(N)$ ...
3
votes
0answers
42 views

About “Principles of Mathematical Analysis” by Walter Rudin Theorem 3.17(a).

I am reading Walter Rudin's "Principles of Mathematical Analysis". There are the following definition and theorem and its proof in this book. Definition 3.16: Let $\{ s_n \}$ be a sequence ...
1
vote
0answers
52 views

What does “$E$ is not bounded above” mean? I am confused. “Principles of Mathematical Analysis” by Walter Rudin Theorem 3.17.

I am reading Walter Rudin's "Principles of Mathematical Analysis". There are the following definition and theorem and its proof in this book. Definition 3.16: Let $\{ s_n \}$ be a sequence ...
1
vote
1answer
49 views

I heard that the empty set $\emptyset$ is bounded. But I think this statement is not correct.

In Rudin's "Principles of Mathematical Analysis", there is the following definition of bounded. Definition: Suppose $S$ is an ordered set, and $E \subset S$. If there exists a $\beta \in S$ such ...
0
votes
0answers
22 views

Infinite descendant sequences

"Show that the order $(A,<)$ is well ordering if and only if there no exists infinite descendant sequences in $A$". Can you help me whit this problem, please, what happens is that my professor isn'...
2
votes
1answer
49 views

Is there a name for an associative algebraic structure in which everything is irreducible?

Let $A$ be a set and $\ast$ a binary operator on that set. Let us suppose that $(A,\ast)$ satisfies the following axioms: For all $x,y,z \in A$, $x \ast (y \ast z) = (x \ast y) \ast z$ For all $x,y,z ...
0
votes
1answer
34 views

Partially ordered sets cardinality

What is the cardinality of the set of all partially ordered sets of natural numbers which have one least element and infinity number of maximal elements? I only noticed that upperbound for this set ...
0
votes
2answers
22 views

Order Topology on a Preorder

While looking at the definition of the order topology defined on a total order (https://en.wikipedia.org/wiki/Order_topology), I realized I needed a generalization to preorders. So ultimately the ...
0
votes
1answer
19 views

Convergence of monotone nets

In sequences of real numbers, we have a monotone convergence result: If $a_{n+1}\geq a_n$ and bounded, then $a_n$ converges to it's supremum. The proof seems to work also in the net case. My ...
2
votes
2answers
71 views

Maximum cardinality of a set of subsets

Let $N$ be a system of subsets of the set $X = \{1,2,3,\cdots ,n \}$ such that there are no three elements $A,B,C \in N$ such that $A \subset B \subset C$. Prove that $$|N| \leq 2 \cdot {{n}\choose{ \...
2
votes
0answers
44 views

Are Morphisms of a Category Order Isomorphisms?

Let the objects be all partially ordered sets $(S,\le)$ in a Category $\mathscr{C}$. A morphism $(S,\le) \to (T,\le)$ is a function $f: S \to T$ such that for $x,y \in S, x \le y \implies f(x) \le f(y)...
1
vote
0answers
22 views

Existence of well-order on an arbitrary infinite set $X$ without a largest element [duplicate]

I've already asked a similar question yesterday (is there a well-order such that $X$ has a largest element). Can one prove the existence of a well-order on an infinite set $X$ such that $\forall x \in ...
1
vote
1answer
23 views

How can one calculate the Möbius function $\mu(a_1,a_i)$ for all $i \in \{1, …, 10\}$ of this poset?

I've seen this partially ordered set in our combinatorics script and it says that it is obvious how to calculate the möbius function $\mu(a_1,a_i)$ for all $i \in \{1, ..., 10\}$. Here's the Hasse ...
2
votes
2answers
30 views

Existence of well-order on an arbitrary infinite set $X$ such that $X$ has a largest element.

One can prove that every set $X$ can be well-ordered. Can we also prove (or disprove) that for any arbitrary infinite set $X$ there exists a well-order such that there is a largest element, that is, ...
0
votes
0answers
44 views

injective order preserving homomorphism ϕ of two ordered abelian groups satisfies a<b⇔ϕ(a)<ϕ(b).

Exercise: Prove that every injective order preserving homomorphism $ϕ$ of two ordered abelian groups satisfies $a < b ⇔ ϕ(a) < ϕ(b)$. Definition: A homomorphism $ϕ : G → H$ of ordered ...
0
votes
1answer
24 views

Constructing lists from Ordered Pairs

I've been searching online for a way of constructing lists from sets, but to no avail. However, I am aware of how to define ordered pairs and, more generally, ordered n-tuples from sets. My first ...
0
votes
1answer
18 views

Subset variance order preserving function

Given a finite set with real numbers. X = {x1, x2, x3}. There can be a unique order defined for all the subsets using Variance operator. e.g. X = {1, 2, 4}. $$ {\displaystyle \operatorname {Var} (X)...
3
votes
1answer
39 views

Is there any work on partition a partial order set into minimum number total order subsets?

The problem is what's the minimum number of total order subsets can a partial order set partition into? For example, (1,2) and (3,4) are comparable i.e. (1,2) < (3,4), and (1,2) and (2,1) are ...
1
vote
1answer
51 views

Finite chain condition - Variation of Martin's Axiom statement

In the following $k$ and $w$ will be cardinal numbers. Consider the classical statement $MA(k)$: For any partial order $P$ satisfying the countable chain condition (hereafter $ccc$) and any family ...
0
votes
1answer
26 views

Number of ordered partitions of N into K distinct parts modulo P

I've come across a combinatorics problem where I'm fairly certain that a solution exists, yet I'm unable to find it. I'm trying to find the number of vectors $(x_1,x_2,...,x_n)$ such that $\sum x_i ...
2
votes
2answers
61 views

The theory of dense linear orders without end-points is not $2^\omega$-categorical

It seems best to prove this by counter example. Both $\mathbb{R}$ and $I := \mathbb{R} \backslash \mathbb{Q}$ under the usual order $<$ are models of the theory of dense linear orders without end-...
0
votes
0answers
33 views

What is the name of a coinductive type defined with a total order relation?

In type theory, is there a name for a coinductive type simply defined with a successor operator and an equivalence relation? And what would be the name of such a type if it were defined with a total ...
0
votes
0answers
42 views

There exists a minimal uncountable well ordered set. [duplicate]

There exists a well-ordered set $A$ having a largest element $\Omega$ such that the section $S_\Omega$ of $A$ by $\Omega$ is uncountable but every other section is countable. Can anyone make me ...
1
vote
2answers
28 views

Is the natural order relation on an idempotent semiring total/linear?

We know that on an idempotent semiring $R$, the natural order relation is defined as: for all $x, y\in R$, $x\leq y$ when $x+y=y$, which is clearly a partial order relation. I am unable to point out ...
2
votes
1answer
14 views

Final maps with the same domain

Let $\mathbb D$ and $\mathbb E$ be two directed sets, then a map $f:\mathbb D\to \mathbb E$ is said to be final,if for any $e\in E$ there exists some $d\in D$ such that $f(d')\geq e$ whenever $d'\geq ...
0
votes
0answers
8 views

segments of arbitrary finite measure on a nonatomic measure space

Let $(E,\Sigma,\mu)$ be a completely non-atomic and $\sigma$-finite measure space. Suppose that $\leq$ is a total order on $E$ and write $<$ for the corresponding strict order. We say that $E'$ ...
3
votes
2answers
44 views

What are “real-world” examples of posets which are not (semi-) lattices?

I know the classic counterexamples which amount to taking a few elements and constructing something like „equip elements $a,a^\prime$ with other elements that are both minimal upper bounds“, but that ...
4
votes
2answers
58 views

Well ordering and maximal chains in power set

Let $M$ be a set and "$\le$" a well-ordering of $M$. For $x \in M$ define: $$ M_{\le x} := \{ y \in M \ \vert\ y \le x \} $$ The map $$ f : M \to \mathcal{P}(M) \ ,\ x \mapsto M_{\le x}$$ is injective ...
0
votes
2answers
37 views

Let $B,C$ be sets, $B\subseteq C$ such that $\forall c∈C,\exists b\in B: c\le b$ then $\sup B=\sup C$.

I had been reading this. In the proof, below lemma is used. I don't know how to go for proving it.Notice that I want to prove this theorem for set of ordinals not real numbers Let $B,C$ be sets, $...
1
vote
1answer
42 views

terminology “possible sequences of a set”

I am not a mathematician but am wanting to informally research some math topics related to order and combinatorics. Up to now unable to discover the right terms to use in a math context, so that I can ...
1
vote
1answer
30 views

Equivalent properties of a proper ideal of a generalized boolean algebra

I do not understand the item c) of the following question, the exercise 9 from section 1.2 from the book "Lattice-ordered Rings and Modules" from Stuart A. Steinberg: A generalized boolean algebra is ...
12
votes
1answer
545 views

What is the order-type of the set of natural numbers, when written in alphabetical order?

We are all familiar with the standard nomenclature for the smallish natural numbers, such as one, two, three, ..., one hundred, one hundred one, ..., fifteen thousand two hundred forty-nine. I ...
3
votes
1answer
40 views

What is a minimal set of rules that determine the usual order on $\Bbb{N}$ given that $1 \lt p_1 \lt p_2 \lt \dots$?

Let $p_i$ always mean the $i$th prime number. Given two numbers $a, b \in \Bbb{N}$ in the form $a = \{(p_i, e_i) : p_i^{e_i} \mid a, e_i \text{ maximal}\}$ ie. essentially their unique ...
2
votes
1answer
54 views

Extension of order-preserving bijection from rationals to reals.

If $f:\mathbb{Q}\rightarrow\mathbb{Q}$ is order-preserving bijection. Prove that $f$ can be extended to an order-preserving homeomorphism $F:\mathbb{R}\rightarrow\mathbb{R}$. Attempt for Proof:The ...
3
votes
2answers
29 views

Define non-eventually-constant $f: I \to \{a, b\}$ from arbitrary upwards-directed poset $I$

Is the following provable and how? I feel like I am missing some proof technique or strong theorems, I'd be grateful for any pointer. Let $(I, \leq)$ be an upwards-directed poset. Define an $f: I \...
3
votes
2answers
37 views

Example of a uniquely complemented lattice?

I'm approaching lattices. I have understood the definition of a Lattice, a Complete Lattice and a Bounded Lattice. Theoretically, even the definition of a complemented lattice doesn't seem difficult, ...
0
votes
1answer
21 views

Given two posets $\preccurlyeq$, prove that the following relation $R$ using both of them is transitive

We're given the following relation $R$ for two posets $(S_1, \preccurlyeq_1)$ and $(S_2, \preccurlyeq_2)$: For $a_1,b_1 \in S_1$ and $a_2, b_2 \in S_2$: $(a_1, a_2)R(b_1,b_2) \Leftrightarrow (a_1 \...
0
votes
1answer
26 views

Partial ordering on a space of matrices

I am wondering as how to define partial ordering on a space of matrices! The following is what i intuitively constructed: If $M$ is a set all $n×n$ matrices with entries of each matrix are from an ...
0
votes
1answer
63 views

Books that summarize the classical application of Zorn’s Lemma.

Zorn’s lemma, as defined in Wikipedia, is stated as follows: (Zorn’s lemma) A partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily ...
2
votes
1answer
39 views

When can one atom be below the join of two distinct atoms?

Consider three distinct atoms of a lattice $a,b,c$. When can we rule out the possibility that $c\le a\lor b$? So, to be clear, the question is: What is the weakest natural property of a lattice that ...
0
votes
0answers
11 views

Componentwise differences of vectors as bound of componentwise differences after permutating the indices

Let $x,y\in\Bbb R ^N$ and $\pi ^x , \pi ^y \in \mathcal S_N$ such that $$x_{\pi^x (1)} \geq \ldots \geq x_{\pi^x (N)} ,\quad y_{\pi^y (1)} \geq \ldots \geq y_{\pi^y (N)}.$$ I think there should hold: ...
0
votes
1answer
9 views

Preserving componentwise order of a vector when permutating the indices

I want to prove the following: Let $x,y\in\Bbb R ^N$ and $\pi ^x , \pi ^y \in \mathcal S_N$ such that $$x_{\pi^x (1)} \geq \ldots \geq x_{\pi^x (N)} ,\quad y_{\pi^y (1)} \geq \ldots \geq y_{\pi^y (N)}...
5
votes
2answers
56 views

Betweenness preserving implies monotonic?

For this question, we can assume that $f:\mathbb{R}\rightarrow\mathbb{R}$. However, I hope that an answer can generalize to arbitrary linearly ordered sets. I assume that everyone will know what I ...
3
votes
1answer
31 views

Isomorphic subsets of countable total orders

Suppose $(\Omega,\leq)$ is a totally ordered set, with $\Omega$ infinite and countable. If $S$ is an infinite subset of $\Omega$, then $(S,\leq)$ denotes the induced totally ordered set. Are there ...
2
votes
1answer
26 views

Möbius function - understanding of relations

I am trying to understand Möbius function from the wikipedia article (and also few others that I have come across so far). This function is defined in posets and so the relations in Special elements ...