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

8
votes
2answers
384 views

Existence of a utility function on the reals

Suppose I have $\preceq$, a total order on $\mathbb R^n$. I wish to show that there is a utility function $u:\mathbb R^n\to\mathbb R$ such that $x\preceq y \leftrightarrow u(x)\leq u(y)$. I came up ...
6
votes
2answers
1k views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
2
votes
2answers
79 views

Is there a single well-ordered set whose discrete space equals to its order topology?

Let $(X,\leq_X )$ and $(Y,\leq_Y)$ be two well-ordered sets, such that the discrete space of $X$ is the same as the order topology on $(X,\leq_X)$ and the same goes for $Y$. I'd like to prove that $(X,...
1
vote
2answers
53 views

What's the name of this property?

Is there a name for (partially or totally) ordered set $(A,<)$ such that for any $x,y\in A$, $x< y$ there is a $z\in A$ such that $x<z<y$?
0
votes
1answer
93 views

Monotonicity of consumer preferences

I'm learning about monotonicity and I can't seem to figure out what larger $x$ is and what is smaller $x$. If I strictly prefer larger x when until $x<10$, what does that mean? Context The ...
2
votes
0answers
96 views

Can the actual scope of “lattice theory” be summarized as “algebraic order theory”?

Lattice and order theory are often mentioned together. So I wonder how lattice theory is "intended" to differ from order theory. Lattice theory became important in the context of universal algebra. ...
1
vote
2answers
297 views

Initial Segments and Initial Sections of Posets

For a set A with a partially ordering <=, define the following 1) A subset s(x) of A = {y in A such that y <=x} 2) A subset S of A with the property that for every x in S then all y in A ...
1
vote
2answers
57 views

What is the order of $f(x) = \frac{2}{2-x}$ as a permutation?

$f(x) = \frac{2}{2-x}$ defines a permutation of the set $A={\bf R}\setminus \{0,1,2\}$. What is its order in the permutation group $S_A$? I don't know how to find orders of functions. Please help!
2
votes
1answer
57 views

How can I prove that $(\mathbb Z,\leq_*)$ is isomorphic to $(\mathbb N,\leq )$

We define the binary relation $\leq_*$ between integers by the following rule: For $n,m\in\mathbb Z$, $n\leq_∗m$ holds if and only if one of the following conditions is satisfied: $|n|<|m|$, or $|...
2
votes
1answer
249 views

How many ways are there to represent a monomial order by term order via matrices?

During the lecture, my professor brought up a list of project ideas to work on. One of the ideas I am interested and currently working on is term order via matrices. That is: I need to find the number ...
4
votes
1answer
108 views

Zorn's Lemma related statement

Consider the following statement: If $X$ is partially ordered set such that every chain in $X$ has un upper bound, then for every $x \in X$ there is a maximal element $m$ in $X$ such that $x \le m$. ...
2
votes
3answers
65 views

I'm confused about the definition of poset.

The definition of poset : $\qquad$A set with a partial ordering. Partial ordering is a binary relation $\preceq$ over a set ($P$). If I understood the definition of relation correctly, then ${\preceq}...
3
votes
1answer
34 views

Order of $\left(\mathbb{Z}/10\mathbb{Z}\right)^{*}$ and others groups

I already know that $\left(\mathbb{Z}/10\mathbb{Z}\right)^{*}=\left(\mathbb{Z}/2\mathbb{Z}\right)^{*}\times\left(\mathbb{Z}/5\mathbb{Z}\right)^{*}$ Theses groups have order 1 and 4 so the group is ...
1
vote
1answer
231 views

Proof that the sum of the order of the orbits of a set is = the order of the set?

I understand that the order of a set is the number of elements it has, however I don't understand the relationship between this number and the orbits of the set. As I understand it, the orbit of an ...
4
votes
2answers
656 views

Why is the minimal uncountable well-ordered set $S_{\Omega}$ unique?

In section 10 of Topology by Munkres, the minimal uncountable well-ordered set $S_{\Omega}$ is introduced. Furthermore, it is remarked that, Note that $S_{\Omega}$ is an uncountable well-ordered ...
2
votes
4answers
135 views

Prove that the order on integers is antisymmetric

Let $m, n \in \mathbb{Z}$. If $m \le n \le m$ then $m = n$. The definition of order is: if $m>n$ it means $m-n \in\mathbb{N}$. I know that by definition this means either $m<n$ and $n<...
0
votes
2answers
216 views

Not well-ordered sets satisfying the least upper bound property

Before proving that every closed interval in $\mathbb{R}$ is compact, James R. Munkres remarks that, in Section 27 entitled "Compact Subspaces of the Real Line" of Topology (2nd edition), Remark: ...
2
votes
0answers
203 views

Back-and-Forth Argument vs. “One-Way” Argument

