The tag has no wiki summary.

learn more… | top users | synonyms

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
609 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
898 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
717 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
827 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
587 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
468 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
701 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. ...
11
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 ...
10
votes
1answer
696 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
576 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
562 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
559 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
481 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
419 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
361 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, ...
12
votes
2answers
495 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
461 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 ...
7
votes
2answers
932 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 ...
17
votes
2answers
574 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
305 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
283 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
219 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
232 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
285 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
391 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
7answers
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
369 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
403 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
515 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
919 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 ...