All Questions
Tagged with set-theory order-theory
147 questions
43
votes
4
answers
4k
views
A principle of mathematical induction for partially ordered sets with infima?
Recently I learned that there is a useful analogue of mathematical induction over $\mathbb{R}$ (more precisely, over intervals of the form $[a,\infty)$ or $[a,b]$). It turns out that this is an old ...
- 65.4k
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
28
votes
1
answer
6k
views
What is the cofinality of the co-infinite subsets of ${\bf N}$?
Let ${\mathcal A}$ be the family of subsets $A$ of the natural numbers ${\mathbf N}$ which are co-infinite (i.e., their complement is infinite). We partially order this family by set inclusion. A ...
- 114k
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
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
24
votes
1
answer
2k
views
Why do we need "canonical" well orders?
(I asked this question on Math.SE earlier but received no response and am therefore moving it here, please note that I realise this question is probably incredibly naïve for the experienced set-...
- 343
23
votes
2
answers
670
views
Order type of the smallest set containing the identity function and closed under exponentiation
Let $E$ be the smallest set of functions $\mathbb{N}^+\to\mathbb{N}^+$ containing the identity function $n \mapsto n$ and closed under exponentiation $(f,g) \mapsto \left(n \mapsto f(n)^{g(n)}\right)$...
- 872
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
19
votes
1
answer
1k
views
Suprema of directed sets
Let $(X, \le)$ be a partially ordered set. We call a subset $S \subseteq X$...
... a chain if each two elements in $S$ are comparable with respect to $\le$ (in other words, $S$ is linearly ordered ...
- 12.6k
18
votes
2
answers
1k
views
Can all $\aleph_2$-dense subsets of $\mathbb{R}$ be isomorphic?
Let $\kappa$ be an infinite cardinal. For a subset $A \subseteq \mathbb{R}$, we say that $A$ is $\kappa$-dense if $|A \cap (a, b)| = \kappa$ for every interval $(a, b)$. By Cantor, any two $\aleph_0$-...
- 1,618
17
votes
2
answers
338
views
Is it possible to reconstruct an order type from its initial segments?
Suppose
$T$ is a totally ordered set without a maximal element,
$\tau$ is the order type of $T$,
$S$ is the set of order types of all proper initial segments (downward closed subsets) of $T$.
Is it ...
- 532
17
votes
1
answer
1k
views
Has the exponentiation of ordinals a nice geometric model?
It is well known that the sum $\alpha+\beta$ of two ordinals $\alpha,\beta$ can be defined "geometrically" as the order type of the sum $(\{0\}\times \alpha)\cup(\{1\}\times\beta)$ endowed ...
- 41.8k
17
votes
1
answer
1k
views
How is this fixed point theorem related to the axiom of choice?
I'm hoping the answer to this is well-known.
Let $X$ be an ordered set (i.e. poset). An inflationary operator $f$ on $X$ is a function $f: X \to X$, not necessarily order-preserving, such that $f(x) \...
- 27.7k
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
16
votes
4
answers
1k
views
Can Suslin (or Aronszajn) lines ever be orderings of abelian groups?
I am interested in realizing linear orders as orderings of abelian groups. In particular, can Suslin lines (and other classes of line) be realised in this way?
Let $\mathcal{C}$ be a class of (...
- 2,111
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
13
votes
2
answers
2k
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 ...
- 918
13
votes
2
answers
690
views
How many subsets of $\mathbb{R}$ are order isomorphic to $\mathbb{Q}$?
How many subsets of $\mathbb{R}$ are order isomorphic to $\mathbb{Q}$?
How many subsets of the long line $\omega_1\times[0,1)$ are order isomorphic to $\mathbb{Q}$?
I can see that results in both ...
- 233
13
votes
1
answer
283
views
Can any poset of cardinality $\leq 2^{\aleph_0}$ be embedded in ${\cal P}(\omega)/(\text{fin})$?
We endow ${\cal P}(\omega)$ with an equivalence relation by saying that $A\simeq_{\text{fin}} B$ iff the symmetric difference $A\Delta B$ is finite. The resulting set of equivalence classes is denoted ...
- 48.9k
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
12
votes
5
answers
1k
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 ...
- 918
12
votes
2
answers
677
views
What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?
Let $\mathbb{R}^\mathbb{R}$ be the set of functions $\mathbb{R}\to\mathbb{R}$ patially ordered by eventual domination. Obviously, every ordinal below $\omega_1$ can be embedded in $\mathbb{R}^\mathbb{...
- 872
12
votes
1
answer
525
views
Is the Tukey order well-founded
Consider the Tukey order restricted to directed orders of the form $(U,\supseteq)$, where $U$ is an ultrafilter on $\omega$. It is defined as follows:
For two ultrafilters $U,W$ on $\omega$, we say ...
- 123
12
votes
1
answer
443
views
Is each cover of the plane by lines minimizable?
A cover $\mathcal C$ of a set $X$ by subsets of $X$ is called
$\bullet$ minimal if for every $C\in\mathcal C$ the family $\mathcal C\setminus\{C\}$ is not a cover of $X$;
$\bullet$ minimizable if $\...
- 41.8k
11
votes
2
answers
682
views
On Applications of Forcing in Domain Theory
An interesting feature of domain theory is to use partial orders in order to provide a mathematical model for the computational approximation in a potentially infinite computational process (e.g. ...
11
votes
1
answer
670
views
Do all toposes satisfy the internal Zorn's lemma?
I came up with this question when trying to give a more detailed answer to a question by Tim Campion in a comment to Ingo Blechschmidt's answer to Examples of statements that are valid in every ...
- 18.4k
11
votes
1
answer
803
views
Is it known whether every $\omega$-tree with an infinite antichain has an infinite chain in $\mathsf{ZF}$?
In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5:
Each of the following statements imply those beneath it.
The countable union of finite ...
- 503
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
11
votes
0
answers
256
views
Existence of a strong antichain
Call an antichain (set of pairwise incomparable elements) $A$ of a poset $P$ strong if for every $p,q \in P$ with $p \leq q$ there exists an $a\in A$ which is comparable with both $p$ and $q$.
...
- 111
10
votes
4
answers
383
views
Universal poset for cardinals $\kappa \geq \aleph_0$
Given a cardinal $\kappa\geq \aleph_0$, is there a poset $(P,\leq)$ with $|P| = \kappa$ such that every poset of cardinality $\kappa$ can be order-embedded into $(P,\leq)$?
- 48.9k
10
votes
2
answers
469
views
Do operations generate well-ordered sets only?
I've read @TauMu's question about the set of functions $\mathbb N\rightarrow\mathbb N$ generated from the identity map by repeatedly applying exponentiation of two already ...
- 7,500
10
votes
3
answers
265
views
Maximal chains in a quasi-order of linear order types
Let $\mathcal{T}_\kappa$ be the set of all linear order types of cardinality $\kappa$. Let $\prec$ denote a binary relation on $\mathcal{T}_\kappa$ representing embeddability of order types (note that ...
- 1,699
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
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
8
votes
4
answers
630
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, ...
- 1,174
8
votes
2
answers
205
views
Spaces without maximal homogeneous subspaces
A homogeneous space $(X,\tau)$ is a topological space such that for all $x,y\in X$ there is a homeomorphism $\varphi:X\to X$ such that $\varphi(x)=y$. As a previous question implies, the union of an ...
- 48.9k
8
votes
2
answers
483
views
Posets obtained from a semigroup by the definition $x \leq y \iff x \cdot y = x$
A po-groupoid is a groupoid $\langle A,\cdot\rangle $ such that the relation
defined by
$$
x \leq y \text{ if and only if } x \cdot y = x
$$
is a partial order on $A$, the order related to $\langle ...
- 1,124
8
votes
1
answer
415
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 ...
- 3,982
8
votes
1
answer
314
views
A strictly decreasing function between uncountable subsets of the reals
By a standard technique of inductive killing everything relevant (in this case decreasing homeomorphisms between uncountable $G_\delta$-subsets of the real line) it is possible to prove the following ...
- 41.8k
8
votes
0
answers
227
views
Is there a 'local' version of Near Coherence of Filters?
The axiom Near Coherence of Filters (NCF) is known to be independent of ZFC.
Axiom (NCF I): For any two free ultrafilters $\mathcal D$ and $\mathcal E$ on $\mathbb N$, there exist finite-to-one ...
- 1,955
8
votes
0
answers
171
views
Can $Ded(\kappa)$ be a supremum?
Definition If there is a dense linear order w/o endpoints of size $\lambda$ with a dense subset of size $\kappa$ then write $D(\kappa,\lambda)$. $Ded(\kappa)=\sup_\lambda \{D(\kappa,\lambda)\}$.
It ...
- 2,882
7
votes
3
answers
355
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 $\...
- 11.3k
7
votes
2
answers
344
views
Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$
Let $X$ be a set, and let $\text{Part}(X)$ denote the collection of all partitions of $X$. For $A, B\in \text{Part}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ ...
- 48.9k
7
votes
2
answers
496
views
Counterexample for Chvatal's conjecture in an infinite set
Let $X \neq \emptyset$ be a set. We say that ${\cal F} \subseteq {\cal P}(X)$ is a down-set if ${\cal F}$ is closed under taking subsets. Whenever $a \in X$, we let ${\cal F}_a = \{ S \in F : a \in S\}...
- 48.9k
7
votes
1
answer
579
views
Progress on determining which partial orders embed into the rationals
The following result is relatively well-known: (for example in Math StackExchange answer #37161)
For every countable linear order $(R,\prec)$, there is an $X\subseteq\mathbb Q$ such that $(R,\prec)$ ...
- 2,031
7
votes
2
answers
874
views
Which linearly ordered sets have the property that their completion is equipotent with their powerset?
As is well-known, ZFC proves the equipotency of $\mathbb{R}$ and $\mathcal{P}(\mathbb{Q}).$ Is there a nice characterization of those linearly ordered sets $L$ which, like $\mathbb{Q}$, have the ...
- 3,793
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
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