The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
204 views

Order density of smooth functions among continuous functions?

Let $\mathcal{C}^0([a,b],\mathbb{R})$ be the space of all continuous functions $f:[a,b]\rightarrow\mathbb{R}$ and $\mathcal{C}^\infty([a,b],\mathbb{R})$ the subspace of all smooth functions. Define ...
2
votes
1answer
257 views

Is there a Dirichlet Unitary Unit Theorem?

Dirichlet's unit theorem computes the group of units of the algebraic numbers of a number field. There are a few generalisations for orders available. Assume the order has an involution. For example, ...
6
votes
0answers
388 views

What is the structure of a space of $\sigma$-algebras?

Let $X$ be a compact metric space, and consider the Banach space $\Omega = C(X,\mathbb R)$ of continuous, real-valued functions on $X$, equipped with the supremum norm. Let $\delta_x \in \Omega^*$ be ...
12
votes
1answer
593 views

Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?

It is well known that every partial order on a set can be extended to a linear order on that set. That is, for every partial order $\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such that ...
7
votes
3answers
316 views

Extracting countable chains from linear orders

There is a well-known fact in infinite combinatorics asserting that for each infinite linear order $P$ there is a countable subset $R\subseteq P$ of order type either $\omega$ or $\omega^{*}$ (by ...
1
vote
1answer
321 views

Complete De Morgan algebra

Recall that an algebra $(A,\sim)$ is a De Morgan algebra if $A$ is a bounded distributive lattice and $\sim$ is a unary operation which satisfies: ${\sim} (x\vee y)={\sim} x\wedge {\sim} y$ and ...
3
votes
0answers
185 views

Oriented matroids and posets?

Is there a characterization of oriented matroids in terms of order theory, similar to that of matroids as geometric lattices? Does this question make sense at all? I have seen (for instance in ...
6
votes
1answer
510 views

A categorical characterization of the lexicographic order

In $Pos$ (the category of partial ordered sets and order preserving maps) there is the categorical product of two objects, but on the set product there is (naturally) also the lexicographic order. I ...
0
votes
3answers
804 views

Well-ordered cofinal subsets [closed]

Let $(P, \leq)$ be a total ordering (some of you prefer the name linear order). Can we find a subset $R\subseteq P$ which is well ordered (with respect to $\leq\upharpoonright R$) and cofinal in $P$, ...
6
votes
1answer
600 views

How this set of functions is ordered?

Notation: $k, m, n$ are non-negative integers $f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$ $f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$ $f \prec g$ means ...
3
votes
5answers
559 views

Visualizing large posets

Hi, does somebody know if there is any software for visualizing very large posets? (like those in page 27 of this notes of Guenter Ziegler). They may arise (as in that text) by considering the face ...
4
votes
2answers
295 views

Heights of several interesting posets

Let the height of a poset $P$ be the supremum of ordinals that are order types of all well-ordered subsets of $P$ (with order inherited from $P$). Define several sets of total functions, in each ...
7
votes
2answers
335 views

Ordinals and complexity classes

What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size ...
3
votes
0answers
209 views

When Aut(M) preserves a linear order?

I have a general-type question: Suppose $M$ is a countable structure that is ultrahomogeneous, i.e. every (partial) isomorphism between finitely generated substructures of $M$ extends to an ...
9
votes
0answers
196 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
2answers
375 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
2answers
249 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
1answer
362 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
1answer
242 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
1answer
208 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
0answers
198 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
2answers
244 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
1answer
378 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
1answer
762 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
1answer
307 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
1answer
258 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
2answers
682 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
1answer
557 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
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
791 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
545 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 ...
11
votes
1answer
616 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
438 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
498 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
828 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
564 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 ...
8
votes
4answers
800 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
77 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$) ...
0
votes
2answers
352 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
757 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
383 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
0answers
222 views

Modern books about orders and algebras on trees

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
330 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
188 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 ...
6
votes
2answers
591 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
506 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
644 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
203 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
238 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 ...