Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
2answers
45 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, ...
0
votes
0answers
41 views

Preserving Fat Diamond principle

I recall the definition of a fat diamond principle at $\kappa$. Definition: $S\subseteq\kappa$ is called fat stationary if $S$ is stationary and for every club $C\subseteq\kappa$ and every $\alpha&...
-1
votes
1answer
20 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 (...
0
votes
1answer
115 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) ...
1
vote
1answer
39 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<\...
2
votes
0answers
40 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 ...
3
votes
0answers
43 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 ...
5
votes
0answers
33 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 ...
1
vote
1answer
42 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 \...
2
votes
1answer
136 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 ...
1
vote
0answers
28 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 \...
2
votes
0answers
58 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 $\...
1
vote
1answer
101 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 ...
1
vote
1answer
60 views

How to understand $e$ and other terms in this probability distribution?

Algebraically, the derivation of the probability function of a Poisson random variable is fairly straightforward. Letting $\mu = np$ with $n \to \infty, p \to 0$ so that $\mu < \infty$: Starting ...
6
votes
1answer
137 views

A regularity-like property of normal ultrafilters

Suppose $\kappa$ is a measurable cardinal, with normal measure $U$. Is there a sequence $\{ X_\alpha : \alpha < \kappa^+ \} \subseteq U$ such that for every $Y \in [\kappa^+ ]^\kappa$, $\bigcap_{\...
1
vote
1answer
49 views

Special tree properties

Let $κ$ be an uncountable regular cardinal and $T$ be a tree of height $\kappa$. (1) A function $r : T → T$ is called regressive if $r(t) <_T t$ holds for every $t \in T$ \ {root($T$)}. (2) The ...
1
vote
0answers
83 views

Can the Infinite Ramsey Theorem be extended even when coloring a graph's edges with an infinite number of colors?

In the language of partition calculus, I want to know if the following is true: Let $n$ be an integer, $n \geq 2$. Then $\aleph_n \rightarrow (\aleph_0)^2_{\aleph_0}$. I'm new to infinitary ...
6
votes
1answer
216 views

Unboundedness property is ccc indestructible?

I saw the following claim and I've not been able to prove it. Any suggestion is welcome. We say $f: [\omega_2]^2\to \omega_1$ is unbounded if for any $\Gamma\in [\omega_2]^{\omega_1}$ we have $f''[\...
0
votes
2answers
39 views

number of finite subsets of a cardinal $\kappa$

Why there are only $\kappa$ many finite subsets of a cardinal $\kappa$? There are obviously at least $\kappa$ of them, but why also at most $\kappa$ of them?
1
vote
1answer
43 views

Are there countably many elements?

Consider the function $d$ mapping the Intervals $I = \{[a,b) \mid a<b \}$ to its power set defined by $$d([a,b)) := \{ [a+(b-a)2^{-(k+1)},a+(b-a) 2^-k \mid k=0,1,2,3,\ldots \}$$ So for example $d([...
0
votes
1answer
92 views

0,1-Tree, number of branches

How many branches has this tree: $\{s\in 2^{<\kappa}:|\alpha\in dom(s):s(\alpha)\neq 0|<\aleph_0\}$, and why? How does the tree look like, i.e. what is its shape? Thank you.
1
vote
0answers
37 views

Is $Ord$ weakly compact?

$\DeclareMathOperator{\Ord}{Ord}$Let $c: \Ord^{[2]} \rightarrow 2$ be a $2$-coloring of the class of pairs of ordinals. Is there a definable class-sized subclass $H$ of $\Ord$ which is $c$-...
0
votes
1answer
20 views

Reconstruct a set of enumerations from the set of its restrictions to smaller domains

Let $\alpha_1$ be the first uncountable ordinal. Let $U$ be the set of all $\alpha_1$-long enumerations of $\alpha_1$ (equivalently: $U$ is the set of bijections $\alpha_1 \to \alpha_1$). Let $S\...
5
votes
0answers
95 views

Reference Request: A Tychonoff space $X$ where the game $\mathrm{G}_1(\Omega,\Omega)$ is undetermined

Given a Tychonoff space $X$, let $\Omega$ be the set of all $\omega$-coverings of $X$, where by $\omega$-cover we mean a collection $\mathcal{U}$ of open sets of $X$ such that for any $F\in[X]^{<\...
0
votes
1answer
57 views

Shrinking a family of sets preserving cardinality

I'm having trouble with a simple problem about infinitary combinatorics. Suppose $\kappa$ is an infinite cardinal, $\mathcal A=\{A_\alpha: \alpha<\kappa\}$ and for each $\alpha$, $|A_\alpha|=\kappa$...
2
votes
1answer
210 views

Version of Fodor's Lemma

I know that pressing down functions exist, but it is not intuitively clear to me. Is there a way to prove the existence of such functions in this form: $$f: \omega_1 \to \omega_1 $$ $$\exists \alpha \...
5
votes
2answers
163 views

A consequence of the continuum hypothesis

A set $S \subset \omega_1 \times \omega$ is a large rectangle if $S = A \times B$ where $A$ is uncountable, and $B$ is infinite. Assuming the continuum hypothesis, is there necessarily a set $T \...
2
votes
0answers
87 views

Proving that a set is an ultrafilter.

A sequence of ultrafilters of $\omega$ (therefore each $p_n \in \beta \omega$) $p_n$ is discrete if there exists a sequence $X_n$ of subsets of $\omega$ such that for each $n$, $X_n \in p_n$ and if $n ...
4
votes
1answer
87 views

Showing that the least cardinal $\kappa$ such that a specific poset has no strong antichain of size $\kappa$ is regular

Given a poset $P$, let $\operatorname{cc}(P)$ be the least cardinal $\kappa$ such that $P$ has no strong antichains of size $\kappa$ — i.e. for any set of size $\kappa$, there exist two elements ...
2
votes
1answer
148 views

The splitting number is uncountable

How can we show that any splitting family is uncountable? A family ${\cal F} \subset 2^\omega$ is called a splitting family if for every infinite $X \subset \omega$ there exists $A \in F$ such that ...
3
votes
0answers
198 views

Understanding a proof about almost disjoint families

I am having trouble on understanding Michael Hrusak's proof on "Recent Progress in General Topology III", page 605. The theorem states the following: Given an AD family $\mathcal A$ and a ...
2
votes
0answers
113 views

Extending almost disjoint family preserving the positivity of a member

An almost disjoint family is an infinite collection $\mathcal A$ of infinite subsets of $\omega$ such that for all $A, B \in \mathcal A$, the intersection $A \cap B$ is finite. A mad family is a ...
2
votes
1answer
101 views

Kunen's proof of $\mathfrak{b}\le \mathfrak{a}$

I'm reading Kunen's Set Theory, and I'm stuck on his proof that least size of a dominating family of $\omega^\omega$, denoted by $\mathfrak{b}$, is less than or equal to the least size of a maximal ...
1
vote
0answers
50 views

Recovering (reconstructing) all possible walks from a finite subset of walks over a finite graph

Compute a finite set of walks for a given finite graph $g$ such that the (possibly infinitely large) set of all (finitely long) walks over the same graph can be recovered (reconstructed).  Background ...
1
vote
1answer
112 views

Do well pruned $\omega_1$ Aronszajn trees have any branches?

If a tree is well pruned then any node will have a node above it at any level of the tree above the nodes level. Doesn't this mean that no branch can have a countable height, because if you assume a ...
0
votes
1answer
44 views

Stochastics in infinity

I am a German student who will finish his A-levels in around half a year, and for quite a long time I have this question on mind that I'm unable to find an answer to. You have a value y=100 Now, you ...
4
votes
1answer
88 views

Free infinitary algebras

Let $\Sigma$ be a set which consists of function symbols with allowed infinite arities (which can be arbitrary sets). A $\Sigma$-algebra is a set $X$ equipped with maps $\omega_* : X^d \to X$ for each ...
3
votes
0answers
139 views

special Aronszajn trees

I have found two different definitions for Aronszajn special trees: somewhere they say they are Aronszajn trees where there exists a strictly increasing function from the tree to the rational numbers, ...
2
votes
1answer
47 views

$\Box_{\kappa}$ principle, unknown derivation of its property

In Set Theory: The Third Millennium Edition, revised and expanded, page $443$, Jech states the $\Box_{\kappa}$ principle as follows: $(\Box_\kappa)$ There exists a sequence $\langle C_\alpha:\alpha\...
0
votes
0answers
49 views

Dearrangements and $e$

I have often heard a nice way that $e$ can appear in probability theory -- that, say, I had an abitrarily large box of specialty chocolates (so they are all unique), and I mixed them all up. The ...
2
votes
0answers
57 views

Generalization of Helly theorem

I am working on Helly theorems But it is a very famous theorem which has many many different types; Here is a well-known and basic version of Helly: "Lectures on discrete geometry Jiri Matousek" ...
3
votes
0answers
95 views

Are there $\kappa$-closed $\kappa$-Aronszajn trees for $\kappa>\omega_1$?

It is an easy exercise in Kunen that no pruned (i.e. without terminal nodes) $\kappa$-Aronszajn tree is $\kappa$-closed as a partial order (for $\kappa$ regular). I'm wondering if the same is true ...
0
votes
1answer
114 views

Countably closed forcings preserves $\diamondsuit$ sequence

Given a forcing poset $\mathbb{P}$ it is said that $\mathbb{P}$ is countably closed if given $\{p_n\}_n$ a decreasing sequence of conditions there exists a condition $q\in \mathbb{P}$ below them. As ...
1
vote
1answer
40 views

Existence of branches on a tree.

I would like to ask an easy detail about the proof of the following combinatorial question. Suppouse that $\kappa,\lambda$ are infinite regular cardinals and $\lambda<\kappa$. If $T$ is a tree of ...
3
votes
1answer
125 views

Jech Third Edition Set Theory p191 Theorem 13.21 Jensen. What is the Essence of the Diamond Principle?

The diamond principle in theorem 13.21 of Jech : There exists Z = $\langle S_\alpha : \alpha < \omega_1\rangle$ with $S_\alpha\subset \alpha$, such that for every X $\subset \omega_1$, the set Y=$...
1
vote
1answer
87 views

Ineffable cardinals and diamond principle.

A regular uncountable cardinal $\kappa$ is said to be ineffable iff for every $\{A_\alpha\}_{\alpha<\kappa}$ such that $A_\alpha\subset \alpha$ there exists a stationary set $S$ verifying that for ...
2
votes
0answers
108 views

Kurepa trees and inaccessible cardinals in $L$

Given a regular uncountable cardinal $\kappa$ we say that a $\kappa-$tree is $\kappa-$Kurepa if it has at least $\kappa^+$ branches. If $\kappa=\omega_1$ we simply say that $T$ is Kurepa. In this ...
1
vote
1answer
78 views

Prikry Hypothesis implies Kurepa Hypothesis

I want to show that $\textbf{HP}_\kappa$ implies $\textbf{HK}_\kappa$, Prikry hypothesis and Kurepa hypothesis in $\kappa$, respectively. Where \begin{equation} \textbf{HK}_\kappa: \text{ There's a ...
4
votes
0answers
148 views

Every family $\mathscr{A} $ of sets satisfies $|\mathscr{A} \setminus \mathscr{A}| \geq |\mathscr{A}|$

Let $\mathscr{A} $ be a set of sets. Let's denote $\{A \setminus B : A,B \in \mathscr{A}\}$ by $\mathscr{A} \setminus \mathscr{A} $. The Marica-Schönheim theorem in combinatorics says that $|\...
1
vote
1answer
147 views

Equivalents forms of $\diamondsuit$

I'm trying to see that assuming $\diamondsuit$ the following holds: Exists $\{A_\alpha\}_{\alpha<\omega_1}$ such that $A_\alpha\subset\alpha\times\alpha$ and for every $A\subset \omega_1\times\...