The tag has no usage guidance.

learn more… | top users | synonyms

6
votes
1answer
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
2answers
916 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
1answer
625 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
1answer
652 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
1answer
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
3answers
476 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
1answer
538 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
2answers
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
2answers
593 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
4answers
870 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
0answers
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
2answers
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
1answer
921 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
1answer
395 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
1answer
324 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
1answer
339 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
2answers
201 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
2answers
649 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
2answers
532 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
748 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
1answer
207 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
2answers
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
0answers
329 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
1answer
458 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
2answers
293 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
0answers
273 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
2answers
298 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
0answers
387 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
3answers
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
4answers
1k views

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

Are the computable numbers one example?
3
votes
2answers
443 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 ...
28
votes
4answers
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
4answers
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
1answer
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
0answers
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
2answers
441 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 ...
1
vote
1answer
572 views

The poset of k-small downward-closed subposets of a poset P is k-filtered when k is a regular cardinal?

Let $\kappa$ be a cardinal, and let $P$ be a poset. Let $\mathcal{P}_\kappa(P)$ denote the poset of $\kappa$-small subposets of $P$ and let ...
3
votes
2answers
202 views

Finite categories and partial orders

I'm studying category theory for the first time in a very succint book for computer scientists (I'm not actually a computer scientist, I'm a physicist, but my interest in cat theory is related to ...
3
votes
0answers
180 views

How linearly independent are the obvious combinatorial invariants of a Bruhat interval?

Let $[u, v]$ be a Bruhat interval in some Coxeter group. Let $I$ be the set of all Bruhat intervals. I am interested in functions $I \to \mathbb{Z}$ which are invariant under poset isomorphisms. ...
7
votes
1answer
295 views

Monotonic maximal chains in a Coxeter group

Let $(W, S)$ be a Coxeter system, and let $T = \bigcup_{w \in W, s \in S} wsw^{-1}$. Associated to every element $t \in T$ is a unique positive root $\alpha_t \in \Phi^{+}$ considered as a vector in ...
11
votes
1answer
530 views

Any further applications of Freudenthal's 1936 Spectral Theorem?

Seemingly completely forgotten, back in 1936, the Dutch mathematician Freudenthal, quite well known at the time, proved his so called Spectral Theorem, see chapter 6 in Luxemburg & Zaanen : Riesz ...
15
votes
3answers
873 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}$, ...
0
votes
0answers
178 views

Vector-valued valuations on lattices

There's a fair amount of work on valuations on (modular) lattices, by which I mean functions $v : \mathcal{L} \rightarrow R$ that satisfy the modular expression $$v(x) + v(y) = v(x \wedge y) + v(x ...
12
votes
5answers
2k views

Explicit ordering on set with larger cardinality than R

Is it possible to construct (without using Axoim of Choice) a totally ordered set S with cardinality larger than $\mathbb{R}$? Motivation: A total ordering is often called a “linear ordering”. I have ...
28
votes
2answers
696 views

What is the minimal size of a partial order that is universal for all partial orders of size n?

A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds order-preservingly into $\mathbb{B}$. For example, every partial order ...
3
votes
2answers
1k views

Cyclic order relation in Zn

The ring Zn:={0,1,..,n-1} under addition and multiplication modulo n. Suppose a,b,c,x $\in$ Zn are nonzero and the cyclic order R(a,b,c) holds, then under what conditions does R(ax,bx,cx) hold ?
8
votes
4answers
844 views

Order types of positive reals

Suppose one has a set $S$ of positive real numbers, such that the usual numerical ordering on $S$ is a well-ordering. Is it possible for $S$ to have any countable ordinal as its order type, or are the ...
6
votes
1answer
869 views

Correspondence between functions on a set and “states” on its power set

Let $L$ be the poset (ordered by set inclusion) that is the power set of some set $X$. A state is a function $s:L \rightarrow [0,1]$ satisfying i) for {$p_1,p_2,...$}, $p_i \in L$ a pairwise ...
-2
votes
1answer
649 views

Terminology: Lexicographical order [closed]

I would like to order a group of things by a set of rules of decreasing precedence. Please critique this sentence to help illustrate that: We define a lexicographical ordering for sheep by looking at ...
3
votes
4answers
479 views

(a,b) ≤ (a',b') iff b ≤ a' or (b' = b and a ≤ a') where a≤b and a'≤b'. Has any one seen this order?

I have been mucking round with orders, and this is the order that I found I needed. I would like to know if it is defined somewhere else, it is kind of difficult to search for such things. *EDIT* ...