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
2 votes
1 answer
44 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 ...
user avatar
  • 7,538
1 vote
0 answers
18 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 ...
user avatar
7 votes
1 answer
96 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 ...
user avatar
3 votes
1 answer
99 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 ...
user avatar
  • 413
0 votes
1 answer
59 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)...
user avatar
  • 3,999
2 votes
1 answer
48 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 ...
user avatar
1 vote
0 answers
52 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}\...
user avatar
  • 373
0 votes
0 answers
58 views

showing diamond principal => another version of diamond principal

Im trying to solve an exercise on Jech set theory book: showing that existence of diamond (existence of a sequence $\langle S_\alpha:\alpha<\omega_1\rangle$ such that $\forall\alpha(S_\alpha\subset\...
user avatar
3 votes
1 answer
99 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$
user avatar
  • 3,578
2 votes
2 answers
62 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 ...
user avatar
  • 1,009
7 votes
1 answer
117 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 ...
user avatar
  • 423
4 votes
1 answer
79 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 ...
user avatar
2 votes
1 answer
113 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 $...
user avatar
  • 7,538
0 votes
0 answers
207 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–...
user avatar
  • 639
1 vote
1 answer
52 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 ...
user avatar
  • 639
2 votes
0 answers
70 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_\...
user avatar
7 votes
1 answer
144 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 ...
user avatar
1 vote
2 answers
63 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 ...
user avatar
0 votes
1 answer
68 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 ...
user avatar
  • 723
2 votes
1 answer
59 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 \...
user avatar
3 votes
1 answer
208 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_\...
user avatar
  • 128
5 votes
1 answer
187 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|...
user avatar
  • 25.4k
1 vote
2 answers
110 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 ...
user avatar
1 vote
1 answer
53 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)...
user avatar
  • 2,542
1 vote
0 answers
35 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-...
user avatar
  • 2,542
1 vote
1 answer
127 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 ...
user avatar
7 votes
2 answers
292 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 ...
user avatar
2 votes
1 answer
167 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 ...
user avatar
2 votes
1 answer
197 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 ...
user avatar
  • 136
2 votes
1 answer
76 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$-...
user avatar
5 votes
1 answer
103 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+\...
user avatar
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 ...
user avatar
  • 2,785
2 votes
1 answer
168 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$ ...
user avatar
  • 55
1 vote
1 answer
59 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'...
user avatar
  • 131
0 votes
0 answers
64 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 \...
user avatar
  • 195
1 vote
1 answer
182 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$(\...
user avatar
  • 367
4 votes
0 answers
133 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=\...
user avatar
6 votes
1 answer
103 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 ...
user avatar
  • 297
1 vote
2 answers
102 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, ...
user avatar
-1 votes
1 answer
26 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 (...
user avatar
  • 3
3 votes
2 answers
357 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) ...
user avatar
1 vote
1 answer
48 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<\...
user avatar
  • 329
2 votes
0 answers
55 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 ...
user avatar
4 votes
0 answers
67 views

Universal Classes of Regular Graphs

There is a small but well-known open problem in graph coloring called the Total Coloring Conjecture. I worked on this problem several years ago and am interested in returning to it, potentially. For ...
user avatar
5 votes
0 answers
52 views

Prove using Koenig's lemma that a rayless connected graph $G$ with $\delta(G) = k$ has a finite subgraph $H$ with $\delta(H)=k$

As the question says: I want to prove using Koenig's lemma that a rayless connected Graph $G$ with minimum degree $\delta(G) = k$ has a finite subgraph $H$ with $\delta(H) = k$. So obviously this is ...
user avatar
  • 1,427
1 vote
1 answer
46 views

Reduction of families to size $\aleph_1$

Suppose that $X$ is a set and $\mathcal A$ is a collection of subsets of $X$ such that $X = \bigcup \mathcal{A}$ and for every countable $\mathcal{A}_0\subset \mathcal{A}$ we have $X\neq \bigcup \...
user avatar
2 votes
1 answer
248 views

Infinite rooms and doors (2)

Suppose we have a house (with finitely many rooms) in which every room has an even number of doors. Prove that the number of doors from the house to the outside world is also even. All I could figure ...
user avatar
1 vote
0 answers
39 views

Finding necessary/sufficient conditions for when a directed graph's geodesic function is unbounded.

Given any directed graph $G=(V,R)$ where $R\subseteq V\times V$ is an arbitrary binary relation, we have under the standard definition of distance in an unweighted digraph that $d_G:V\times V\to \...
user avatar
  • 10.4k
2 votes
0 answers
65 views

Verifying a proof (under AC) that any (possibly non-finite) graph $G$ has a $\kappa$-coloring ($\kappa$ a cardinal) if $\chi(G)\leq \kappa\leq |V(G)|$

Assuming the axiom of choice it seems pretty intuitive that every simple graph $G$ has a $\kappa$-coloring if $\chi(G)\leq \kappa\leq |V(G)|$, simply color $G$ with $\chi(G)$ colors and swap out $\...
user avatar
  • 10.4k
1 vote
1 answer
204 views

Existence of Aronszajn tree

There are theories that prove the existence and non-existence of Souslin trees [exist if $V=L$, don't exist if $\mathsf{MA}(\aleph_1)$] and Kurepa trees [exist if $V=L$, don't exist by Lévy collapsing ...
user avatar
  • 863

1
2 3 4 5 6