All Questions
Tagged with set-theory order-theory
34 questions
8
votes
2
answers
698
views
Order type of $\alpha$-computable well-orderings
One of the nice features of the first admissible ordinal after $\omega$, i.e. $\omega_1^{CK}$, is that it is the collection of ordinals whose order type is that of a computable well-ordering on $\...
- 2,221
16
votes
1
answer
2k
views
totally ordered chain in the powerset with big cardinality
Let $B$ be some set. The problem is to find a set $A\subset\mathcal{P}(B)$ of subsets of $B$ which is totally ordered by inclusion and such that there exists a bijection $A\leftrightarrow \mathcal{P}(...
- 642
34
votes
3
answers
2k
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 ...
- 65.4k
31
votes
3
answers
2k
views
Is the fixed point property for posets preserved by products?
Recall that a partially ordered set (poset) $P$ has the fixed point property (FPP) if any order preserving function $f:P\longrightarrow P$ has a fixed point.
Theorem. Suppose $P$ and $Q$ are posets ...
- 1,872
2
votes
1
answer
973
views
Compactness and completeness in Gödel logic
The standard proof of the completeness theorem in first-order Gödel logic is based
on a first-order countable language. I want to know that is there any proof of the completeness theorem in first-...
- 49
24
votes
2
answers
1k
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 ...
- 236k
16
votes
4
answers
4k
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 ...
- 1,593
12
votes
4
answers
1k
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 ...
- 656
6
votes
1
answer
223
views
Minimal Hausdorff topologies compatible with a bunch of functions
Let $X$ be an infinite set, let ${\cal F}$ be a set of functions $f: X\to X$. We say that a topology $\tau$ is compatible with ${\cal F}$ if every $f\in {\cal F}$ is a continuous function $f:(X, \tau)\...
- 48.9k
24
votes
3
answers
2k
views
Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?
Is it possible to construct an infinite subset of $\Bbb R$ that is not order isomorphic to any proper subset of itself?
- 343
20
votes
2
answers
1k
views
An order type $\tau$ equal to its power $\tau^n, n>2$
(This is a re-post of my old unanswered question from Math.SE)
For purposes of this question, let's concern ourselves only with linear (but not necessarily well-founded) order types.
Recall that:
$...
- 6,819
11
votes
1
answer
418
views
A monotone countably cofinal function from $\omega^\omega$ to $\omega^{\omega_1}$
For a set $X$ we endow the set $\omega^X$ of all functions from $X$ to $\omega$ with the natural partial order $\le$ defined by $f\le g$ iff $f(x)\le g(x)$ for all $x\in X$.
A function $f:\omega^\...
- 41.8k
10
votes
0
answers
381
views
Can one define in ZFC a directed system of embeddings on the class of all linear orders realizing the surreal line as the direct limit?
Consider the surreal line $\langle\newcommand\No{\text{No}}\No,\leq\rangle$, in its order structure only. This is a proper class linear order, which is universal for all set-sized linear orders, as ...
- 236k
9
votes
2
answers
1k
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 ...
- 3,982
7
votes
1
answer
952
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 ...
- 32.5k
7
votes
1
answer
278
views
Incomparable dense linear orderings extending $\langle \mathbb{R},< \rangle$
Where $a<b$, say that the four “types” of non-empty bounded intervals are:
$(a,b)$, $[a,b]$, $(a,b]$, and $[a,b)$.
Let $\langle X,< \rangle$ and $\langle Y,< \rangle$ be dense linear ...
- 449
6
votes
1
answer
229
views
Smallest ordinal $\mu$ not embeddable in ${\cal P}(\omega)$
The motivation for this question is the startling fact that there is an order-preserving injective map (embedding) from $\mathbb{R}$ into ${\cal P}(\omega)$. (Think Dedekind cuts.) I am wondering how &...
- 48.9k
5
votes
1
answer
356
views
Calculate the $\downarrow$, $\downarrow\uparrow$ and $\uparrow\downarrow$ cofinalities of the poset of nontrivial finitary partitions of $\omega$
Let $(P,\le)$ be a poset. For a point $x\in P$ let
$${\downarrow}x=\{p\in P:p\le x\}\quad\text{and}\quad{\uparrow}x=\{p\in P:x\le p\}$$be the lower and upper sets of the point $x$, and for a subset $...
- 41.8k
5
votes
0
answers
134
views
Chains of length $2^\kappa$ in ${\cal P}(\kappa)$ [duplicate]
It is a fact that continues to boggle my mind: There is a set ${\cal C}\subseteq {\cal P}(\omega)$ such that $|{\cal C}|=\frak{c}=2^{\aleph_0}$ and for all $A,B\in{\cal C}$ we have $A\subseteq B$ or $...
- 48.9k
5
votes
2
answers
352
views
The cofinality of the poset $[\kappa]^{<\kappa}$ for a singular cardinal $\kappa$
For a cardinal $\kappa$ let $[\kappa]^{<\kappa}$ denote the family of subsets of cardinality $<\kappa$ in $\kappa$. The family $[\kappa]^{<\kappa}$ is endowed with the partial order of ...
- 41.8k
4
votes
1
answer
260
views
Is ${\cal P}(\omega)/\text{(fin)}$ a fractal poset?
If $(P,\leq)$ is a partially ordered set and $a,b\in P$ we set $[a,b]:=\{x\in P: a\leq x\leq b\}$. We say that $P$ is fractal if whenever $a,b\in P$ and $[a,b]$ contains more than one element, then $[...
- 48.9k
4
votes
1
answer
648
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 $\...
- 2,882
4
votes
2
answers
657
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 ...
- 3,630
4
votes
1
answer
227
views
Cardinality of maximal chains in the poset of ultrafilters with Rudin-Keisler ordering
Let $\text{NPU}(\omega)$ be the set of non-principal ultafilters on $\omega$. The Rudin-Keisler preorder on $\text{NPU}(\omega)$ is defined by
$${\cal U} \leq_{RK} {\cal V} :\Leftrightarrow (\exists f:...
- 48.9k
4
votes
1
answer
416
views
"Lexicographic" ordering on ${\cal P}(\omega)$
For $A\neq B\in {\cal P}(\omega)$ we set $$\mu(A,B) = \min\big((A\setminus B)\cup (B\setminus A)\big).$$ We define $A < B$ if and only if $A \neq B$, and
$A = B\cap \mu(A,B)$ (that is $A$ is an ...
- 48.9k
4
votes
0
answers
435
views
Can infinite bounded distibutive lattices be "arbitrarily wide"?
I was always thinking, in an informal way, that the powerset lattices ${\cal P}(X)$ (where $X$ is an infinite set) are the "widest" bounded distributive lattices with respect to their height. (In ${\...
- 48.9k
4
votes
2
answers
220
views
locally incomparable dense linear orderings extending $\langle \mathbb{R}, < \rangle$
This follows up on Incomparable dense linear orderings extending $\langle \mathbb{R},< \rangle$
and hopefully sparks more discussion.
Where $a<b$, say that the four “types” of nonempty bounded ...
- 449
3
votes
3
answers
3k
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$, ...
- 113
3
votes
2
answers
432
views
When is a filter generated by a (countable) chain?
In any partial order $(P,\leq)$ it is easy to see that every chain generates (i.e., by taking the upwards closure) a filter, and any filter built as a result of the Rasiowa-Sikorski lemma in forcing ...
- 3,115
2
votes
1
answer
282
views
Infima in the Rudin-Keisler ordering
Let $\text{NPU}(\omega)$ be the set of non-principal ultafilters on $\omega$. The Rudin-Keisler preorder on $\text{NPU}(\omega)$ is defined by
$${\cal U} \leq_{RK} {\cal V} :\Leftrightarrow (\exists f:...
- 48.9k
2
votes
1
answer
256
views
Chains of maximum cardinality in distributive lattices
It's quite straightforward to construct a (complete) lattice in which no chain has maximum cardinality: for each $n\in \omega\setminus\{0\}$ let $C_n$ be a copy of $n$ with the chain ordering ...
- 48.9k
2
votes
1
answer
356
views
getting one tower from two
Suppose that $(L,\leq_L,0,1)$ is a distributive and complemented Lattice that is dense as an order (i.e. if $a<_L b\in L$ then there exists $x\in L$, s.t. $a<_L x<_L b$)
Suppose that there ...
- 469
2
votes
2
answers
279
views
About the existence of a particular kind of "splitting" function on atomless complete Boolean algebras
Let $\mathbb{B} = \langle B, \wedge, \vee, \leq, \neg, 0, 1 \rangle$ be an atomless complete Boolean algebra.
We call $f$ a splitting function on $\mathbb{B}$ iff
$f : B-\{1\} \longrightarrow B \...
- 1,328
1
vote
0
answers
54
views
getting one tower from two (stronger hypothesis than a previous question with same title)
Suppose that $(L,\leq_L,0,1)$ is a Boolean algebra that is dense as an order (i.e. if $a<_L b\in L$ then there exists $x\in L$, s.t. $a<_L x<_L b$) s.t all non trivial closed segments are ...
- 469