The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
2answers
296 views

Cardinality of Equivalence Relation of Eventually Sublinear Functions

Let $\Bbb{R}^{+}\_{0}$ be the set of non-negative real numbers and $\Bbb{R}^{+}$be the set of positive reals. Let us say that a function $f \colon \Bbb{R}^{+}\_{0} \to \Bbb{R}^{+}\_{0}$ is eventually ...
1
vote
0answers
192 views

existence of order preserving map [closed]

suppose A is a linear order set with a copy of rationals in it that is $A=B\cup\{\bar{r}:r\in\mathbb{Q}\cap[0,1]\}$. is there an orde preserving map that preservs sup and inf betwwen A and $[0,1]$ in ...
2
votes
1answer
170 views

Is there research on the notion of co-accessibility?

I want to start off with a disclaimer that I am only a mathematical amateur. Please forgive me for ignorance or any non-standard nomenclature I use here :) Let's start off with some context. Let X ...
5
votes
1answer
235 views

Complete anti-chain lattices and the axiom of choice

Hello, everyone. I'm trying to find out about lattices of anti-chains, and was wondering whether you could help me with getting to grips with a Comp. Sci. paper I'm struggling with. I've been reading ...
2
votes
1answer
225 views

Cardinality of group of order-preserving functions from R to R

The title pretty much says it all. What is the cardinality of $G$, the group of all functions $f: \mathbb{R} \to \mathbb{R}$ such that $\forall x,y\in \mathbb{R} \left( x>y\Rightarrow ...
6
votes
1answer
245 views

Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?

I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in ...
4
votes
1answer
337 views

Uncountable orderings

Let $P$ be an uncountable linear ordering. Is it true that either $P$ contains an order-copy of $\omega_1$ or there is $x_0\in P$ such that there exist uncountably many distinct $y\in P$ with $y< ...
4
votes
2answers
324 views

Definition of continuous functions in order theory

If we have a complete partial order (i.e. directed complete) I find frequently the following definition of a continuous function. A function $f:A\to B$ where $A$ and $B$ are cpos is called continuous ...
3
votes
2answers
162 views

A linearly orderable monoid which does not embed into a linearly orderable group

It is known (after an example of A.I. Mal'cev) that there exist cancellative semigroups which do not embed into a group. On the other hand, it is not difficult to see that every linearly orderable ...
0
votes
0answers
223 views

Transitive closures and inductive reasoning [solved]

Let's say that r is an endorelation over A (i.e. $r$ is a subset of $A \times A$), $\bar{r}$ is the transitive closure of r (i.e. the least set containing r and being transitive). Furthermore $r$ has ...
0
votes
1answer
169 views

wellfounded sets and predecessors

Following question: Let's assume that W is a wellfounded set, i.e. it has a partial order and every nonempty subset of W has minimal elements with respect to the order. Now we can easily define a ...
1
vote
0answers
125 views

How many more join-irreducibles can there be in a sub join-semilattice of a finite lattice?

Let $L$ be a finite lattice. Then $L$ is generated by its join-irreducible elements $J(L)$ or alternatively its meet-irreducible elements $M(L)$. If $S \subseteq L$ is a sub join-semilattice then ...
2
votes
0answers
117 views

Generalization of order dimension and interval orders

A partial order $(X, <_X)$ has order dimension $n$ if it can be realized as the product order of $n$ total orders, which means that there is an order-embedding between $(X, \lt_X)$ and $(Y^n, ...
2
votes
3answers
304 views

A characterisation of Boolean algebras

Let $M$ be a meet-semilattice with a least element $0$. Suppose there is an order-reversing involution $a \mapsto -a$ on $M$ such that for all $a, b \in M$, $a \wedge b = 0$ if and only if $b \le ...
1
vote
1answer
198 views

Strictly totally ordered semigroups - Looking for references

Let $\mathfrak A = (A, \cdot)$ be a semigroup (written multiplicatively). We say that $\mathfrak A$ is linearly orderable if there exists a total order $\le$ on $A$ such that $ac < bc$ and $ca < ...
5
votes
1answer
317 views

Characterizing $\omega_1$-like dense linear orderings

I recently came upon the following theorem which was attributed to J. Conway: For each $A\subset \omega_1$, let $\Phi(A)$ be a linear ordering of type $\sum_{\alpha<\omega_1} \tau_\alpha$, where ...
6
votes
1answer
410 views

Strictly order preserving maps into the integers

If $P$ and $P'$ are partial orders, a strictly order preserving map from $P$ to $P'$ is an $f:P\to P'$ satisfying that $x\lt y$ implies $f(x)\lt f(y)$ for all $x,y\in P$. An interval in $P$ is a set ...
3
votes
2answers
451 views

Cantor theorem on orders

It is "a well-known theorem of Cantor", said Sierpinski (circa 1920), that every countable total order can be imbedded in the rationals, and he proceeds to demonstrate that, assuming the continuum ...
0
votes
1answer
382 views

A property of a product of posets

Let $\mathfrak{A}$ is a poset. For $a, b \in \mathfrak{A}$ we will denote $a \curlyvee b$ if only if there is a non-least element $c$ such that $c \leqslant a \wedge c \leqslant b$. I call a poset ...
1
vote
1answer
206 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
260 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
407 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
622 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
319 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
330 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 ...
4
votes
0answers
189 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
528 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
871 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
601 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
588 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
296 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
197 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
394 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
252 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
365 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
243 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
209 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
203 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
251 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
403 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
775 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
260 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
688 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
832 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
570 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 ...