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

Total Order between sets.

If I have two streams x1 and x2 and I define a prefix ordering on them such that, x1 <| x2 :⇔ x1=x2 V ∃β ∈ streams that x1.β = x2. Are they in Partial Order as well as in total order?
3
votes
2answers
50 views

Embedding $\omega_1$ into the direct sum/product of $\Bbb R$'s and $\Bbb N$'s

I'm trying to find a way to visualize the first uncountable ordinal $\omega_1$. This is rather difficult, as the visualization tactic that I often use for countable ordinals - namely, the "matchstick" ...
4
votes
0answers
93 views

adjoints and duality

Let $X$ and $Y$ be posets seen as a category. Let $F:X \to Y$ and $G: Y \to X$ be an adjunction. That is, $(G \circ F) (x) \ge_X x$ and $(F \circ G) (y) \le_Y y$. Now, $F$ is additive and $G$ is ...
0
votes
0answers
27 views

Shorten a proof using Galois connections

Consider a Galois connection: $f:R\rightarrow F$ is a lower adjoint of $r:F\rightarrow R$ for partially ordered sets (actually complete lattices) $F$ and $R$. We have also $f(r(g))=g$ for every $g\in ...
7
votes
2answers
245 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
285 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
48 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 ...
1
vote
2answers
42 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$?
2
votes
0answers
38 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
99 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 ...
0
votes
2answers
51 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
48 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 ...
1
vote
1answer
135 views

How many ways are there to represent a monomial order, defined by $>$, by term order via matrices?

During the lecture, my professor brought up the 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 ...
3
votes
1answer
72 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
58 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 ...
0
votes
0answers
19 views

A fuzzy formulated problem about partial and total orders

Let we have a partial order and elements $a\le b$. Can we define a total order from $a$ to $b$ such that it is dense in our partial order? What do I mean by "dense"? I don't know. Please help to ...
0
votes
0answers
18 views

Bijection between partial order and $<$

How to show the correspondence between a less than relation and partial orders ? here A less than relation $<$ on a set $S$ is a relation that satisfies If $a < b$ , then $a \neq b$. ...
3
votes
1answer
31 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 ...
-3
votes
1answer
171 views

What's the difference between relations, functions, and operations?

My understanding is vague: operations is a subclass of functions, functions is a subclass of relations. operations and functions can form terms but not formulas, relations can form formulas but not ...
1
vote
1answer
36 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 ...
0
votes
0answers
10 views

Ordering multilinear functions by their binary exponent presentation, is this an lexicographical order?

I am trying to understand the Lexicographical order aka dictionary order here. I order multilinear functions to a vector, for example $x_2x_1-x_3$ where $x_2x_1$ has the binary order $011$ while ...
3
votes
2answers
103 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 ...
0
votes
0answers
26 views

Suppose y is a prime and that b has order 3 modulo y. What is the order of b+1? [duplicate]

order is 6 by showing the expansion of (b+1)^6, but are there other solutions where I have to solve for all the pairs (y,b) that meets the conditions of the problem ?
0
votes
2answers
53 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
93 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
46 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
32 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
39 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
37 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) ...
10
votes
3answers
2k views

What do curly less than sign 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
68 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
54 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
66 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 ...
2
votes
2answers
108 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 ...
6
votes
1answer
74 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 ...
2
votes
2answers
107 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
125 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
36 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
85 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
45 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 ...
1
vote
0answers
34 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
29 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
58 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
33 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
32 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
60 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
0answers
29 views

Order Embeddings

Let (S,<=) be an (partially) ordered set and A a subset of S with the inherited order, namely, <= /\ AxA Thus, A is order embedded in S. When S isn't a lattice and A is a lattice would would ...
0
votes
1answer
34 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 ...
1
vote
0answers
64 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
44 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 ...