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.

Filter by
Sorted by
Tagged with
1 vote
3 answers
90 views

Find an equivalence relation over all of $\mathbb{Z}$ which has infinitely many equivalence classes with infinitely many elements in each

I want to find an equivalence relation defined on all integers (that is, all of $\mathbb{Z}$) where The equivalence relation partitions $\mathbb{Z}$ into infinitely many equivalence classes; and ...
Christopher Miller's user avatar
0 votes
0 answers
19 views

Solving systems of simultaneous equations with permutations as variables: algebra meets combinatorics and order statistics

We may treat a given permutation as a vector variable, so that permutation s$_n$ is a variable that takes values among all possible number sequences of length $n$, which have elements in the rank ...
virtuolie's user avatar
  • 171
2 votes
2 answers
218 views

Antichains of maximal size in the set of all finite subsets of a singular cardinal

Let $P = (P, \le)$ be a partially ordered set. A subset $T$ of $P$ is called: cofinal (in $P$), if for all $x \in P$ there is a $t \in T$ such that $x \le t$, antichain, if for all $x, y \in T$, $x \...
Ulli's user avatar
  • 3,912
1 vote
0 answers
37 views

Martin's axiom and uncountable independent family

I'm stuck on the following exercise and would appreciate hints on how to proceed. I haven't worked much with MA before. Assume MA. Given a countable independent family $\mathcal{A} \subseteq [\omega]^...
lowcard's user avatar
  • 57
5 votes
1 answer
117 views

Forcing to add a $\square_\lambda$-sequence is $\mathrm{<}\lambda^+$-strategically closed

For an uncountable cardinal $\lambda,$ a $\square_\lambda$-sequence is a sequence $(C_\alpha: \alpha\in \lim(\lambda^+))$ such that Each $C_\alpha$ is a club in $\alpha$ with order type $\le \lambda.$...
spaceisdarkgreen's user avatar
0 votes
1 answer
116 views

Argument that there are no Suslin trees

I'm trying to prove exercise 36 From Kunen "Set Theory", Chapter II: If $T$ and $T'$ are $\kappa$-trees, define the product $T\times T'$ to be the $\kappa$-tree whose $\alpha$-th level is $\...
Neo pythagorean's user avatar
2 votes
0 answers
80 views

Understanding the tree in the proof of Erdős-Rado theorem

Define $\beth_n(\kappa)$ inductively by $\beth_0(\kappa)=\kappa$ and $\beth_{n+1}(\kappa)=2^{\beth_n(\kappa)}$. Erdős-Rado theorem says $\beth_n(\kappa)^+\rightarrow(\kappa^+)^{n+1}_\kappa$ holds, i.e....
n901's user avatar
  • 460
1 vote
1 answer
33 views

Given the sums by line and by column, find the corresponding matrix (in a general (complete ?) monoid or semiring)

I'm interested in the following question: In a monoid $\mathbf{M}$, given sums $\sum_{i \in I} a_i = \sum_{j \in J} b_j$, is it possible to find elements $c_{i,j}$ such that for all $i$, $a_i = \...
sparusaurata's user avatar
2 votes
1 answer
43 views

Number of infinite trees on certain cardinal

Let $\kappa$ be some infinite cardinal. I usually use the notation $\langle T,<_T\rangle$ to refer to a tree. My question is: what is the number of non-isomorphic trees with $|T|=\kappa$? There is ...
Yester's user avatar
  • 414
3 votes
1 answer
62 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$ ...
sanguine's user avatar
  • 249
2 votes
1 answer
60 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 ...
Roy Sht's user avatar
  • 1,339
0 votes
0 answers
119 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 ...
lowcard's user avatar
  • 57
7 votes
1 answer
396 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 ...
Edward H's user avatar
  • 132
1 vote
1 answer
74 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 = \...
Moni145's user avatar
  • 2,142
2 votes
0 answers
50 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'...
Matteo Casarosa's user avatar
2 votes
0 answers
49 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 ...
littleman's user avatar
  • 434
3 votes
0 answers
58 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, ...
Jim's user avatar
  • 518
2 votes
1 answer
90 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 ...
Clement Yung's user avatar
  • 8,347
1 vote
0 answers
29 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 ...
Stefania Dokker's user avatar
8 votes
1 answer
191 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 ...
MIO's user avatar
  • 1,916
3 votes
1 answer
165 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 ...
Peluso's user avatar
  • 509
0 votes
1 answer
107 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)...
ViHdzP's user avatar
  • 4,582
2 votes
1 answer
64 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 ...
Matteo Casarosa's user avatar
1 vote
0 answers
93 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}\...
Matt D's user avatar
  • 405
3 votes
1 answer
130 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$
user122424's user avatar
  • 3,926
2 votes
2 answers
167 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 ...
BENG's user avatar
  • 1,105
7 votes
1 answer
146 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 ...
Elswyyr's user avatar
  • 423
4 votes
1 answer
124 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 ...
Green Park's user avatar
2 votes
1 answer
147 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 $...
Clement Yung's user avatar
  • 8,347
0 votes
0 answers
220 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–...
Ari's user avatar
  • 865
1 vote
1 answer
72 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 ...
Ari's user avatar
  • 865
2 votes
1 answer
112 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_\...
GOTO Tatsuya's user avatar
7 votes
1 answer
160 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 ...
GOTO Tatsuya's user avatar
1 vote
2 answers
72 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 ...
Jason Zesheng Chen's user avatar
0 votes
1 answer
137 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 ...
ikrto's user avatar
  • 873
2 votes
1 answer
106 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 \...
Jordan Mitchell Barrett's user avatar
3 votes
1 answer
229 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_\...
Robin's user avatar
  • 128
5 votes
1 answer
239 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|...
Hanul Jeon's user avatar
  • 27.4k
1 vote
2 answers
154 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 ...
Boccherini's user avatar
1 vote
1 answer
60 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)...
YCB's user avatar
  • 2,691
1 vote
0 answers
45 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-...
YCB's user avatar
  • 2,691
1 vote
1 answer
166 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 ...
Grinsekotze's user avatar
7 votes
2 answers
419 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 ...
Jason Zesheng Chen's user avatar
2 votes
1 answer
237 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 ...
Dominic van der Zypen's user avatar
2 votes
1 answer
267 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 ...
mtg's user avatar
  • 157
2 votes
1 answer
91 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$-...
Shervin Sorouri's user avatar
5 votes
1 answer
119 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+\...
Kevin Shannon's user avatar
3 votes
0 answers
44 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 ...
frafour's user avatar
  • 3,015
2 votes
1 answer
338 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$ ...
Jim's user avatar
  • 518
2 votes
1 answer
142 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'...
Kiyoon Eum's user avatar

1
2 3 4 5 6