Questions tagged [infinitary-combinatorics]
For topics of a combinatorial character in set theory. Topics belonging to "combinatorial set theory" may be tagged this way. These include: Partition calculus, diamond principles, square principles, combinatorial properties of infinite graphs or partial orders, etc.
264
questions
3
votes
1
answer
40
views
Cardinality of tree of height $\kappa$, $\kappa$ measurable
The following is Theorem $2.8$ in Chapter 13 of Hrbacek and Jech's "Introduction to Set Theory" ($3^{\text{rd}}$ edition):
Theorem $\bf{2.8}$ Let $\kappa$ be a measurable cardinal. If $T$ ...
- 117
2
votes
1
answer
37
views
Reference request: infinitary Ramsey theory
I was reading about the (various) infinite versions of Ramsey's theorem, and stumbled across a text containing a proof of the Bolzano-Weierstrass Theorem using it:
Unfortunately, I forgot where I ...
- 1,311
0
votes
0
answers
16
views
Maximal almost disjoint family not countable
I recently stumbled upon the concept of almost disjoint families and I read that maximal almost disjointness requires at least an uncountable cardinality of the family. I believe it is not so clear to ...
- 25
7
votes
1
answer
304
views
Continuous chain of $\kappa^+$ isomorphic linear orders on $\kappa\ge\aleph_1$
For $\kappa\ge\aleph_0$ an infinite cardinal, and for $\kappa<\alpha\le\kappa^+$ an ordinal, we ask the existence of a chain $\left\langle(I_i,{<}):i<\alpha\right\rangle$ of linear orders ...
- 174
1
vote
1
answer
56
views
Confusion in Jech's proof that "If there is a Suslin tree, then there is a normal Suslin tree"
I'm a bit confused on Jech's proof of Lemma 9.13. I will not give the definitions of "normal Suslin tree" or "Suslin tree" here.
He claims that if $T$ is a Suslin tree, and $T_1 = \...
- 1,992
2
votes
0
answers
47
views
Reference for Jech's notion of stationary set
I am writing a brief introduction to the Proper Forcing Axiom and I need a reference for Jech's notion of stationary set in $[\lambda]^\omega$ : https://en.wikipedia.org/wiki/Stationary_set#Jech'...
- 506
2
votes
0
answers
36
views
Modern/introductory books on partition relations/partition calculus?
Are there any modern books on partition relations for cardinals/the partition calculus? I've seen several sources say it's a very active field of infinitary combinatorics, but the only book on it I ...
- 121
3
votes
0
answers
46
views
Erdős–Rado theorem generalisation for infinitely many colours
I'll ask my question and then explain the background. Thanks in advance.
Question: Is it the case that
$$
\beth_{\omega}\rightarrow (\beth_{\omega})_{{\aleph_{0}}}^{n}
$$
for finite $n$? If not, ...
- 180
2
votes
1
answer
62
views
Homogeneous Suslin tree in $L$ (Exercise 15.27 of Jech's Set Theory)
Exercise 15.27 of Jech's Set Theory says:
If $V = L$ then there exists a homogeneous Suslin tree.
Recall that a Suslin tree $T$ is a tree of height $\omega_1$ such that every chain and antichain is ...
- 7,881
1
vote
0
answers
25
views
A CSP on bit vector operations
I've got a CSP which is based on constraining bit vector variables. It is explained below through an example, followed by the full definition. So, what I'm concerned about is if you have some idea if ...
7
votes
1
answer
123
views
Finding where in Ramsey's theorem one uses the Axiom of choice
Ramsey's Theorem for infinite graphs requires some choice but when looking at the proof it is not evident how choice is exactly used.
Sketch of the proof:
Given $c:[\omega]^2\rightarrow 2$ a ...
- 1,802
3
votes
1
answer
129
views
Help with an exercise from Kunen's book
I've been having a hard time deciphering Kunen's suggestion in the following exercise:
Overall, I'd like to get a little more direction in solving this exercise. Specifically, I would like some help ...
- 449
0
votes
1
answer
73
views
Cofinality of functions $\mathbb N\to\mathbb N$ under eventual domination
As the question suggests, I'm interested in the cofinality of functions $\mathbb N\to\mathbb N$ under eventual domination, i.e.
$$f\prec g \quad\Longleftrightarrow\quad\exists N,\ \forall n>N,\ f(n)...
- 4,145
2
votes
1
answer
58
views
Tree without cofinal branches and with levels of bounded size
My question is: let's say that a tree T has no cofinal branch and has all levels of size $< \mu$. Can we prove (in ZFC) that the set of branches of T has cardinality $\leq \mu$? I have a very ...
- 506
1
vote
0
answers
67
views
Trying to understand the proof that the bounding number $\mathfrak{b}$ is uncountable
Background
For two functions, $f,g \in {}^\omega\omega$ we say that $g$ dominates $f$, denoted $f<^*g$, if for all but finitely many integers $k\in\omega$, $f(k)<g(k)$.
A family $\mathscr{B}\...
- 395
3
votes
1
answer
117
views
tree property and arrow notation
How can I see that for an uncountable cardinal $\kappa$ these 2 conditions are equivalent :
$\kappa$ has the tree property
$\kappa \to (\kappa)^2$
- 3,911
2
votes
2
answers
100
views
Strong Finite Intersection Property and Pseudo-intersection (Kunen III.1.23)
I have a question on the proof of a lemma in Kunen's Set Theory regarding pseudo-intersections and the cardinal $\mathfrak{p}$ (least size of a family $\mathcal{F} \subseteq [\omega]^{\omega}$ which ...
- 1,043
7
votes
1
answer
128
views
The Diamond Principle and Whitehead's problem
I am currently writing my master's thesis about Whitehead's problem in homological algebra. My main source is Eklof's article https://www.jstor.org/stable/2318684. Eklof does not name the Diamond ...
- 423
4
votes
1
answer
85
views
Proving that the partial order for adding a dominant real is weakly homogeneous
I am trying to prove that the partial order that adds a dominant real is weakly homogeneous. This is listed as exercise IV.4.17 of Kunen's Set Theory (the "new" one).
The details are as ...
- 103
2
votes
1
answer
131
views
Show that $C = C_A = \{\sigma < \omega_1 : M_{A,\sigma} \cap \omega_1 = \sigma\}$ is a club
$\newcommand{\c}[1]{\left\langle #1 \right\rangle}$
$\newcommand{\A}{\mathcal{A}}$
$\newcommand{\Po}{\mathcal{P}}$
I refer to Kunen's Set Theory, 2011 Edition, Theorem III.7.14.
Assume $V = L$. Then $...
- 7,881
0
votes
0
answers
212
views
What's wrong with this proof that $\mathbb{R}$ cannot be well-ordered?
I'm trying to figure out where I'm going wrong with the following proof that $\mathbb{R}$ cannot be well ordered (and thus, ZFC is inconsistent). It's based off a special case of the Erdős–Dushnik–...
- 679
1
vote
1
answer
62
views
Uncountable Intersection of uncountably many uncountable subsets of $\mathbb{R}$
I'm trying to prove or find a counterexample to the following: If $A$ is an uncountable collection of uncountable subsets $S$ of $\mathbb{R}$ such that each $x\in\mathbb{R}$ is in uncountably many of ...
- 679
2
votes
1
answer
102
views
Products of sequentially compact spaces versus $\mathfrak{t}$ and $\mathfrak{s}$
Let $\mu$ be the minimal cardinal $\kappa$ such that there exists a sequence $(X_\alpha : \alpha < \kappa)$ with each $X_\alpha$ sequentially compact space such that $\prod_{\alpha < \kappa} X_\...
- 581
7
votes
1
answer
153
views
For some sequentially compact space $X$, is $X^{\omega_1}$ not sequentially compact?
When we assume the continuum hypothesis, for $X=\{0, 1\}$, the $\omega_1$ product $X^{\omega_1} = X^{\mathfrak{c}}$ is not sequentially compact while $X$ is sequentially compact.
So the proposition in ...
- 581
1
vote
2
answers
67
views
Can there be a fragile family on $\mathcal{P}(\omega)$?
By a fragile family on $\mathcal{P}(\omega)$ (this is a made-up term), I mean a countable family $F\subseteq\mathcal{P}(\omega)$ of pairwise distinct infinite sets such that for any $n\in\omega$, the ...
- 1,466
0
votes
1
answer
88
views
Cardinality of almost disjoint families of sets of reals
Let $\Delta$ be a set of infinite subsets of reals, suppose for any elements $X\neq Y$ of $\Delta$, $X\cap Y$ is finite. Does that imply anything about the cardinality of $\Delta$? Notice that if we ...
- 723
2
votes
1
answer
64
views
Translation invariant ultrafilters?
Is there an ultrafilter $\mathcal{U}$ on $\mathbb{N}$ such that $\mathcal{U}-n = \mathcal{U}$ for all $n \in \mathbb{N}$? Here, $$\mathcal{U}-n = \{ A - n: A \in \mathcal{U} \}$$ and $$A - n = \{ m \...
- 1,816
3
votes
1
answer
215
views
Equivalence of $\square_\kappa\Leftrightarrow\square'_\kappa$
In Devlin - Constructibility on page 158f. he defines $\square_\kappa$ and $\square_\kappa'$ and then proceeds to show that these two are equivalent.
$\square_\kappa$ holds if there is a sequence $(C_\...
- 128
5
votes
1
answer
217
views
The failure of product lemma for Sacks forcing
I am reading Jörg Brendle's Bogota note, and the author claimed that Sacks forcing with countable support product does not satisfy a product lemma. Especially, he mentioned that if $\mathbb{S}_I$, $|I|...
- 26.3k
1
vote
2
answers
134
views
A probability question on infinite sets
Suppose all members of a countably infinite set of people each pick an integer "at random" (I want to avoid uniform distributions for the obvious reasons). (I hope this setting makes enough ...
- 781
1
vote
1
answer
54
views
Definition of a rank function related with a dense subset.
Consider $D$ be a filter over $\omega$ and $\mathbb{L}(D)$ be the Laver forcing (i,e, the elements of $\mathbb{L}(D)$ are trees $T\subseteq\omega^{<\omega}$ with stem $s_T$ and $\forall s\in LV_n(T)...
- 2,592
1
vote
0
answers
37
views
Club set in a finite support iteratiot of c.c.c forcing notions.
I'm reading the Baumgartner and Dordal paper "Adjoining dominating functions" and I have a problem with the Theorem 4.1 proof.
My problem is the following: Suppose that $P$ is a c.c.c-...
- 2,592
1
vote
1
answer
138
views
Why is MA not provable from ZFC?
All texts I have seen about Martin's Axiom briefly mention that it is independent of ZFC, that it is implied by CH and that it is relatively consistent with ZFC+(not CH). I have seen proofs of the ...
- 126
7
votes
2
answers
352
views
Is Fodor's Lemma necessary for the $\omega_1$ train station puzzle?
A common homework problem with Fodor's lemma is to imagine a train network with stations $\langle S_\alpha\mid \alpha<\omega_1+1\rangle$. The train starts at $S_0$ and stops at each station. At ...
- 1,466
2
votes
1
answer
194
views
Zorn's Lemma and injective choice functions
Let $X\neq\emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ be a collection of non-empty subset. We say that a map $f: {\cal E}\to X$ is an injective choice function if ...
- 2,676
2
votes
1
answer
226
views
A lemma in the proof of $\kappa$-chain condition preservation with iterated forcing
I do have a question about a fragment of a proof of a theorem in iterated forcing.
It is the one that Jech invokes in the following form as theorem 16.30 in the 'Seth Theory' book and as Part II, Thm ...
- 135
2
votes
1
answer
80
views
If $\kappa$ is ineffable, then there is no $\kappa$-Kurepa tree
So this is an exercise($4.25$) from Ralf Schindler's book, and I have some trouble with it.
This is the statement:
(Jensen-Kunen) Show that if $\kappa$ is ineffable, then there is no $\kappa$-...
- 2,324
5
votes
1
answer
108
views
Unexpected result, does $\Big\lfloor\frac{n-1}{2}\Big\rfloor=\sum_{i=1}^\infty\bigg\lfloor\frac{n+2^i-1}{2^{i+1}}\bigg\rfloor $
While trying to prove something else, I arrived at the result that for $n\in\Bbb{Z}^+$
$$\Big\lfloor\frac{n-1}{2}\Big\rfloor=\Big\lfloor\frac{n+1}{4}\Big\rfloor+\Big\lfloor\frac{n+3}{8}\Big\rfloor+\...
3
votes
0
answers
41
views
Colorability of graphs with finite clique number
Let $G$ be an infinite graph such that the clique number $\omega(G)$ is finite. By the De Brujin - Erdos theorem, the chromatic number $\chi(G)$ is finite if and only there is a bound on the chromatic ...
- 2,865
2
votes
1
answer
241
views
Generalisation of infinite Ramsey's theorem to countably infinite or variable edge arities
The usual statement of the infinite Ramsey's Theorem, as appears e.g. in
Wikipedia page on Ramsey's Theorem
is (paraphrasing slightly):
If $X$ is an infinite set, and $C$ is a finite set, and $n$ ...
- 180
1
vote
1
answer
83
views
Simple property of arrow notation
Assume that $\kappa \to (\lambda)^r_s$ holds.
Prove that if $r'\le r$, $\kappa \to (\lambda)^{r'}_s$
I proved similar cases like when $s'\le s$ etc. but I have no idea about this case.
Actually I can'...
- 196
0
votes
0
answers
65
views
Ramsey cardinals lemma
I am reading the chapter on large cardinals in Jech's book and I found the following lemma:
If $\kappa \rightarrow (\kappa)^{<\omega} $ and if $\lambda < \kappa $ is a cardinal, then $ \kappa \...
- 197
1
vote
1
answer
237
views
Show that for every uncountable $A \subseteq \omega_1$, the set $\{\alpha \in Lim(\omega_1): A_\alpha \subseteq A\}$ is stationary in $\omega_1$
Let Lim$(\omega_1)$ denote the set of limit ordinals in $\omega_1$. Suppose $A_\alpha$ is a sequence where $\alpha \in$ Lim$(\omega_1)$ that satisfies the following.
i) For every $\alpha \in$ Lim$(\...
- 367
4
votes
0
answers
143
views
Minkowski difference in a pseudo-AP
This question arises from a previous answer of mine, in which I claimed a fact I am not so sure about.
Let $\alpha\in(1,2)$ be an irrational number (feel free to assume $\alpha=\sqrt{2}$ or $\alpha=\...
- 347k
6
votes
1
answer
106
views
On the distributive number $\mathfrak h$
The distributive number $\mathfrak h$ is defined as the least cardinal $\kappa$ such that there exists a family of $\kappa$ open dense subsets in the preordered set $([\omega]^\omega,\subset^*)$ whose ...
- 297
1
vote
2
answers
145
views
How is $\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}x^{i+j} = \sum_{n=0}^{\infty}\sum_{i=0}^{n}x^n$
My professor used this in class for a proof and I'm having trouble understanding it.
$\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}x^{i+j} = \sum_{n=0}^{\infty}\sum_{i=0}^{n}x^n$
The way he explained it, ...
- 415
-1
votes
1
answer
28
views
Partitioning an infinite set into fixed number of sets
Suppose we have a set of size $\kappa$, and want to partition it into $\mu$ sets, where $\kappa$ is an infinite cardinal, and $1<\mu\leq\kappa$. I am aware that it can be done in $2^\kappa$ ways (...
- 3
3
votes
2
answers
422
views
the generalized Delta System Lemma
I'm trying to understand the proof of the generalized Delta System Lemma in Kunen's Set Theory, the 2013 edition.
This stationary set $T$ we've constructed using Fodor's Lemma (Pressing Down Lemma) ...
- 927
1
vote
1
answer
51
views
A Bijection Between $\kappa\times\aleph_{\alpha+\kappa}$ and $\aleph_{\alpha+\kappa}$ with Certain Order-Preservation Properties
In Claim 5.5 of the book $ Almost$ $Free$ $Modules$, second edition, by P. Eklof and A. Mekler (page 254), the authors consider regular cardinals $\kappa$ and $\aleph_\alpha$, where $\kappa<\...
- 349
2
votes
0
answers
56
views
An infinite basis for an ad hoc vector space
To prove a combinatorial identity I'm building an ad hoc vector space that I will define below.
First, I define the set of Pseudo Power Series.
A Pseudo Power Series (pps) $\alpha$ is an ...