A poset or partially ordered set is a set endowed with a partial order, meaning a binary relation $\leq$ which is reflexive ($x \leq x$ for all $x$) and transitive ($x\leq y$ and $y\leq z$ implies $x \leq z$).

learn more… | top users | synonyms

3
votes
1answer
155 views

Decomposing a poset into directed subposets

Let us say that a poset $P$ is $\mathbf{\kappa}$-directed iff every collection of fewer than $\kappa$-many elements in $P$ has an upper bound in $P$. $P$ has the $\mathbf{\kappa}$ chain condition iff ...
8
votes
1answer
323 views

Decomposing posets into countably many chains

A conjecture of Galvin's is that the following is possible (which I take to mean that the consistency of the following can be proven relative to the consistency of something like ZFC, or ZFC plus some ...
0
votes
1answer
286 views

Terminology for posets.

What should I call a poset with the property that each element has AT MOST ONE predecessor? (I'm actually interested in the special case in which there are no infinite descending chains.) ...
1
vote
2answers
892 views

On the number of antichains of a poset

I am not an expert in combinatorics, but I need to count (or to approximate) the number of antichains of a poset. The idea relies on approximating this number by embedding my poset into another one, ...
9
votes
1answer
303 views

Set of maximal subfields not containing particular elements.

Instead of extending a field, by adjoining a new element, consider what happens if we remove an element or elements. This started as a question on math.SE Field reductions where Pete L. Clark ...
5
votes
1answer
357 views

Does “antichain” mean something different in set-forcing than in lattice theory?

On page 3 of Introduction to Lattices and Order, Davey and Priestley define an antichain in a poset $\langle P,\leq\rangle$ as a set of pairwise incomparable elements: The ordered set P is an ...
7
votes
3answers
573 views

Characterizing forcings that don't add any dominating reals

Regarding reals as functions from $\omega$ to $\omega$, let's say a real $f$ eventually dominates $g$ iff $(\exists n)(\forall m > n)[ f(m) > g(m)]$. Let's say that a (non-trivial separative) ...
3
votes
2answers
497 views

A problem about posets similar to Suslin's problem

Suslin's problem is: Given a complete dense linear order without endpoints, if it has the ccc must it be isomorphic to $\mathbb{R}$? The answer is that it's independent of ZFC. The related ...
3
votes
2answers
623 views

Does order isomorphism of linear extensions of two partially ordered sets imply order isomorphism of themselves?

Consider two partially ordered sets $A = \{a< b,a< c\}$, $B=\{x< z,y< z\}$. Their linear extensions (here we allow equality in linear extensions) for $A, B$ are $$A_L=\{A_1=\{a< b< ...
2
votes
1answer
275 views

Count of lattices on finite set

Let $p(n)$ denote count of lattices on finite set $G$, $|G|=n$ (without isomorphism). It's know closed formula for $p(n)$? It's clear, that $1 \leq p(n)$ and also that $p(n-1) \leq p(n)$ for $n \geq ...
4
votes
1answer
293 views

Posets of finite sequences are highly connected

I need the following result for an example in a paper I'm writing. It's easy enough to prove, but I'd prefer to just give a reference. Does anyone know one? Fix $1 \leq k \leq n$. Define $X_{n,k}$ ...
3
votes
0answers
346 views

a poset with small “cycles”

(a followup to this recent question) I noticed the following curious property of a poset (which I strongly believe to be a lattice, I'm still trying to prove that...): Suppose that $z$ is covered by ...
14
votes
3answers
2k views

Proving that a poset is a lattice

I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably ...
7
votes
2answers
373 views

A sequence of generic filters that does not come from an iteration

Fix a countable transitive model $M$ of ZFC. In my answer to this question I indicated that there are forcing iterations $((Q_\alpha:\alpha\leq\omega),(\dot P_\alpha:\alpha<\omega))$ in $M$ and ...
14
votes
3answers
1k views

Banach and Knaster-Tarski fixed point theorems — are they related?

It there any known way of obtaining the Banach fixed-point theorem from the Tarski fixed-point theorem or vice-versa?
2
votes
1answer
254 views

Selecting k sub-posets

I ran into the following algorithmic problem while experimenting with classification algorithms. Elements are classified into a polyhierarchy, what I understand to be a poset with a single root ...
48
votes
6answers
11k views

How many orders of infinity are there?

Define a growth function to be a monotone increasing function $F: {\bf N} \to {\bf N}$, thus for instance $n \mapsto n^2$, $n \mapsto 2^n$, $n \mapsto 2^{2^n}$ are examples of growth functions. Let's ...
14
votes
3answers
813 views

Subposets of small Dushnik-Miller dimension

The Dushnik–Miller dimension of a partial order $(P,{\leq})$ is the smallest possible size $d$ for a family ${\leq_1},\ldots,{\leq_d}$ of total orderings of $P$ whose intersection is ${\leq}$, ...
2
votes
0answers
121 views

non-degenarete tools to calculate a derived functor on a model category which is a poset?

Are there theorems (esp. computational tools) on model categories which survive and do not trivialise when its underlying category is a (quasi-)poset ? Are there tools that may help to calculate ...
1
vote
2answers
854 views

Proof of glb and lub of Lexicographic Product of poset

Is there a book, or a paper where the Lexicographic glb and lub are proven commutative, associative, idempotent and absorbing. I have already proven this, but would like to check proofs, and a short ...
4
votes
4answers
761 views

Category = Groupoid x Poset?

Is it possible to split a given category $C$ up into its groupoid of isomorphisms and a category that resembles a poset? "Splitting up" should be that $C$ can be expressed as some kind of extension ...
5
votes
3answers
1k views

Constructing a metric over a lattice

Consider a lattice $({\cal L}, \wedge, \vee)$ with an antimonotonic function $f: {\cal L} \rightarrow {\mathbb R}$ defined on it (i.e $x \preceq y \implies f(x) \ge f(y)$). $f$ is said to be ...
7
votes
1answer
492 views

Does ⋄ generate all De Morgan algebras?

(Asked by Nathaniel Hellerstein on the Q&A board at JMM) This question is about De Morgan algebras (see also Wikipedia), which are something like Boolean algebras, but with a different weaker ...
4
votes
2answers
425 views

Is every lattice the fixed-point set of an order endomorphism of ⋄^n?

(Asked by Nathaniel Hellerstein on the Q&A board at JMM) Let ⋄ be the 4 element lattice τ / \ i j \ / f Is every lattice isomorphic to the fixed point lattice of some ...