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
6
votes
2answers
75 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 ...
3
votes
1answer
98 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
votes
1answer
91 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 ...
2
votes
1answer
64 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$-...
5
votes
1answer
80 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
0answers
29 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
votes
1answer
82 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$ ...
1
vote
1answer
41 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'...
0
votes
0answers
57 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 \...
1
vote
1answer
96 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$(\...
4
votes
0answers
115 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=\...
6
votes
1answer
86 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 ...
1
vote
2answers
53 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, ...
-1
votes
1answer
22 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
195 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
44 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
47 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 ...
4
votes
0answers
49 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
40 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
43 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
193 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
35 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
64 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
133 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
153 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
61 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
121 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
237 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
48 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
45 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
137 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
38 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
23 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
101 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
63 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
310 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
183 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
95 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
109 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
192 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
215 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
115 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
116 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
156 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
47 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
110 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
198 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
53 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\...

1
2 3 4 5