45

The True (?) Story of Hilbert's Infinite Hotel, by Helge Kragh (2014)
What is known as "Hilbert's hotel" is a story of an imaginary hotel
with infinitely many rooms that illustrates the bizarre consequences
of assuming an actual infinity of objects or events. Since the 1970s
it has been used in a variety of arguments, some of them relating to
...

answered Sep 19 '14 at 8:54

Carlo Beenakker

139k1212 gold badges335335 silver badges483483 bronze badges

35

I think it follows from Theorem 1.1 of "Subgroups of Infinite Symmetric Groups" by Macpherson and Neumann (J. London Math. Soc. (1990) s2-42 (1): 64-84) that there is no minimal generating set of $S(\Omega)$for infinite $\Omega$.
The theorem states that any chain of proper subgroups of $S(\Omega)$ whose union is $S(\Omega)$ must have cardinality strictly ...

answered Jul 10 '14 at 16:44

Jeremy Rickard

29.3k22 gold badges9090 silver badges126126 bronze badges

19

Choose any infinite set $A\subseteq\mathbb N$ such that $\mu^+(A)=0$. Enumerate both $A$ and $B=\mathbb N\setminus A$ as
\begin{align*}
A&=\{a_1<a_2< \dots < a_n < \dots\}\\
B&=\{b_1<b_2< \dots < b_n < \dots\}
\end{align*}
Then you can definite the function $f\colon\mathbb N\to\mathbb N$
\begin{align*}
f(b_k)&=b_{k+1}\\
f(...

18

It may be clarifying to work with equivalence relations $E$ on $X$ rather than partitions on $X$. The two are in natural bijection, with $E$ inducing a partitioning quotient map $q: X \to X/E$, and $X/E$ refines $X/E'$ iff $E \subseteq E'$ as subsets of $X \times X$.
Next, there is a surjective order-preserving map $P(X \times X) \to \text{Equiv}(X)$ where ...

answered Sep 27 '18 at 12:16

17

Jeremy Rickard's answer uses the fact that a symmetric group is not the union of a countable chain of proper subgroups. The following easy proof of that fact is quoted from Fred Galvin, Generating countable sets of permutations, J. London Math. Soc. (2) 51 (1995), 230-242.
[. . .] permutations are regarded as right operators, and are composed from left to ...

15

Not necessarily. Komjáth showed that it is consistent that there is a graph of chromatic number $\aleph_2$ which does not have a subgraph (not just induced) of chromatic number $\aleph_1$. See P. Komjáth, Consistency results on infinite graphs, Israel J. Math., 61 (1988), pp. 285-294.

14

Nice question! I like it very much.
Sure, we can do this. We'll also arrange that
$\text{ran}(f_\alpha)$ is coinfinite. That will make the successor
steps easy, since there is always another point available. The
difficulty is what to do at limits. Suppose we have $f_\alpha$ for
$\alpha<\lambda$, where $\lambda$ is a countable limit ordinal. We want to ...

answered Jul 16 '15 at 11:52

Joel David Hamkins

193k3333 gold badges595595 silver badges10431043 bronze badges

14

No.
Indeed, F. Galvin proved in 1995 that every countable subset of $S_\omega$ is contained in a finitely generated subgroup (and also $S_\kappa$ for every infinite $\kappa$). By contradiction suppose $M$ exists. Let $I$ be an infinite countable subset of $M$, so $I\subset \langle F\rangle$ for some finite $F$, and hence there exists a finite subset $J$ of $...

14

An infinite path, the "left half" of its vertices is glued to triangles, the "right half" is glued to paths of length two.
You can remove an edge from one of the triangles without changing the graph.

14

The answer is no. A set $S$ to be piecewise syndetic iff there is an integer $d$ such that there exist intervals $I$ of arbitrary length such that distances between elements of $S\cap I$ are bounded by $d$. In particular, $|S\cap I|\geq\frac{1}{d}|I|$. I will show no such $d$ exists.
For any prime $p$, the fraction of those which are either not divisible by $...

13

UPDATE:
Jörg Brendle, Joel David Hamkins, and I have now written a paper entitled "The subseries number" (link) in which we analyze some new cardinal invariants of the continuum related to this question.
The main topic of the paper (and its title characteristic) is the cardinal originally defined by Joel in his answer here, the subseries number $\...

13

In ZFC, the player aiming for the empty set has a winning strategy in the game played on any infinite set, including the reals. Using the axiom of choice, we can well-order the set and thereby pretend that we are playing sets of ordinals. Now, whenever it is the empty-set player's turn, she should look at the order type of the ordinals remaining, and play so ...

answered Jan 2 '17 at 19:28

Joel David Hamkins

193k3333 gold badges595595 silver badges10431043 bronze badges

13

First, in case your question suggests that you managed to prove the consistency of $GCH+SH(\omega_2)$, then let me congratulate you wholeheartedly!
Second, to put things in context, let us recall that an $\omega_2$-Souslin tree is a non-special $\omega_2$-Aronszajn tree which is (obviously) an $\omega_2$-Aronszajn tree.
Back to your question. By the time ...

13

This is a partial answer. I will show that if $\delta$ is Woodin then $\diamondsuit_\delta$ holds.
Claim: Any Woodin cardinal is subtle.
Proof: Let $\delta$ be a Woodin cardinal. Let $\vec{A} = \langle A_\alpha \mid \alpha < \delta\rangle$ be a sequence a sets, $A_\alpha \subseteq \alpha$ and let $C$ be a club in $\delta$. We want to find $\alpha < \...

12

The following theorem of Kurepa answers the question.
Theorem (Kurepa) Suppose that $\kappa$ is regular, $\lambda< \kappa$, and $T$
is a $\kappa$-tree each of whose levels has cardinality less than $\lambda$. Then $T$ has a
cofinal branch.
The theorem is stated in Kanamori's book ``The higher infinite'', as Proposition 7.9 (page 78).

answered May 30 '15 at 4:08

Mohammad Golshani

29.9k22 gold badges8181 silver badges181181 bronze badges

12

For $\lambda > 2^{\aleph_0}$, there is no such sequence.
Suppose $\lambda > 2^{\aleph_0}$. Because $2^{\aleph_0}$ cannot have countable cofinality, there is some $\kappa < \lambda$ with $2^{\aleph_0} < \kappa$. Consider the sequence $\{A_\alpha \cap A_\kappa \mid \alpha < \kappa\}$. For each particular $\alpha$, the sets $A_\alpha$ and $A_\...

12

Such a measure cannot exist. Suppose to the contrary that we have an uncountable family of lines $\ell$ such that $\mu(\ell)>0$. Then there is $\epsilon>0$ and an infinite family of lines $\{\ell_i\}_i$ with $\mu(\ell_i)\geq\epsilon$. These lines intersect at countably many points. Since the measure has no atoms, this set $E$ has measure zero. Removing ...

answered May 11 '18 at 15:40

Piotr Hajlasz

21.9k55 gold badges6767 silver badges137137 bronze badges

12

No, this fails not only for selective ultrafilters but for all non-principal ultrafilters $\mathcal F$ on $\omega$.
The main ingredient in the proof is the theorem that, if an ultrafilter $\mathcal U$ on a set $X$ is sent to itself by some map $g:X\to X$ (meaning that $\mathcal U=g(\mathcal U):=\{A\subseteq X:g^{-1}(A)\in\mathcal U\}$), then the set of ...

answered Feb 27 '19 at 15:21

Andreas Blass

67.7k88 gold badges167167 silver badges265265 bronze badges

12

This isn't an answer, as you're working in ZFC. But it seems worth noting.
Assume ZFC + AD$^{L(\mathbb{R})}$. Then
$L(\mathbb{R})$ satisfies ZF + AD + DC + "the statement is false".
Proof: Work in $L(\mathbb{R})$. Then every real has a sharp, and every subset of $\omega_1$ is
constructible from a real. Suppose $\vec{f}=\left<f_\alpha\right>_{...

11

Here is some general background information. The relevant search phrases for this topic are generalized cardinal invariants or generalized cardinal characteristics, and the topic has a growing literature, emerging over many years. The topic has been studied as folklore for some time.
Here are a few specific resources:
Dilip Raghavan, Saharon Shelah, Two ...

answered Feb 11 '18 at 20:57

Joel David Hamkins

193k3333 gold badges595595 silver badges10431043 bronze badges

11

What you are calling the "matching number" of $X$ is usually called its Souslin number -- the smallest cardinal bounding the size of any collection of pairwise disjoint open subsets of $X$.
What you are calling the "vertex covering number" of $X$ is usually called its density.
Thus your question is how the Souslin number and the density of a Hausdorff ...

11

I guess this is a variant of Noah's construction:
Let $S$ be an infinite subset of $\mathbf{N}=\{0,1,2,\dots\}$. Define a leafless rooted tree $V_S$, starting from a root at level 0, such that given a vertex $v$ of level $n\ge 0$, $v$ has exactly 1 successor if $n\notin S$ and exactly 2 successors if $n\in S$.
Let $\mathcal{W}\subset\mathcal{P}(V_S)$ be ...

11

Known as unfriendly partition conjecture. Open for countable graphs: http://www.openproblemgarden.org/op/unfriendly_partitions.

11

No, $\chi(G)=\mathfrak c$, in fact $G$ contains a complete subgraph on $\mathfrak c$ vertices.
A simple way to construct one is by fixing a bijection $f\colon\Bbb Q\to\omega$ and fixing, for every $r\in\Bbb R\setminus\Bbb Q$, a sequence $(q^r_i)_{i\in\omega}$ of rationals numbers converging to $r$. Taking the images through $f$ of those sequences gives an ...

answered May 7 '21 at 17:55

Alessandro Codenotti

1,91211 gold badge1313 silver badges1919 bronze badges

10

Consider any coloring $\varphi:V\to\omega$. Construct a strictly decreasing sequence $\langle X_n:n\lt\omega\rangle$ in $\mathcal P(\mathbb N)$ and a strictly increasing sequence $\langle f_n:n\lt\omega\rangle$ in $V$ so that for each $n\in\omega$ we have:
$\text{range}(f_n)\subset X_n$,
$|X_n\setminus\text{range}(f_n)|=\aleph_0$,
either $\varphi(f_n)=...

10

Consider two sets $e,f\in E$, assume that $\max(|f|,|e|)=:\mu<\kappa$, $\{x\}:=e\cap f$. Take arbitrary element $y\in f\setminus x$, it is contained in at most $\mu$ sets from $E$. Indeed, they all have a common element with $e$, and all those common elements are different. So, the elements of $f\setminus x$ are contained totally in at most $\mu\times \mu&...

answered Nov 20 '16 at 16:09

Fedor Petrov

84.6k88 gold badges195195 silver badges354354 bronze badges

10

You ask for the number of isomorphism classes of projective planes on $\omega$. I claim that it is exactly $2^{\aleph_0}$.
It is at most $2^{\aleph_0}$.
Indeed, a projective plane on $\omega$ can be encoded by the set of $\{x,y,z\}\subset\omega$ of cardinal $3$ which are aligned (i.e., such that $z$ lies on the unique line containing $x,y$), and the set ...

10

First of all, note (as Monroe does in his question) that if $\mathbb P,\mathbb Q$ are ccc, then $\mathbb P\times\mathbb Q$ is $\mathfrak c^+$-cc, as an immediate consequence of the Erdős-Rado theorem $(2^{\aleph_0})^+\to(\aleph_1)^2_2$. (This is to say, if $\mathbb P$ and $\mathbb Q$ do not admit uncountable antichains, then any antichain in their product ...

answered Aug 27 '17 at 4:33

Andrés E. Caicedo

30.5k55 gold badges112112 silver badges201201 bronze badges

10

Professor Hamkins already gave many interesting references. Let me add a few more.
Possibly, the work of Cummings-shelah Cardinal invariants above the continuum is the starting point for the study of generalizations of cardinal invariants to the context of uncountable cardinals. In this paper, they prove the following: If $λ↦(β(λ),δ(λ),μ(λ))$ is a class ...

answered Feb 12 '18 at 4:37

Mohammad Golshani

29.9k22 gold badges8181 silver badges181181 bronze badges

10

Chapter IX of Proper and Improper Forcing addresses this issue.
Shelah proves that Souslin's Hypothesis does not imply every Aronszajn tree is special, and he does this by investigating weak notions of specialness that are still incompatible with Souslinity. He shows that there are forcings that "specialize" Aronszajn trees in the weak sense, and that ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

infinite-combinatorics × 359set-theory × 235

co.combinatorics × 86

graph-theory × 83

hypergraph × 56

lo.logic × 54

forcing × 32

graph-colorings × 29

gn.general-topology × 19

gr.group-theory × 15

large-cardinals × 12

ultrafilters × 12

matching-theory × 12

order-theory × 11

cardinal-characteristics × 11

descriptive-set-theory × 10

posets × 9

ramsey-theory × 9

covering × 9

nt.number-theory × 8

reference-request × 8

measure-theory × 6

real-analysis × 5

sequences-and-series × 5

axiom-of-choice × 5