The wikipedia article on the Back and Forth Argument claims at the end: If we iterated only step $(1)$, rather than going back and forth, then in some cases the resulting function from A to B ...
2
votes
1answer
63 views

In the transition from set theory to order theory, what is the appropriate generalization of “group”?

Given a set $X$, the collection of all bijective endofunctions on $X$ forms a group, called the symmetric group on $X.$ Furthermore, Cayley's theorems says that every group embeds into a subgroup of ...
3
votes
1answer
44 views

Injectivity of rank function

Let $R$ be well founded and set like on $A$. I want to show that $R^{*}$ is a total order iff $rank_{A,R}(y)=\sup\{rank(x)+1|$ $xRy$ $\wedge{x\in{A}}\}$ is injective. Here $R^{*}$ is the transitive ...
0
votes
1answer
56 views

Completeness of posets

I think this is rather a simple question in order theory, but if someone could explain it step by step that would be really useful. If we have an arbitrary set, then let's denote the set of all finite ...
1
vote
2answers
45 views

Is there an (order-theoretic) version of bijectivity? But appropriate for lower adjoints.

Let $f : X \rightarrow Y$ denote a function. Then the following are equivalent. ($f$ is an isomorphism) There exists a function $g : Y \rightarrow X$ such that $$\forall x \in X, y \in Y \;\;\; f(x) ...
19
votes
4answers
7k views

What does “curly (curved) less than” sign $\succcurlyeq$ mean?

I am reading "Convex Optimization" by Stephen Boyd. He is using a curved greater than and curved less than equal to signs. $f(x^*) \succcurlyeq \alpha$ or $f(x*) \preccurlyeq \alpha$ Can someone ...
3
votes
1answer
87 views

Uncountable sets and interval topology

Let be an uncountable well-ordered set $(X,\leq)$. We suppose that exists some $x\in X$ such that $y < x$ for uncountably many values of $y$ and define $x_1$ as the minimum $x\in X$ such that $y &...
2
votes
0answers
137 views

Cones and partial ordering

A positive cone always induces a partial ordering on a vector space. I wonder if the converse holds, so is every partial ordering in a vector space induced by a positive cone, or in other words, is ...
2
votes
1answer
98 views

A well ordering on $\mathbb{R}$ and bigger sets

Consider the set of sequences $S = \{f:\mathbb{N}\to\mathbb{N}\}$, define an order on $S$ by the following: Based on the well-ordering of $\mathbb{N}$ and induction, either $f_1 = f_2$ or there is a ...
3
votes
2answers
950 views

Number of ways to interleave two ordered sequences. [duplicate]

Suppose we have two finite, ordered sequences $x = (x_1,\dots,x_m)$ and $y = (y_1,\dots,y_n)$. How many ways can we create a new sequence of length $m+n$ from $x$ and $y$ so that the order of elements ...
7
votes
1answer
167 views

Order-preserving injections of ordinals into $[0,1]$

The usual "matchstick" representation of an ordinal number can be thought of as an order-preserving injection of that ordinal into the interval [0,1]. For example, here's a representation of $\omega^2$...
3
votes
2answers
133 views

Collection of independent sets equal to downset?

I have been struggling with the following problem. Every set here is supposed to be finite. If we have a closure $\lambda$ on $X$, we define the collection of independent sets of $X$ as $$ I_\lambda ...
11
votes
2answers
220 views

Which of these constructions are left adjoints?

A groupoid can be regarded as a small category in which every arrow is an isomorphism A monoid can be regarded as a small category with only a single object A preorder can be regarded as a small ...
2
votes
1answer
46 views

Likeness of strictly well-ordered sets

The question itself: Given a strictly ordered set $\langle A, < \rangle$ (< merely symbolises some kind of an order in this case) which is dense, with a least and greatest elemnts that are not ...
1
vote
1answer
121 views

Which mathematician has argued that we should move from “set” to “order”?

I recall reading (on this very site, in fact) that there is a mathematician whom argues that we ought to switch from "set" to "order" in the foundations, so as to "recover duality" or some such. Does ...
0
votes
1answer
56 views

Elementary Properties of Order

