# Tagged Questions

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.

99 views

### Help to understand a proof (about filters)

Niels Diepeveen claims that he has proved the following theorem: Theorem Consider the cofinite filter $F$ on an infinite set. Let $K$ be a collection of ultrafilters such that $\bigcap K=F$. Then for ...
100 views

### Existence of totally ordered ring with zero divisors

Does there exist a totally ordered ring with zero divisors? I can't think of an example right now.
227 views

### Could the empty set be complete partial order?

According to the definition, $(S,\leq)$ is cpo when each totally ordered subset of $S$ has supremum. I'm sure $(\emptyset,\emptyset)$ is a total order, but I don't know whether $(\emptyset,\emptyset)$ ...
96 views

### Existence of non-commutative ordered ring

Does there exist a totally ordered ring which is non-commutative? I have searched the web, but I have not found any examples.
73 views

### Countability of a certain set

Suppose $S$ is a totally ordered set such that for any $x,y\in S$ there are finitely many elements between them. Does it follow that $S$ is (at most) countable? It seems like the answer should be yes,...
987 views

### How long does a sequence need to be to be guaranteed to have a monotonic subsequence length k?

The sequence 7, 2, 4, 1, 4, 8 has an increasing subsequence length four (2, 4, 4, 8) and a decreasing subsequence length three (7, 4, 1). It has other monotonic (increasing or decreasing) subsequences ...
144 views

### Is a Lattice just a linearly ordered set?

The definition of Lattice I was introduced to recently was a poset for which every two elements had a supremum and infimum. Doesn't this just mean that the poset is a chain and tus a linearly ordered ...
68 views

59 views

### Cardinality of a linear continuum

A linear continuum is a totally ordered set with more than one element, which is both dense and satisfies the least upper bound property. Is it true that every linear continuum has the same ...
75 views

### Proof that there is an order relation

For an arbitrary set M there is a relation $R \subseteq 2^M \times 2^M$ about $$A \mathrel R B \Leftrightarrow A \cup \{x\} = B$$ The join is a disjoint join. There are not more details what is $x$. ...
92 views

### Non-trivial order on a set with infinitely many minimals/maximals

I am looking for an example of each: 1) A non-trivial order on a set A such that there are infinitely many minimal elements and 2) A non-trivial order on a set A such that there are infinitely many ...
17 views

### How would I show that this is a subset?

