19 votes
Accepted

"Rocket elements" in bijections $f:\mathbb{N}\to \mathbb{N}$

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&=\{...
Martin Sleziak's user avatar
18 votes
Accepted

Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$

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/...
Todd Trimble's user avatar
  • 52.4k
16 votes
Accepted

Connected graphs isomorphic to their own contraction

No. Let $G$ be the Rado graph (which is infinite, connected, and not complete), and $S$ a finite subset of the vertices of $G$ (because the Rado graph is countable). $G/S$ still has the extension ...
paste bee's user avatar
  • 1,411
15 votes
Accepted

Selective ultrafilter and bijective mapping

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$...
Andreas Blass's user avatar
15 votes
Accepted

Induced subgraphs of any given smaller chromatic number

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. ...
Incompactness's user avatar
14 votes
Accepted

Minimal generating set for $S_\omega$

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 ...
YCor's user avatar
  • 60.1k
14 votes
Accepted

Graph $G$ such that removing an edge leaves $G$ "unchanged"

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 ...
M. Winter's user avatar
  • 12.6k
14 votes
Accepted

Is the set of powerful numbers piecewise syndetic?

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 ...
Wojowu's user avatar
  • 27.4k
14 votes

Size of maximal intersecting families

The answer is yes. Consider first for simplicity the case where $X$ is countably infinite. If $\mathcal{S}$ is a maximal intersecting family, then I claim that $\mathcal{S}$ must contain a set with ...
Joel David Hamkins's user avatar
13 votes
Accepted

Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?

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 ...
Joel David Hamkins's user avatar
13 votes
Accepted

Historical question about the $\aleph_2$-Souslin hypothesis

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 ...
saf's user avatar
  • 1,156
13 votes

Does $\diamondsuit(\kappa)$ provably hold at Woodins or inaccessible Jónssons $\kappa$?

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} = \...
Yair Hayut's user avatar
  • 5,192
13 votes
Accepted

Family of sets with a covering property

Yes. Let $S$ be a set of cardinality $|S|\ge k+2$. Let $X=\binom Sk$, the set of all $k$-element subsets of $S$. For each $s\in S$ let $a_s=\{x\in X:s\notin x\}$, and let $A=\{a_s:s\in S\}$. It is ...
bof's user avatar
  • 11.9k
13 votes

Connected graphs isomorphic to their own contraction

No. Let $V = \mathbb{N}$ and $E = (0, i)$ for $i$ in $\mathbb{N}^*$ (a "star" graph where every vertex is connected to $0$). If you collapse a subset containing $0$, the collapsed vertex can ...
Vincent's user avatar
  • 181
12 votes
Accepted

Non-isomorphic projective planes on $\omega$

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 ...
Gro-Tsen's user avatar
  • 30k
12 votes
Accepted

"Towers" on singular cardinals with countable cofinality

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^{\...
Will Brian's user avatar
  • 17.4k
12 votes
Accepted

Is there a non-atomic finite positive measure in the plane, of which uncountably many projections have atoms?

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 $\{\...
Piotr Hajlasz's user avatar
12 votes
Accepted

"Drinking number" of a graph

Known as unfriendly partition conjecture. Open for countable graphs: http://www.openproblemgarden.org/op/unfriendly_partitions.
user195625's user avatar
12 votes

Diagonalizing against $\omega_1$-sequences of functions mod finite

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: ...
Farmer S's user avatar
  • 8,752
12 votes
Accepted

Size of maximal intersecting families

Let $\mathcal S$ be a maximal intersecting family of subsets of a nonempty set $X$. Note that, for each set $A\subseteq X$, exactly one of the sets $A$ and $X\setminus A$ belongs to $\mathcal S$. It ...
bof's user avatar
  • 11.9k
12 votes

The Stable Set Conjecture

There is a subsequent 1989 paper by Hildebrand, "On integer sets containing strings of consecutive integers" which shows that the if the set satisfies $d(A)>\frac{k-2}{k-1}$ then the ...
JoshuaZ's user avatar
  • 6,100
11 votes
Accepted

"König's theorem" for $T_2$-spaces?

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 ...
Will Brian's user avatar
  • 17.4k
11 votes
Accepted

Cardinality of families of subsets of $\mathbb{N}$ whose intersections are finite

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 ...
YCor's user avatar
  • 60.1k
11 votes
Accepted

Is $S_\omega/F_\omega$ embeddable to $S_\omega$?

No, it is not. McKenzie (1971) observed that the "direct sum" of $\ge\aleph_1$ non-abelian groups cannot be embedded into $S_\omega$ (indeed, it yields an ascending chain of centralizers in $S_\...
YCor's user avatar
  • 60.1k
11 votes
Accepted

Is there a topological group with the small index property that does not have automatic continuity?

Here is a counterexample. Consider $\mathbb{R}$ with addition. We define a topology on this group by giving the cosets of all countable index subgroups as a sub-basis. This subbasis is actually a ...
Luke Elliott's user avatar
11 votes
Accepted

Coloring almost-disjointness

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\...
Alessandro Codenotti's user avatar
11 votes
Accepted

Does "$X \not\to (\omega)^\omega_2$ for every infinite $X$" imply ${\sf AC}$?

The answer is no, the statement that for every set $X$ we have $$X\not\to(\omega)^\omega_2$$ does not imply the axiom of choice. This was shown by Kleinberg and Seiferas in 1973, see MR0340025 (49 #...
Andrés E. Caicedo's user avatar
11 votes
Accepted

Maximal intersecting families on $\omega$ that are not ultrafilters

Let $U,V,W$ be three distinct ultrafilters on $\omega$. Let $M$ be the family of those subsets of $\omega$ that belong to at least two of $U,V,W$. Then $M$ is a maximal intersecting family, it is not ...
Andreas Blass's user avatar
11 votes

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$

The following partial answer (inspired by Pace Nielsen's deleted answer) addresses only the instances where $|R|=\aleph_0$ and $|S|\gt2^{\aleph_0}$. I claim that it's consistent (relative to the ...
bof's user avatar
  • 11.9k
10 votes
Accepted

On a set of sets intersecting in $1$ point

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 ...
Fedor Petrov's user avatar

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