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
0answers
188 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–...
1
vote
1answer
39 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 ...
0
votes
0answers
23 views

Schur function in linerly shifted power symmetric basis

Previously I have aksed the following question about schur function in power symmetric basis Schur function principal specialisation Let $s_{\lambda}(p_1,p_2,)$ denote schur function in power-sum ...
2
votes
0answers
68 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_\...
7
votes
1answer
126 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 ...
1
vote
2answers
59 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 ...
0
votes
1answer
48 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 ...
0
votes
1answer
101 views

Can manoeuvres in a cardinal be shuffled?

Difficult... Informally: suppose you take a set $B$ (a 'board') and cover some of the elements with pennies or pawns. Then you pick up a penny and put it on a different point of $B$ that is empty. ...
2
votes
1answer
49 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 \...
3
votes
1answer
200 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_\...
5
votes
1answer
155 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|...
1
vote
2answers
95 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 ...
1
vote
1answer
51 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)...
1
vote
0answers
31 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-...
1
vote
1answer
120 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 ...
7
votes
2answers
214 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 ...
2
votes
1answer
143 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
152 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
74 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
95 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
33 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
121 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
52 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
62 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
138 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
125 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
95 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
72 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
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 (...
1
vote
1answer
258 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
45 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
52 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
55 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
44 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
44 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
219 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
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 \...
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
170 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
61 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
154 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
77 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
132 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
256 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
62 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
50 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
157 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
44 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
110 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]^{<\...

1
2 3 4 5