Let R1 and R2 be relations on N defined by xR1y if and only if y=a+x for some a ∈ N0. xR2y if and only if y=xa for some a ∈ N. for all x,y ∈ N. Also N0 denotes all integers x>=0, while N denotes all ...
Let $L=(X,\wedge,\vee,^\bot)$ denote a non-empty lattice having a unary operation $x \mapsto x^\bot$ that satisfies both "shuffle" laws: $$x \wedge y \leq z \iff x \leq y^\bot \vee z.$$ $$x \leq y \... 1answer 89 views ### Effectively describing all elements of the Borel \sigma-algebra Consider, for simplicity, the Borel \sigma-algebra of the unit interval [0,1]. Let \{A_i\} be a family of Borel subsets which generate the sigma algebra (can be either countable or uncountable)... 1answer 131 views ### How to rigorously prove that these two sets have different order types? Let A and B be two given ordered sets with the linear (or total) order relations <_A and <_B, respectively. Then (A,<_A) and (B,<_B) are said to be of the same type if there ... 1answer 92 views ### Adjoint of forgetful functor I want to solve an exercise about adjoints (but I am not sure about the steps). Let U:\textbf{CL}\rightarrow\textbf{Posets} be the forgetful functor. Here we have a functor from the complete ... 1answer 49 views ### I want to be able to write proof's for each of these but I don't know where to start. Let \mathrel{R_1} and \mathrel{R_2} be relations on \mathbb N defined by x\mathrel{R_1}y if and only if y = a + x for some a \in\mathbb N_0. x\mathrel{R_2}y if and only if y = ... 1answer 80 views ### Expected value of round robin scores and ranks Suppose you have n players play a round robin tournament. A win adds 1 to the winning score of a player while a loss adds nothing. After the round robin tournament is finished the players are ... 2answers 649 views ### Total Order Relation Given X = \{ a , b , c \} and R = \{ (a,a) , (b,b) , (c,c) , (a,b) , (a,c)\} Is R a total order on X? I know that total order requires the relation to be comparable on all elements, anti-... 1answer 66 views ### I want to show that \mathrel{R_1} and \mathrel{R_2} are a partial order on \mathbb N, how would I do this? Let \mathrel{R_1} and \mathrel{R_2} be relations on \mathbb N defined by x\mathrel{R_1}y if and only if y = a + x for some a \in\mathbb N_0. x\mathrel{R_2}y if and only if y = ... 1answer 40 views ### Is this complete partial order? Is (\mathbb{N} , \#) complete partial order, where m\#n iff (\exists k \in \mathbb{N})m=kn. I proved it's partial order. For completeness I take directed subset and I know there is upper bond 1... 1answer 57 views ### Let A denote a closed subset of \mathbb{R}. Is it true that for all B \subseteq A, if B has a supremum, then \mathrm{sup}(B) \in A? Let A denote a closed subset of \mathbb{R}. It seems obvious that for all B \subseteq A we have that if B has a supremum, then \mathrm{sup}(B) \in A. Perhaps this is trivial, but I cannot ... 1answer 70 views ### Can the obvious “product” of complete atomistic Boolean algebras be realized as a categorial product? Let X and Y denote sets, and \eta_X,\eta_Y : X,Y \rightarrow X+Y denote the natural injections to the disjoint union. Then intuitively, the "product" of the Boolean algebras 2^X and 2^Y ... 1answer 162 views ### Reference Request on Order Theory topics I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ... 1answer 30 views ### When can complete dense linear orders be made into topological fields? By a "complete dense linear order," I mean a dense linear order in which every nonempty subset with an upper bound has a least upper bound. The canonical example, \mathbb{R}, is a topological field ... 1answer 59 views ### Is this a partially ordered set? I was wondering if partially ordered sets could have loops in their diagrams. For example isn't the S=\{1,2,3\} and relation R=\{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\} a partially ordered set that ... 1answer 504 views ### If a partial order has just one unique maximal element, must that element be a greatest element of x? I believe that it does not have to be a greatest element, because to be a greatest element it must be comparable to all the x in X. I just don't know how to go about proving this. 1answer 110 views ### Is there anything wrong with this use of the axiom of choice? I have a proof of the following theorem: Let A be a finite set and X be a perfectly normal topological space, and let \{(A,\succsim_x): x\in X\} be a family of binary relations on A satisfying ... 2answers 929 views ### How to prove a total order has a unique minimal element Let R be a total order on set S. Prove that if S has a minimal element, than the minimum element is unique. I have difficulties with proofs. I know any graph of a total order is a straight line,... 1answer 133 views ### How to tell if relation on set is a partial order when relation is defined as a set of ordered pairs? Determine whether R is a partial order on set the S and justify your answer. S=\{1,2,3\} and R=\{(1,1),(2,3),(1,3)\}. So the job is to consider if R is reflexive, antisymmetric and ... 2answers 126 views ### \mathbb R\times\mathbb R not order isomorphic to \mathbb R I am trying to show that if you use the lexicographic ordering induced by \mathbb R on \mathbb R\times\mathbb R they are not isomorphic. Is it enough to use the counter-example that whilst (1,0) ... 1answer 69 views ### A representation of well-orderings? Is there a well-ordering P of the set of real numbers \mathbb{R} such that there is NO function f: \mathbb{R}->\mathbb{R} satisfying the property: for all x,y \in \mathbb{R}, xPy iff ... 1answer 81 views ### Contractibility of topological spaces associated to posets Suppose \mathcal{P} is a partially ordered set. To \mathcal{P} we can associate a simplicial complex K(\mathcal{P}) whose n-simplices are the chains of length n+1 in \mathcal{P}. Since ... 1answer 189 views ### union of cyclic groups Let p be a prime integer. Let C(p^n) be the cyclic group of order p^n (C(p^n)=\{z \in C\mid z^{p^n}=1\} and let C(p^\infty) be the union of the groups C(p^n), i.e., C(p^\infty)=\{z\in C\... 1answer 72 views ### Prove anti-symmetric-ness of partial ordered set in lattice. Prove anti-symmetric-ness of partial ordered set in lattice. Definition: If (A, \le_{A}) is a lattice and C is a set, ([C \rightarrow A], \le) is also a lattice. And \rightarrow is defined ... 1answer 146 views ### Prove transitivity of partial ordered set in lattice. Prove transitivity of partial ordered set in lattice. I am given this If (A, \le_{A}) is a lattice and C is a set, ([C \rightarrow A], \le) is also a lattice. And \rightarrow is defined as ... 1answer 102 views ### order preserving implies isomorphism Let M = (M, <) and N = (N, <) be two dense totally ordered sets without endpoints. Let F be the collection of order preserving maps between finite subsets of M,N respectively. ... 1answer 35 views ### Finding order properties in the relation aSb \iff \exists k \in \mathbb{N} : b = ak An order relations exercise I just did. I think it's fine, but the second proof felt a bit too wordy or discursive, instead of going straight to the point with brief and accurate statements. How could ... 0answers 232 views ### Finding the first, last, minimal and maximal elements in these relations. I'm now learning about relations of order. This is what I gather: First element: Precedes all elements Minimal elements: Have no predecessors. The first element is always a minimal. Last element: ... 1answer 330 views ### How many possible DAGs are there with n vertices I am have n vertices and trying to enumerate all possible DAGs \theta over n. How many DAGs are there? For example when n=2, there are 3 possible DAGs and when n=3 I tried the following: |... 0answers 258 views ### Power-set in Hypercube: historical background of indexing each term like Hasse Diagram? My instructor wants references about the indexation over the hypercube, related question here, he does not believe that I was the first who used it -- [update] thanks to a comment, the name is Hasse ... 1answer 189 views ### Counting certain partitions of integers [Recall that] Young's lattice is a partially ordered set in which all partitions of integers are ordered thus: The elements just one step below any partition are those that you can get by subtracting ... 1answer 37 views ### Does every tree have an upper portion that is a non-empty chain? Given a poset P, call A \subseteq P an upper portion iff A^c < A, by which I just mean that for all a \in A^c and all b \in A we have that a < b. Then every upper portion is upward ... 3answers 6k views ### A finite set always has a maximum and a minimum. I am pretty confident that this statement is true. However, I am not sure how to prove it. Any hints/ideas/answers would be appreciated. 2answers 1k views ### Order preserving bijection from \mathbb Q\times \mathbb Q to \mathbb Q Do you have a simple example of order preserving bijection from \mathbb Q\times \mathbb Q to \mathbb Q? On \mathbb Q, I use the usual order and on \mathbb Q\times\mathbb Q, I define the ... 1answer 125 views ### Is this poset a lattice? Given the set \Bbb Z^+\times\Bbb Z^+ and the relation$$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
As I roughly know, a function $f$ in $\mathbb{R}$ is called order-preserving if $f(x)>f(y)$ for $x>y$, $x,y \in \mathbb{R}$. May I ask, if anybody knows the terminology for two functions $f$ ...