The tag has no wiki summary.

learn more… | top users | synonyms

19
votes
4answers
852 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
193 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 ...
4
votes
2answers
387 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
539 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
194 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 ...
2
votes
0answers
171 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
245 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 ...
8
votes
1answer
421 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 ...
14
votes
3answers
814 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
163 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 ...
10
votes
5answers
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
2answers
634 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
942 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
736 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
841 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
606 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
476 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
3answers
708 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 ...
23
votes
9answers
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
5answers
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 ...
11
votes
1answer
729 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
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 ...
-3
votes
2answers
613 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
4answers
606 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
3answers
217 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 ...
3
votes
2answers
584 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
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
426 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
2answers
369 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
2answers
654 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 ...
2
votes
3answers
480 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
2answers
943 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 ...
20
votes
2answers
623 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
2answers
308 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
2answers
293 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
1answer
223 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
2answers
241 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
1answer
290 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
2answers
393 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
6answers
1k 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 ...
19
votes
6answers
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
2answers
376 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
1answer
418 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
3answers
523 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 ...
8
votes
5answers
924 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 ...