# Tagged Questions

The tag has no usage guidance.

2k views

### Is every continuous function measurable?

This question has already been asked on Math StackExchange here, but was too old to be migrated, and I think will be more appropriate to MathOverflow. In non-Hausdorff topology it is standard to ...
1k views

### Is the fixed point property for posets preserved by products?

Recall that a partially ordered set (poset) $P$ has the fixed point property (FPP) if any order preserving function $f:P\longrightarrow P$ has a fixed point. Theorem. Suppose $P$ and $Q$ are posets ...
138 views

### reduction to np hard ordering problem

I am trying to show a reduction from a problem of ordering problem to an np-hard problem that has approximation poly-time algorithm. My problem is: I have M auctions and in each auction I have N ...
189 views

### Directed subposet of a poset containing the minimal elements

The following appears naturally in a certain context: Let $P$ be a graded partially ordered set. Let $M$ be the subset of minimal elements of $P$. Define subsets $E_i$ inductively as follows: First, ...
135 views

### Are there any results on well-quasi-ordering of languages?

There are a number of papers that I can find about well-quasi-orders in formal lnaguage theory, by Kunc, de Luca, D'Alessandro, and Varricchio, among others. I am interested, however, in well-quasi ...
103 views

### Mapping graphs to ordinals

Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...
310 views

### The category of categories and adjunctions

What is known about the category that has small categories as objects and adjunctions as morphisms? Obviously, it has neither terminal nor initial objects. But what about other kinds of limits? Are ...
136 views

### Can $Ded(\kappa)$ be a supremum?

Definition If there is a dense linear order w/o endpoints of size $\lambda$ with a dense subset of size $\kappa$ then write $D(\kappa,\lambda)$. $Ded(\kappa)=\sup_\lambda \{D(\kappa,\lambda)\}$. It ...
199 views

### Profinite completion of a partial order

In Johnstone's Stone Spaces it is proved that the category of profinite partial orders is (equivalent to) the category of ordered Stone spaces (also called Priestley spaces) and that the obvious ...
176 views

255 views

### Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...
118 views

### Linearly ordered set arithmetic: reference request

A lot has been written about the arithmetic of ordinal numbers. However, we can also do arithmetic with linearly ordered sets. Question. Is there an article or book where I can learn the basics of ...
323 views

### An equivariant Hahn Embedding Theorem?

The Hahn Embedding Theorem asserts that for any (linearly) ordered abelian group $\Lambda$, there exists a linearly ordered indexing set $\Omega$ such that $\Lambda$ admits an order-preserving group ...
423 views

### Which linearly ordered sets have the property that their completion is equipotent with their powerset?

As is well-known, ZFC proves the equipotency of $\mathbb{R}$ and $\mathcal{P}(\mathbb{Q}).$ Is there a nice characterization of those linearly ordered sets $L$ which, like $\mathbb{Q}$, have the ...
86 views

110 views

136 views

### Totally right preorderable groups

Are there any known non-trivial sufficient conditions, or full characterizations, of a totally right-preorderable group? More precisely: totally right-preorderable: has a non-trivial total right-...
105 views

### Expected size of $k$-th layer of a POSET

Is this known? What is the expected width of the $k$-th layer (anti-chain layer) of a $d$-dimensional partially ordered set of $n$ elements formed by product of $d$ random linear orders chosen from ...
218 views

### Proving equivalence of a tree-based version of Countable Choice for families of finite sets

In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5: Each of the following statements imply those beneath it. The countable union of ...
173 views

An exercise in Stanley's Enumerative Combinatorics (Chapter 3, ex. 8) asked for an example of a finite self-dual poset, (i.e. there is a bijection $f: P\to P$ such that $s\le t \Longleftrightarrow f(s)... 1answer 202 views ### Does every locally finite acyclic directed set embed into a linear order locally isomorphic to the integers? (Edit: extend, not merely embed.) Let$S=(S,\prec)$be a set together with an acyclic binary relation, generally nontransitive.$S$is locally finite if, for every element$x\in S$, the sets$\{w|w\prec x\}$("direct past of$x$") ... 1answer 309 views ### Does every countably infinite interval-finite partial order embed into the integers? A partially ordered set$(S,\le)$is called interval finite if the open intervals$(x,z):=\{y|x\le y\le z\}$are finite for all choices of$x,z$in$S$. An embedding$(S,\le)\rightarrow(S',\le')$of ... 1answer 155 views ### Linear order extensions on (nonabelian) groups If$G$is a group with a (left) linear order, does every (left) partial order on$G$extend to a (left) linear order? The answer is affirmative on abelian groups, where being torsion-free is ... 2answers 232 views ### Conditions for a group to be lattice-ordered Given a set$S$with a group operation$\cdot$and a lattice ordering$\leq$, I wish to know when we can say that$\cdot$preserves$\leq$, i.e.$(x\vee y)z=xz\vee yz$and similarly for meets. ... 2answers 384 views ### Extending a partial order while preserving an automorphism It is well known that if$(P, \leq)$is a partial order then$\leq$can always be extended to a linear order. This is sometimes called Szpilrajn´s theorem although it had been previously proved by ... 2answers 508 views ### Embedding a brouwerian lattice into a boolean lattice I have already asked a similar question at http://math.stackexchange.com/questions/470704/can-a-brouwerian-lattice-be-extended-into-a-boolean-algebra but have received no answer. Sorry, I ask a ... 2answers 245 views ### When is a filter generated by a (countable) chain? In any partial order$(P,\leq)$it is easy to see that every chain generates (i.e., by taking the upwards closure) a filter, and any filter built as a result of the Rasiowa-Sikorski lemma in forcing ... 1answer 490 views ### A characterization of the poset of filters on a set For the lattices of all subsets of a given set it is known an axiomatic characterization: A poset is isomorphic to a set of all subsets of some set iff it is a complete atomic boolean algebra. The ... 3answers 191 views ### Maximal chains in a quasi-order of linear order types Let$\mathcal{T}_\kappa$be the set of all linear order types of cardinality$\kappa$. Let$\prec$denote a binary relation on$\mathcal{T}_\kappa$representing embeddability of order types (note that ... 1answer 359 views ### What kind of category is a cyclically ordered set? Background: A preorder is a binary relation$\leq$which is reflexive and transitive. We can write the transitive property as${\leq}(a,b)\wedge{\leq}(b,c)\to{\leq}(a,c)$. There are additional axioms ... 1answer 180 views ### For what classes of comparability graphs are their complements also comparability graphs? An interval graph is an intersection graph of real intervals, that is, an undirected graph whose vertices can be labeled with real intervals so that there is an edge between two vertices iff their ... 1answer 234 views ### Terminology question for poset maps Is there a standard name for order-preserving maps$f\colon P\to Q$of posets with the property that the image of a lower set is a lower set, or equivalently if$q\leq f(p)$then there exists$p'\leq ...
Directed sets are defined to be sets equipped with a preorder that admit (finitary) upper bounds e.g. pairs $(D, \preceq)$ such that $\forall p,q \in D$ there exists $r \in D$ such that $p \preceq r$ ...
A continuous lattice is a complete lattice $L$ in which every element $y$ is equal to $\bigvee${$x \in L \mid x \ll y$} where $x \ll y$ ("x approximates y" or "x is way below y") if for any directed ...