The order-theory tag has no wiki summary.

**3**

votes

**2**answers

439 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

**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

990 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

194 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

428 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

**1**answer

561 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

**2**answers

197 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

**0**answers

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

**1**answer

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

**9**

votes

**1**answer

437 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

**3**answers

845 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

**0**answers

171 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

**5**answers

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

**27**

votes

**2**answers

676 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

**2**answers

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

**4**answers

800 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

**1**answer

868 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

**1**answer

638 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

**4**answers

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

**22**

votes

**3**answers

722 views

### Does the exact pair phenomenon for partial orders occur in your area of mathematics?

Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if
...

**27**

votes

**9**answers

2k views

### How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...

**10**

votes

**5**answers

3k views

### infinite permutations

This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same ...

**12**

votes

**1**answer

804 views

### Kuratowski closure-complement problem for other mathematical objects?

The original Kuratowski closure-complement problem asks:
How many distinct sets can be obtained by repeatedly applying the set operations of closure and complement to a given starting subset of a ...

**5**

votes

**3**answers

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

**-3**

votes

**2**answers

641 views

### Weak partitioning vs. strong partitioning

Let $U$ is a complete lattice with least element 0.
Weak partitioning is a collection $S$ of nonempty subsets of $U$ such that $\forall x\in S: x\cap\bigcup(S\setminus\{x\})=0$.
Strong partitioning ...

**2**

votes

**4**answers

651 views

### Filter-closed vs. chain-closed

Let A is a complete lattice.
I call a subset $S$ of A filter-closed when for every filter base $T$ in $S$ we have $\bigcap T\in S$. (A filter base is a nonempty, down directed set.)
I call a subset ...

**3**

votes

**3**answers

224 views

### Name for “lower/upper bounds” of arbitrary relations?

Given a partial order $R_{\leq}$ over a set $D$, the set of upper bounds under $R$ of a subset $S$ of $D$ is commonly defined as $\{ y \in D | \ \forall x\in S, x R y \}$.
(The set of lower bounds of ...

**5**

votes

**2**answers

611 views

### Reconstruction puzzles

[Added: This is a follow-up of an earlier post.]
Consider the following "reconstruction puzzle", stated informally:
Given a concrete poset, e.g. the poset of undirected unlabeled finite graphs ...

**7**

votes

**1**answer

518 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

**2**answers

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

**6**

votes

**2**answers

386 views

### closure of separative quotients

Does there exist a partial order, nontrivial for forcing, that is countably closed, but whose separative quotient is not countably closed? Supposing the answer is yes, then is there a partial order, ...

**17**

votes

**2**answers

697 views

### Which are the rigid suborders of the real line?

Which are the rigid suborders of the real line?
If A is any set of reals, then it can be viewed as an order structure itself under the induced order (A,<). The question is, when is this structure ...

**1**

vote

**1**answer

152 views

### The proper name for a kind of ordered space [closed]

I'm trying to find the correct term for a specific kind of totally ordered space:
Let $S$ be a totally ordered space with strict total order $<$.
Property: For any two $s_{1}$ and $s_{2}$ in $S$ ...

**2**

votes

**3**answers

515 views

### Countable atomless boolean algebra covered by a larger boolean algebra

Suppose Q is an atomless countable boolean algebra, and B is an arbitrary atomless boolean algebra. Q is unique modulo isomorphisms. There is a subalgebra in B that is isomorphic to Q. There is ...

**6**

votes

**2**answers

984 views

### Ordinals that are not sets

The class of all ordinal numbers $\mathbf{Ord}$, aside being a proper class, can be thought of an ordinal number (of course it contains all ordinal numbers that are sets, not itself). Then one could ...

**22**

votes

**2**answers

716 views

### How much choice is needed to show that formally real fields can be ordered?

Background: a field is formally real if -1 is not a sum of squares of elements in that field. An ordering on a field is a linear ordering which is (in exactly the sense that you would guess if you ...

**3**

votes

**2**answers

325 views

### Semilattices in atomless boolean algebras

Let S be a bounded semilattice without maximal elements. Can we always construct an atomless boolean algebra B, containing S as a subsemilattice, such that S is cofinal in B-{1}? That is, for every ...

**0**

votes

**2**answers

302 views

### name for “solid” subset of a partially ordered set?

For P a partially ordered set, let S be a subset of P such that if:
a,c\in S and b\in P and a<=b<=c then b\in S
Is there a name for a subset with this property? The term "dense" subset is ...

**-3**

votes

**1**answer

226 views

### Ordering of tuples equivalent to mapping to R?

Suppose we have a non-strict total ordering on tuples of real numbers (the ordering includes tuples of differing lengths). Any tuple, t2, generated from another tuple, t1, by increasing one or more ...

**4**

votes

**2**answers

253 views

### Is there a poset with 0 with countable automorphism group?

Is there a poset P with a unique least element, such that every element is covered by finitely many other elements of P (and P is locally finite -- actually, per David Speyer's example, let's say that ...

**0**

votes

**1**answer

307 views

### Determining set membership from ordering relationships among disjoint sets

Suppose we have a set $P$ (an infinite set), and we have a partition of $P$ into (finitely many) disjoint subsets $P_i$, so that $P = \cup_i P_i$, and $P_i \cap P_j = \emptyset$ for $i \neq j$.
...

**3**

votes

**2**answers

398 views

### Unbounded countable subset

(Edit: The first formulation is wrong. See the second answer) Does every totally ordered set contain an unbounded countable subset. In other words: If S is a totally ordered set, can we find a (edit: ...

**8**

votes

**6**answers

2k views

### Generalizations of Boolean posets/lattices

A Boolean lattice has a number of rather nice properties which give it a central role in many parts of combinatorics. For instance, it's a lattice, it can be augmented with a ring structure, it can ...

**20**

votes

**6**answers

2k views

### What's a non-abelian totally ordered group?

Because I have heard the phrase "totally ordered abelian group", I imagine there should be non-abelian ones. By this I mean a group with a total ordering (not to be confused with a well-ordering) ...

**2**

votes

**2**answers

404 views

### Automorphisms of the totally ordered group Z^n with lexicographical order

It is easy to see that the totally ordered group Z (the integers) with the natural order has no non-trivial automorphisms. Is this also true for Z^n with the lexicographical order?

**2**

votes

**1**answer

432 views

### Chains intersecting antichains in finite posets

I feel a little embarrassed to be asking this question here, since I think it should be much easier than I'm making it, but here goes:
Given a finite poset P, does there necessarily exist some chain ...

**3**

votes

**3**answers

549 views

### Is there a “universal LYM inequality?”

This question is based on a blog post of Qiaochu Yuan.
Let P be a locally finite* graded poset with a minimal element, and w be a weight function on the elements of P. Suppose that the total weight ...

**10**

votes

**5**answers

1k views

### Questions about ordering of reals and irrationals

Three problems from G.Rosenstein "Linear orderings" (from the end of Chapter 2 and beginning of Chapter 4):
1) Is there a nondecreasing function from irrationals onto reals?
2) Is there a ...