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&=\{...

- 4,580

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/...

- 51.3k

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$...

- 69.9k

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. ...

- 166

14
votes

Accepted

### Constructing an $\omega_1$-sequence of functions that almost extend all previous functions

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 ...

- 206k

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 ...

- 55.4k

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 ...

- 11.3k

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 ...

- 25.3k

13
votes

Accepted

### On Hamkins' answer to a problem by Michael Hardy

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 ...

- 16.3k

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 ...

- 206k

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 ...

- 1,056

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} = \...

- 5,047

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 ...

- 9,221

12
votes

Accepted

### Can there be a tree of height $\omega_2$ having all levels countable, with no cofinal branch?

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 ...

- 30.9k

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^{\...

- 16.3k

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 $\{\...

- 24.4k

12
votes

Accepted

### "Drinking number" of a graph

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

- 136

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: ...

- 6,549

11
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 ...

- 25.4k

11
votes

### Dominating families in bigger cardinals

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 ...

- 206k

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 ...

- 16.3k

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 ...

- 55.4k

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\...

- 2,273

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 #...

- 31.6k

10
votes

Accepted

### How hard is it to destroy a diamond? (with a real)

The answer is yes, assuming the existence of $\aleph_2$-many measurable cardinals. To see this, assume $GCH+\Diamond$ holds and $S$ is a discrete set of measurable cardinals of size $\aleph_2.$
Step ...

- 30.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 ...

- 93.7k

10
votes

Accepted

### chain condition of a product of posets

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 $...

- 31.6k

10
votes

### Dominating families in bigger cardinals

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 ...

- 30.9k

10
votes

Accepted

### Destroying Suslin, nothing special

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 ...

- 7,172

10
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 ...

- 156

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

#### Related Tags

infinite-combinatorics × 430set-theory × 275

co.combinatorics × 99

graph-theory × 95

hypergraph × 71

lo.logic × 63

graph-colorings × 34

forcing × 33

gn.general-topology × 21

gr.group-theory × 17

large-cardinals × 15

order-theory × 15

matching-theory × 15

ultrafilters × 14

ramsey-theory × 14

descriptive-set-theory × 12

cardinal-characteristics × 12

nt.number-theory × 11

posets × 11

covering × 11

reference-request × 9

measure-theory × 8

axiom-of-choice × 7

partitions × 7

sequences-and-series × 6