The order-theory tag has no usage guidance.

**9**

votes

**0**answers

198 views

### Reference for sparseness of incomparability graphs implying sparseness of covering graphs

If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the ...

**1**

vote

**2**answers

424 views

### Definition of $\beta$-limit ordinals

Hello,
I am reading Rosenstein's "Linear Orderings" and I am not sure if I am missing something, or if there is an error.
He gives the definition of a $\beta$-limit ordinal inductively, as follows ...

**1**

vote

**2**answers

260 views

### Automorphisms of locally finite countable posets-2

Given is a locally finite countable connected poset which satisfies further the following properties:
Let $C$ be any maximal chain ( i.e. inextendible chain) and $A$ be any antichain. Then $A$ is ...

**1**

vote

**1**answer

372 views

### Causal sets quantization

Hi,
Here are a couple of questions:
Is there a way to classify all homomorphisms between two finite posets?
Same question as (1) but for infinite, locally finite countable connected posets.
...

**4**

votes

**1**answer

252 views

### Automorphisms of locally finite countable posets

I rephrase my last question. Given a locally finite countable connected (as a graph) poset which satisfies the following further condition: the intersection of any antichain with the set of elements ...

**2**

votes

**1**answer

217 views

### Automorphisms of locally finite countable posets

Hi,
Is the automorphism group of a countable locally finite connected poset finite or countable?
If not, is there a way to equipp it (the uncountable group) with a topology and a measure?
Need this ...

**1**

vote

**0**answers

212 views

### What is known about orbifolding ordered groups and sets? Who has been involved? Links to Lee metrics?

In mathematical music theory several ordered groups are considered. Some examples contain the frequency space or Tonnetzes. Other groups (commutative and non-commutative ones) are discussed by Dawid ...

**2**

votes

**2**answers

282 views

### Algorithm to compute certain poset from a given poset.