Need help with this question: Prove: Let $x = a_1, a_2...a_n$, and let $y$ be a product of the same factors, permuted cyclically. (That is, $y = a_k, a_{k+1}...a_na_1...a_{k-1}$. Then $ord(x)=ord(y)$...
1
vote
0answers
54 views

The null set as the underlying set of a relation structure

Can the null-set underly a relation structure? Can it underly a well-order? If so, would such a well-order have order-type $0$? (Can one even have an order-type of $0$?) My motivation for this ...
0
votes
1answer
42 views

Question about sets of well-orderings

I recently posted a question on here about sets of well-orders and isomorphisms between well-orders. I have a related question about order-type-comparison: if $W$ is any set of well-orders, doesn't ...
5
votes
1answer
112 views

Question about sets of well-orders and isomorphisms between well-orders

I was thinking about this problem in trying to better get a feel for and understand well-orders (I'm trying to learn some set theory) - right now, I'm not really hoping for anybody to supply me with a ...
0
votes
1answer
38 views

Could someone check this proof for me?

The problem (and a definition first): The following definition explained Let $U \subseteq \mathbb{N}$. We say that a function $x: \{0,1\}^U\to \{0,1\}$ is a $xor$ on the set $U$ if the following ...
0
votes
2answers
37 views

How many pairwise nonisomorphic dense subsets exist

in the completion of a linear order of cardinality $\kappa$? Can there be more than $\kappa$? To be more precise, suppose $L$ is a linear order of cardinality $\kappa$. Let $\overline L$ denote ...
1
vote
1answer
70 views

Interesting question with ordering integers

The numbers $1,2,3,...,101$ are written down in a row in some order. Is it always possible to cross out $90$ numbers in a way such that all $11$ numbers left will stay either in increasing or in ...
0
votes
1answer
54 views

Proof by contradiction: $c=\max (A) \wedge d=\max (B) \to \max (A \cup B ) \in \{c,d\}$

Let be $A,B \subseteq \Bbb{R}$, with $A \neq \emptyset $ and $B \neq \emptyset$ and $\Bbb{R}$ totally ordered by $\leq$, and $c,d \in \Bbb{R}$, with $c=\max (A)$ and $ d=\max (B)$. I must proof by ...
2
votes
0answers
91 views

Does the Riemann zeta function tell us about the order theoretic properties of the natural numbers?

The classical Möbius function $\mu(n)$ fulfills the multiplicative inversion formula, e.g. see this thread. Now I see in the theory of posets, they generalize the concept of that function, see ...
1
vote
1answer
68 views

What motivates the definition of “Periodic” group action

Consider a group $G$ acting on a set $\Omega$. For example, let $G=\{g\in A(\mathbb R):(\alpha +1)g=\alpha g+1\}$ for all $\alpha\in\mathbb R$, where $A(\mathbb R)$ are the order-preserving ...
1
vote
0answers
52 views

Monoid Ring of a Commutative Cancellative Ordered Monoid

Suppose $M$ is a commutative cancellative monoid with $0$ as the identity and $+$ as the operation, and $M$ is equipped with an order $\preceq$ defined by $$ m \preceq m' \text{ if and only if there ...
1
vote
2answers
94 views

Proving that Order for N is Anti-symmetric

I'm having trouble deriving the following fact from the basic properties of $+_{\mathbb{N}}$ and the definition: Definition. $\forall n, m \in \mathbb{N}: (n \geq m) \leftrightarrow (\exists a \in ...
0
votes
1answer
31 views

Order isomorphic but not Boolean isomorphic

Is there an example of Boolean lattices $(X,\le)$ and $(Y,\le)$ and a function $$f:X\to Y$$ such that for all $x,z\in X$ $$x\le z ~~~~ \leftrightarrow ~~~~f(x)\le f(z) $$ so that for some $a\in X$, $...
5
votes
2answers
126 views

Old exam question about well ordering on $\mathbb{R}$

I am not sure how to start tackling this question and would love a hint: Let $<$ the regular order relation on $\mathbb{R}$, and $<_w$ well ordering on $\mathbb{R}$. We define a coloring ...
2
votes
0answers
85 views

Do subhomomorphisms / subfunctors have a standard name, and where can I learn more?

Sorry for all the mistakes in the original! I think they're mostly fixed now. Thank you for your patience. Part 1. If $A$ and $B$ are models in $\mathrm{Pos}$ of an algebraic signature $\sigma$, ...
2
votes
1answer
72 views

Extracting subnets from nets.

Let $x_i:\Lambda_i\to X_i$ be a net in a topological spaces $X_i$ that converges to $a_i\in X_i$ where $i\in\{1,2\}$ Does there exist a poset $\Lambda$ and subnets of $x_i:\Lambda_i\to X_i$ of the ...
1
vote
1answer
41 views

Does irreflexivity guarantee acyclicity?

Assume $R$ to be an irreflexive, transitive relation over a set $X$. Let $G=(X,E)$ be its directed graph where $(x,\hat{x})\in E$ if $xR\hat{x}$ is true. I know irreflexivity means $xRx$ cannot ...
2
votes
1answer
55 views

Bernstein- Schroeder thm for ordered sets

Hi everyone the I know that the Bernstein- Schroeder Thm says that if we have two sets $A,B$, and there exists an injection $f: A\rightarrow B$ and $g: B\rightarrow A$, then there exists a bijection $...