Hi. Associated with a finite poset $P$, one can consider the poset $S(P)$, whose elements are the intervals of $P$, ordered by inclusion. (See Discrete version of Nullstellensatz? for some motivation ...

**4**

votes

**1**answer

468 views

### Intervals in posets: how to extend interval orders, Allen's algebra, and interval graphs to intervals of posets?

BACKGROUND
Assume a poset $\langle P, \le \rangle$. For two points $a,b \in P$
with $a \le b$, then $I = [a,b] = \{ x : a \le x \le b \}$ is the
interval between $a$ and $b$.
When $P$ is a chain ...

**10**

votes

**1**answer

802 views

### Discrete version of Nullstellensatz?

Hi. I was reading the paper "On the foundations of combinatorial theory (VI): The idea of a generating function" by Doubilet, Rota and Stanley, and there is a relation treated which is very ...

**0**

votes

**1**answer

308 views

### Power of an order relation

Let there be > included in AxB as a binary relation.
What does (x)>^2(y) mean? What is the meaning of an order relation raised to a power?
My first tought was that >^2 = >x> which is a cartesian ...

**2**

votes

**1**answer

268 views

### is $ded^{*}(\kappa)< ded(\kappa)$ consistent?

Hello,
I wonder if anyone knows this.
Definition:
$ded\left(\lambda\right)$ is the supremum of all sizes
of linear orders with a dense subset of size $\lambda$.
$ded^{*}\left(\lambda\right)$ is ...

**8**

votes

**2**answers

725 views

### Is $Ded(\kappa)<Ded(\kappa)^\omega$ consistent?

Hello,
I want to ask if anyone can tells us what is known (consistently) about $Ded(\kappa)$, $\kappa$ an infinite cardinal.
Definition If there is a dense linear order w/o endpoints of size ...

**3**

votes

**1**answer

574 views

### Height of ordered set

In all "constructive" fixed-point theorems for functions on ordered sets that I am aware of, where the fixed point is obtained as the limit of a stationary increasing transfinite sequence, it is ...

**6**

votes

**1**answer

1k views

### Probability distributions: The maximum of a pair of iid draws, where the minimum is an order statistic of other minimums?

General question: What is the distribution for the maximum of 2 independent draws from cdf F(x), when we know that the minimum of those same two draws is the kth order statistic of the minimum of n ...

**0**

votes

**2**answers

954 views

### order-preserving question

A B are totally-ordered sets and there exist two maps f and g such that f is a order-preserving injection from A to B and g is a order-preserving injection from B to A.
Q: Are A and B necessarily ...

**8**

votes

**1**answer

650 views

### Which countable linear orders are $\aleph_0$-categorical?

The question is: Which countable linear orders are $\aleph_0$-categorical?
I have a bit of progress on this:
Define a discrete tuple to be a set of elements, ordered discretely, such that if $a$ and ...

**12**

votes

**1**answer

657 views

### Converse to Banach’s fixed point theorem for ordered fields?

Suppose $R$ is an ordered field. Call a continuous map $f: R \rightarrow R$ a contraction if there exists $r < 1$ (in $R$) such that $|f(x)-f(y)| \leq r |x-y|$ for all $x,y \in R$ (where $|x| := ...

**7**

votes

**1**answer

2k views

### Number of graphs with a given number of nodes, edges and triangles

Hi. Does anyone know if it is possible to enumerate the set of labeled/unlabeled graphs (loopless, undirected, only one edge between pairs of nodes) having a given number of nodes, edges and ...

**0**

votes

**3**answers

490 views

### way-below relation

Wiki says that an infinite set may be way-below another set.
More precisely, in a power set, pow(S), with subset order and with X and Y subsets of S, does X way-below Y entail that X is finite?
...

**5**

votes

**1**answer

540 views

### Bridge game with only one suit: strategy

This game looks like bridge, but 1- there are only two players Alice and Bob, 2- there is only one suit, whose cards are numbered $1, 2,\ldots,2n$. One deals each player $n$ cards. Therefore Alice ...

**0**

votes

**2**answers

1k views

### Topological sort of partial order into sorted sets

Given a partial order of elements, one can use topological sorting to produce a sorted list of elements. For example, if we have the partial order A->B and A->C, then the possible topological sort ...

**3**

votes

**2**answers

605 views

### Is it reasonable to define `poset homotopy' as a `natural transformation of posets'?

Pausing to speak metaphorically for a bit, I have always thought of partial orders as being something like a simplified version of topological spaces. (In the finite case at least, all topological ...

**9**

votes

**4**answers

881 views

### Universal order type

Every countable order type, such as the countable ordinals, $\mathbb Z$, etc. can be embedded in $\mathbb Q$, so it is universal for countable order types. Is there a universal space for all linear ...

**2**

votes

**0**answers

78 views

### A specific notion between the notions of transversal and system of distinct representatives.

Let $X$ be a set, let $\mathcal{C}$ be a collection of subsets of $X$, and let $x_1, \dots , x_k \in X$. Say that the sequence $\{x_i\}_{i=1\dots k}$ is a sequential transversal (of length $k$) ...

**1**

vote

**2**answers

362 views

### Semilattices with n elements

How many n-element semilattices there are?
For example, for n-element partially ordered set we can figured out, that there are $2^{n*(n-1)}$ possible sets.
And can I find all possible n-element ...

**3**

votes

**1**answer

952 views

### Well ordering of countably branching well founded trees

Hello everybody,
I would like to say, before stating the question, that I'm not a mathematician, and therefore i apologize in advance if the question is trivial, or well-known. I'll try to state it ...

**8**

votes

**1**answer

398 views

### Does this “flipping lexicographic” ordering have a standard name?

I’ve run into the following straightforward variant of lexicographic ordering, and am wondering if it has a standard name. I’ve been calling it the flipping lexicographic ordering, for evident ...

**1**

vote

**1**answer

326 views

### Modern books about orders and algebras on trees [closed]

Please help to find books about orders and algebras on trees.
If there is no modern books, please advice good old ones!
I'm more interested in finite trees (my current problem), but infinite ones are ...

**8**

votes

**1**answer

343 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 ...

**2**

votes

**2**answers

204 views

### Of what kind of complemented bounded poset are the structures in my quasi-variety?

I feel that my question is very basic, but, somewhat suprisingly, nobody was able to give me an answer so far:
Let
$\mathbf{M} := \langle \{ 0,1 \}, 0, 1, \leq, \neg \rangle$
be the structure with ...

**7**

votes

**2**answers

656 views

### Given a cardinal k, what's the biggest dense linear order with a dense subset of size k?

It's not hard to show that for any cardinal $\kappa$, there is no dense linear order without endpoints (DLO) of size greater than $2^{\kappa}$ that has a dense subset of size $\kappa$. But one can ...

**2**

votes

**2**answers

541 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

**2**answers

762 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< ...

**0**

votes

**1**answer

209 views

### Is every countable well-order embeddable in \mathbb{R}? [duplicate]

Possible Duplicate:
Order types of positive reals
The title is self-explanatory.

**3**

votes

**2**answers

242 views

### What do you call a lattice whose meet operation preserves disjointness of subsets?

To make my question more precise and compact (and probably more intuitive), let me define the following:
A subset $S$ of a lattice is mutually disjoint if for each $x \in S$, $\bigvee(S - \lbrace x ...

**1**

vote

**0**answers

332 views

### Functoriality of a standard integral domain construction.

The evident forgetful functor from fields to integral domains has a left adjoint, namely the construction of the quotient field for a given integral domain. Another standard construction is taking the ...

**10**

votes

**1**answer

461 views

### Partial word orders on groups

This is a followup question related to this question. Recall that a left-invariant partial order on a finitely generated group $G$ is called a partial word order if for every $a\le b\le c$ we have ...

**6**

votes

**2**answers

298 views

### orders and length functions on finitely generated groups

Let $G$ be a finitely generated group with the natural word length function ($|x|$ is the length of the shortest word in generators of $G$ representing $x$). We call a partial left invariant order ...

**8**

votes

**0**answers

274 views

### Higher-order dimension in posets: a reference request

Let $P = (X, \le)$ be a partially-ordered set. Then the dimension of $P$ is the minimum number of total orders over $X$ whose intersection yields $P$. Alternately, the dimension of $P$ is the minimum ...

**0**

votes

**2**answers

301 views

### Is this a pre-ordered commutative semigroup?

Motivation
I'm studying an approach to axiomatic thermodynamics based on the notion of commutative semigroup $(S,+)$ with a preorder relation $\to$ on $S$. In other words, $S$ is non-empty set, the ...

**3**

votes

**0**answers

396 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 ...

**15**

votes

**3**answers

3k 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 ...

**3**

votes

**4**answers

1k views

### What are examples of ordered fields that do not have the Archimedean Property?

Are the computable numbers one example?

**3**

votes

**2**answers

445 views

### Arithmetic of ordered sets more general than ordinals

Motivation. Having read about infinite time Turing machines and ω-languages, I was thinking about more general notions of languages and “computation time”. Languages over strings of length ...

**29**

votes

**4**answers

2k views

### A principle of mathematical induction for partially ordered sets with infima?

Recently I learned that there is a useful analogue of mathematical induction over $\mathbb{R}$ (more precisely, over intervals of the form $[a,\infty)$ or $[a,b]$). It turns out that this is an old ...

**19**

votes

**4**answers

1k views

### When does a Galois connection induce a topology?

Let $(X,\leq)$ and $(Y,\leq)$ by partially ordered sets. Recall that a(n antitone) Galois connection between $X$ and $Y$ is a pair of order-reversing maps
$\Phi: X \rightarrow Y, \ \Psi: Y ...

**-3**

votes

**1**answer

213 views

### not sure what these basic FO symbols mean [closed]

I know some basic logic symbols, but i'm not sure what this formula means:
Fragment:
http://i35.tinypic.com/14jt1n9.png
Full paper:
http://www.newton.ac.uk/preprints/NI07003.pdf
in particular, what ...

**3**

votes

**0**answers

195 views

### An elegant formulation for typed sets

Fix a poset $T$, which we'll think of as a set of "types," interpreting $a \leq b$ as "$a$ is more general than $b$." Construct a category of TSet as follows.
Objects: Pairs ($X$, $\tau : X ...

**5**

votes

**2**answers

447 views

### Fraissé limit of the finite linear orderings

Hodges in his Shorter Model Theory promises to show "in what sense the finite linear orderings 'tend to' the rationals rather than, say, the ordering of the integers" (p. 160). After going through his ...