Complete list of blog posts

• A strong form of König’s lemma A student proposed to me the following strong form of König’s lemma: Conjecture. Suppose that $G=(V,E)$ is a countable a graph, and there is a partition of $V$ into countably many pieces $V=\bigcup_{n<\omega}V_n$, such that: for all $n<\omega$, $V_n$ is finite (but nonempty); for all two distinct $n,m<\omega$, for each $x\in V_n$, there is $y\in V_m$ with $\{x,y\}\in ... • Dushnik-Miller for regular cardinals (part 2) In this post, we shall provide a proof of Todorcevic’s theorem, that$\mathfrak b=\omega_1$implies$\omega_1\not\rightarrow(\omega_1,\omega+2)^2$. This will show that the Erdos-Rado theorem that we discussed in an earlier post, is consistently optimal. Our exposition of Todorcevic’s theorem would be slightly more general, with the benefit of yielding another famous theorem of Todorcevic:$\omega_1\not\rightarrow^2_{\omega_1}$. We commence ... • Prolific Souslin trees In a paper from 1971, Erdos and Hajnal asked whether (assuming CH) every coloring witnessing$\aleph_1\nrightarrow^2_3$has a rainbow triangle. The negative solution was given in a 1975 paper by Shelah, and the proof and relevant definitions may be found in this previous blog post. Shelah’s construction of a coloring witnessing$\aleph_1\nrightarrow^2_\omega$with no rainbow triangles ... • Square principles Since the birth of Jensen’s original Square principle, many variations of the principle were introduced and intensively studied. Asaf Karagila suggested me today to put some order into all of these principles. Here is a trial. Definition. A square principle for a cardinal$\theta$asserts the existence of a sequence$\Gamma=\langle C_\alpha \mid \alpha<\theta\rangle$such that ... • Variations on diamond Jensen’s diamond principle has many equivalent forms. The translation between these forms is often straight-forward, but there is one form whose equivalence to the usual form is somewhat surprising, and Devlin’s translation from one to the other, seems a little bit of a magic. Let us provide a proof. Lemma (Devlin, Kunen). The following are equivalent: There ... • Generalizations of Martin’s Axiom and the well-met condition Recall that Martin’s Axiom asserts that for every partial order$\mathbb P$satisfying c.c.c., and for any family$\mathcal D$of$<2^{\aleph_0}$many dense subsets of$\mathbb P$, there exists a directed subset$G$of$\mathbb P$such that$G\cap D\neq\emptyset$for all$D\in\mathcal D$. Solovay and Tennenbaum proved that Martin’s Axiom is consistent with$2^{\aleph_0}>\aleph_1$. In , ... • Prikry forcing may add a Souslin tree A celebrated theorem of Shelah states that adding a Cohen real introduces a Souslin tree. Are there any other examples of notions of forcing that add a$\kappa$-Souslin tree? and why is this of interest? My motivation comes from a question of Schimmerling, which I shall now motivate and state. Recall that Jensen proved that GCH together ... • The reflection principle$R_2$A few years ago, in this paper, I introduced the following reflection principle: Definition.$R_2(\theta,\kappa)$asserts that for every function$f:E^\theta_{<\kappa}\rightarrow\kappa$, there exists some$j<\kappa$for which the following set is nonstationary: $$A_j:=\{\delta\in E^\theta_\kappa\mid f^{-1}\cap\delta\text{ is nonstationary}\}.$$ I wrote there that by a theorem of Magidor,$R_2(\aleph_2,\aleph_1)$is consistent modulo the existence of a weakly compact cardinal, ... • The chromatic numbers of the Erdos-Hajnal graphs Recall that a coloring$c:G\rightarrow\kappa$of an (undirected) graph$(G,E)$is said to be chromatic if$c(v_1)\neq c(v_2)$whenever$\{v_1,v_2\}\in E$. Then, the chromatic number of a graph$(G,E)$is the least cardinal$\kappa$for which there exists a chromatic coloring$c:G\rightarrow\kappa$. Motivated by a paper I found yesterday in the arXiv, this post will be ... • Polychromatic colorings These are lectures notes of two talks Dani Livne gave in our Infinite Combinatorics seminar. I did not take notes in real-time, hence, all possible mistakes here are due to myself. Recall that a function$f:A\rightarrow B$is said to be$\theta$-to-1 if for every$b\in B$, the preimage$f^{-1}\{b\}$has size$\theta$. It is said ... • Infinite Combinatorial Topology Back in 2005, as a master student, I attended a course by Boaz Tsaban, entitled “Infinite Combinatorial Topology”. A friend and I decided to produce lecture notes, but in a somewhat loose sense, that is: we sometimes omit material given in class, sometimes give alternative definitions or proofs, and sometimes include our own additional propositions. ... • The S-space problem, and the cardinal invariant$\mathfrak p$Recall that an$S$-space is a regular hereditarily separable topological space which is not hereditarily Lindelöf. Do they exist? Consistently, yes. However, Szentmiklóssy proved that compact$S$-spaces do not exist, assuming Martin’s Axiom. Pushing this further, Todorcevic later proved that there are no$S$-spaces under PFA. In the above-mentioned paper of Todorcevic, it is also proved ... • Dushnik-Miller for regular cardinals (part 3) Here is what we already know about the Dushnik-Miller theorem in the case of$\omega_1$(given our earlier posts on the subject):$\omega_1\rightarrow(\omega_1,\omega+1)^2$holds in ZFC;$\omega_1\rightarrow(\omega_1,\omega+2)^2$may consistently fail;$\omega_1\rightarrow(\omega_1,\omega_1)^2$fails in ZFC. In this post, we shall provide a proof of Todorcevic’s theorem that PFA implies$\omega_1\rightarrow(\omega_1,\alpha)^2$for all$\alpha<\omega_1$. We commence with a sequence of lemmas. Lemma 1. ... • Universal binary sequences Notation. Write$\mathcal Q(A):=\{ a\subseteq A\mid a\text{ is finite}, a\neq\emptyset\}$. Suppose for the moment that we are given a fixed sequence$\langle f_\alpha:\omega\rightarrow2\mid \alpha\in a\rangle$, indexed by some set$a$of ordinals. Then, for every function$h:a\rightarrow\omega$and$i<\omega$, we define the$i$-valuation of$h$,$h^i:a\rightarrow2$, by letting for all$\alpha\in a$: $$h^i(\alpha):=f_\alpha(h(\alpha)+i).$$ Given an initial state$h:a\rightarrow\omega$, ... • Syndetic colorings with applications to S and L Notation. Write$\mathcal Q(A):=\{ a\subseteq A\mid a\text{ is finite}, a\neq\emptyset\}$. Definition. An L-space is a regular hereditarily Lindelöf topological space which is not hereditarily separable. Definition. We say that a coloring$c:^2\rightarrow\omega$is L-syndetic if the following holds. For every uncountable family$\mathcal A\subseteq\mathcal Q(\omega_1)$of mutually disjoint sets, every uncountable$B\subseteq\omega_1$, and every$n<\omega$, there exist$a\in\mathcal A$, ... • Many diamonds from just one Recall Jensen’s diamond principle over a stationary subset$S$of a regular uncountable cardinal$\kappa$: there exists a sequence$\langle A_\alpha\mid \alpha\in S \rangle$such that$\{\alpha\in S\mid A\cap\alpha=A_\alpha\}$is stationary for every$A\subseteq\kappa$. Equivalently, there exists a sequence$\langle f_\alpha:\alpha\rightarrow\alpha\mid \alpha\in S\rangle$such that$\{\alpha\in S\mid f\restriction\alpha=f_\alpha\}$is stationary for every function$f:\kappa\rightarrow\kappa$. It is ... • c.c.c. forcing without combinatorics In this post, we shall discuss a short paper by Alan Mekler from 1984, concerning a non-combinatorial verification of the c.c.c. property for forcing notions. Recall that a notion of forcing$\mathbb P$is said to satisfy the c.c.c. iff all of its antichains are countable. A generalization of this property is that of being proper: Definition ... • The Engelking-Karlowicz theorem, and a useful corollary Theorem (Engelking-Karlowicz, 1965). For cardinals$\kappa\le\lambda\le\mu\le 2^\lambda$, the following are equivalent:$\lambda^{<\kappa}=\lambda$; there exists a collection of functions,$\langle f_i:\mu\rightarrow\lambda\mid i<\lambda\rangle$, such that for every$X\in^{<\kappa}$and every function$f:X\rightarrow\lambda$, there exists some$i<\lambda$with$f\subseteq f_i$. Proof. (2)$\Rightarrow$(1) Suppose$\langle f_i:\mu\rightarrow\lambda\mid i<\lambda\rangle$is a given collection. Then $$|\{ f_i\restriction\theta\mid i<\lambda,\theta<\kappa\}|\le\lambda<\lambda^{<\kappa},$$ so there must exists some$f\in{}^{<\kappa}\lambda$with$f\nsubseteq ...
• Walk on countable ordinals: the characteristics In this post, we shall present a few aspects of the method of walk on ordinals (focusing on countable ordinals), record its characteristics, and verify some of their properties. All definitions and results in this post are due to Todorcevic. Let $\langle C_\alpha\mid\alpha<\omega_1\rangle$ be a sequence such that $C_{\alpha+1}=\{\alpha\}$ for all $\alpha<\omega_1$, and for all limit ...
• Shelah’s approachability ideal (part 1) Given an infinite cardinal $\lambda$, Shelah defines an ideal $I$ as follows. Definition (Shelah, implicit in here). A set $S$ is in $I^{<\lambda}$, and some club $E\subseteq\lambda$, so that for every $\delta\in S\cap E$, there exists a cofinal subset $A_\delta\subseteq\delta$ such that: $\text{otp}(A_\delta)<\delta$ (in particular, ...
• Happy new jewish year!
• c.c.c. vs. the Knaster property After my previous post on Mekler’s characterization of c.c.c. notions of forcing, Sam, Mike and myself discussed the value of it . We noticed that a prevalent verification of the c.c.c. goes like this: given an uncountable set of conditions, apply the $\Delta$-system lemma, thin out the outcome some more (typically, a few iterations are ...
• Shelah’s approachability ideal (part 2) In a previous post, we defined Shelah’s approachability ideal $I^{<\lambda}$ such that for club many $\delta\in S$, the union $\bigcup_{\alpha<\delta}\mathcal D_\alpha$ contains all the initial segments of some small cofinal subset, $A_\delta$, of $\delta$. The ...
• Partitioning the club guessing In a recent paper, I am making use of the following  fact. Theorem (Shelah, 1997). Suppose that $\kappa$ is an accessible cardinal (i.e., there exists a cardinal $\theta<\kappa$ such that $2^\theta\ge\kappa)$. Then there exists a sequence $\langle g_\delta:C_\delta\rightarrow\omega\mid \delta\in E^{\kappa^+}_\kappa\rangle$ such that $C_\delta$ is a club of $\delta$ of order-type $\kappa$, and with the property that ...
• Bell’s theorem on the cardinal invariant $\mathfrak p$ In this post, we shall provide a proof to a famous theorem of Murray Bell stating that $MA_\kappa(\text{the class of }\sigma\text{-centered posets})$ holds iff $\kappa<\mathfrak p$. We commence with defining the cardinal invariant $\mathfrak p$. For sets $A$ and $B$, we write $B\subseteq^* A$ iff $\sup(B\setminus A)<\sup(B)$. We say that $B$ is a pseudointersection of a ...
• A large cardinal in the constructible universe In this post, we shall provide a proof of Silver’s theorem that the Erdos caridnal $\kappa(\omega)$ relativizes to Godel’s constructible universe. First, recall some definitions. Given a function $f:^n$, we have $f(x)=f(y)$. Let $\kappa\rightarrow(\alpha)^{<\omega}_\mu$ denote the ...
• Comparing rectangles with squares through rainbow sets In Todorcevic’s class last week, he proved all the results of Chapter 8 from his Walks on Ordinals book, up to (and including) Theorem 8.1.11. The upshots are as follows: Every regular infinite cardinal $\theta$ admits a naturally defined function $osc:^2\rightarrow\omega$; there exists, again natural, notion of unbounded subfamily of $\mathcal P(\theta)$, and if $\mathcal X$ ...
• An inconsistent form of club guessing In this post, we shall present an answer (due to P. Larson) to a question by A. Primavesi concerning a certain strong form of club guessing. We commence with recalling Shelah’s concept of club guessing. Concept (Shelah). Given a regular uncountable cardinal $\kappa$ and a subset $S\subseteq\kappa$, we say that $\langle C_\alpha\mid\alpha\in S\rangle$ is a club-guessing sequence, ...
• Prikry Forcing Recall that the chromatic number of a (symmetric) graph $(G,E)$, denoted $\text{Chr}(G,E)$, is the least (possible finite) cardinal $\kappa$, for which there exists a coloring $c:G\rightarrow\kappa$ such that $gEh$ entails $c(g)\neq c(h)$. Given a forcing notion $\mathbb P$, it is natural to analyze $\text{Chr}(\mathbb P,\bot)$, where $p\bot q$ iff $p$ and $q$ are incompatible conditions. Here ...
• Open coloring and the cardinal invariant $\mathfrak b$ Nik Weaver asked for a direct proof of the fact that Todorcevic’s axiom implies the failure of CH fails. Here goes. Notation. For a set $X$, we write $^2$ for the set of unordered pairs $\{ \{x,x’\}\mid x,x’\in X, x\neq x’\}$. Definition (Todorcevic’s axiom). If $X$ is a separable metric space, and $^2=K_0\cup K_1$, with $K_0$ open ...
• Gabriel Belachsan (14/5/1976 – 20/8/2013) רק כשעיני סגורות, עולם נגלה לפני http://www.youtube.com/watch?v=6Mq-xMhhe3s
• Review: Is classical set theory compatible with quantum experiments? Yesterday, I attended a talk at the Quantum Foundations seminar at the beautiful Perimeter Institute for Theoretical Physics (Waterloo, Ontario). The (somewhat provocative) title of the talk was “Is Classical Set Theory Compatible with Quantum Experiments?”, and the speaker was Radu Ionicioiu. Here are the links to the slides and videotape. To make a long story short, the ...
• PFA and the tree property at $\aleph_2$ Recall that a poset $\langle T,\le\rangle$ is said to be a $\lambda^+$-Aronszajn tree, if it isomorphic to a poset $(\mathcal T,\subseteq)$ of the form: $\emptyset\in \mathcal T\subseteq{}^{<\lambda^+}\lambda$; Write $\mathcal T_\alpha:=\{\sigma\in\mathcal T\mid \text{dom}(\sigma)=\alpha\}$; for all $\alpha<\lambda^+$, $\mathcal T_\alpha$ has size $\le\lambda$, say $\mathcal T_\alpha=\{ T_\alpha^i\mid i<\lambda\}$; if $\sigma\in\mathcal T$ and $\alpha<\lambda^+$, then there exists $\tau\in\mathcal T_\alpha$ such that $\sigma\cup\tau\in{}^{<\lambda^+}\lambda$; $\mathcal ... • A Kurepa tree from diamond-plus Recall that$T$is said to be a$\kappa$-Kurepa tree if$T$is a tree of height$\kappa$, whose levels$T_\alpha$has size$\le|\alpha|$for co-boundedly many$\alpha<\kappa$, and such that the set of branches of$T$has size$>\kappa$. In this post, we shall remind ourselves of the proof of Jensen’s theorem that$\diamondsuit^+(\kappa)$entails ... • An$S$-space from a Cohen real Recall that an$S$-space is a regular hereditarily separable topological space which is not hereditarily Lindelöf. In this post, we shall establish the consistency of the existence of such a space. Theorem (Roitman, 1979). Let$\mathbb C=({}^{<\omega}\omega,\subseteq)$be the notion of forcing for adding a Cohen real. Then, in the generic extension by forcing with$\mathbb C$, ... • Review: Stevo Todorcevic’s CRM-Fields-PIMS Prize Lecture After winning the 2012 CRM-Fields-PIMS Prize, Stevo Todorcevic gave a series of talks on his research: at CRM, at PIMS and at the Fields Institute. The director of the Fields Institute asked me to write a short review on Stevo’s Fields lecture for the Winter 2013 Fields Notes, and I thought I should post my review ... • The S-space problem, and the cardinal invariant$\mathfrak b$Recall that an S-space is a regular hereditarily separable topological space which is not hereditarily Lindelöf. In a previous post, we showed that such a space exists after adding a Cohen real. Here, we shall construct one from an arithmetic assumption. Theorem (Todorcevic, 1989). If$\mathfrak b=\omega_1$, then there exists an$S$-space. Proof. Let$\overrightarrow f=\langle f_\alpha\mid\alpha<\omega_1\rangle$... • Erdős 100 The influential mathematician Paul Erdős was born 100 years ago, 26 March 1913, in Budapest. One evidence of his impact on mathematics is reflected in the particular list of invited speakers for the upcoming conference in his honor. Erdős is also famous for taking his birthdays somewhat seriously. Here is a funny video of him talking about ... • The order-type of clubs in a square sequence Recall Jensen’s notion of square: Definition (Jensen): For an infinite cardinal$\lambda$,$\square_\lambda$asserts the existence of a sequence$\overrightarrow C=\left\langle C_\alpha\mid\alpha\in\text{acc}(\lambda^+)\right\rangle$such that for every limit$\alpha<\lambda^+$:$C_\alpha$is a club subset of$\alpha$of order-type$\le\lambda$; if$\beta\in\text{acc}(C_\alpha)$, then$C_\beta=C_\alpha\cap\beta$. Now, consider the set$S(\overrightarrow C):=\{ \alpha<\lambda^+\mid \text{otp}(C_\alpha)=\lambda\}$. If$\lambda$is a regular cardinal, then$S(\overrightarrow C)=\{\alpha<\lambda^+\mid\text{cf}(\alpha)=\lambda\}$, and ... • Dushnik-Miller for singular cardinals (part 2) In the first post on this subject, we provided a proof of$\lambda\rightarrow(\lambda,\omega+1)^2$for every regular uncountable cardinal$\lambda$. In the second post, we provided a proof of$\lambda\rightarrow(\lambda,\omega)^2$for every singular cardinal$\lambda$, and showed that$\lambda\rightarrow(\lambda,\omega+1)^2$fails for every cardinal of countable cofinality. In this post, we shall be dealing with the missing case, proving ... • A natural Mandelbrot set Chris Hadfield is a Canadian astronaut, with a very high-profile twitter account. He posts there beautiful photos everyday, and I (plus half a million followers) enjoy it very much. Today, Chris posted the following picture: and I find it quite similar to the famous Mandelbrot set: Recall that the so-called Mandelbrot set is a fractal whose shape consists ... • Jones’ theorem on the cardinal invariant$\mathfrak p$This post continues the study of the cardinal invariant$\mathfrak p$. We refer the reader to a previous post for all the needed background. For ordinals$\alpha,\alpha_0,\alpha_1,\beta,\beta_0,\beta_1$, the polarized partition relation $$\left(\begin{array}{c}\alpha\\\beta\end{array}\right)\rightarrow\left(\begin{array}{cc}\alpha_0&\alpha_1\\\beta_0&\beta_1\end{array}\right)$$ asserts that for every coloring$f:\alpha\times\beta\rightarrow 2$, (at least) one of the following holds: there are$A\subseteq\alpha$and$B\subseteq\beta$with$\text{otp}(A)=\alpha_0, \text{otp}(B)=\beta_0$s.t.$f=\{0\}$; there ... • Forcing with a Souslin tree makes$\mathfrak p=\omega_1$I was meaning to include a proof of Farah’s lemma in my previous post, but then I realized that the slick proof assumes some background which may worth spelling out, first. Therefore, I am dedicating a short post for a self-contained proof of this lemma. Recall that a Souslin tree is a poset$\mathbb T=\langle T,<\rangle$... • James Earl Baumgartner Sad news: Jim Baumgartner passed away. See here. • The$\Delta$-system lemma: an elementary proof Here is an elementary proof of (the finitary version of) the$\Delta$-system lemma. Thanks goes to Bill Weiss who showed me this proof! Lemma. Suppose that$\kappa$is a regular uncountable cardinal, and$\mathcal A$is a$\kappa$-sized family of finite sets. Then there exists a subcollection$\mathcal B\subseteq\mathcal A$of size$\kappa$, together with a finite set ... • What’s next? I took an offer for a tenure-track position at the Mathematics department of Bar-Ilan University. http://www.youtube.com/watch?v=zJUXFhgN9kQ • The uniformization property for$\aleph_2$Given a subset of a regular uncountable cardinal$S\subseteq\kappa$,$UP_S$(read: “the uniformization property holds for$S$”) asserts that for every sequence$\overrightarrow f=\langle f_\alpha\mid \alpha\in S\rangle$satisfying for all$\alpha\in S$:$f_\alpha$is a 2-valued function;$\text{dom}(f_\alpha)$is a cofinal subset of$\alpha$of minimal order-type, there exists a function$f:\kappa\rightarrow 2$such that for every limit ... • Kurepa trees and ineffable cardinals Recall that$T$is said to be a$\kappa$-Kurepa tree if$T$is a tree of height$\kappa$, whose levels$T_\alpha$has size$\le|\alpha|$for co-boundedly many$\alpha<\kappa$, and such that the set of branches of$T$has size$>\kappa$. Recall also that an uncountable cardinal$\kappa$is said to be ineffable if for every sequence ... • The P-Ideal Dichotomy and the Souslin Hypothesis John Krueger is visiting Toronto these days, and in a conversation today, we asked ourselves how do one prove the Abraham-Todorcevic theorem that PID implies SH. Namely, that the next statement implies that there are no Souslin trees: Definition. The P-ideal Dichotomy asserts that for every uncountable set$Z$, and every P-Ideal$\mathcal I$over$^{\le\aleph_0}$, ... • Jane’s Addiction visiting Toronto Last night, I went to see a live show by Jane’s Addiction, in downtown Toronto. Here’s a video snippet from that show which I could found on YouTube: http://www.youtube.com/watch?v=vprun9x8QWE The playlist was excellent, but there was one song which I was missing – “Had a dad”, so I compensate the loss, by including it here..: http://www.youtube.com/watch?v=zdPCwxCg1a4 • Afghan Whigs on Jimmy Fallon Performing “I’m Her Slave” (from their album Congregation) at NBC’s studios, 22-May-2012: • Pure logic While traveling downtown today, I came across a sign near a local church, with a quotation of Saint-Exupéry: “Pure logic is the ruin of the spirit”? So sad. • Dushnik-Miller for regular cardinals (part 1) This is the first out of a series of posts on the following theorem. Theorem (Erdos-Dushnik-Miller, 1941). For every infinite cardinal$\lambda$, we have: $$\lambda\rightarrow(\lambda,\omega)^2.$$ Namely, for any coloring$c:^2=\{1\}$. In this post, we shall focus on the case ... • Dushnik-Miller for singular cardinals (part 1) Continuing the previous post, let us now prove the following. Theorem (Erdos-Dushnik-Miller, 1941). For every singular cardinal λ, we have: $$\lambda\rightarrow(\lambda,\omega)^2.$$ Proof. Suppose that$\lambda$is a singular cardinal, and$c:^2\rightarrow\{0,1\}$is a given coloring. For any ordinal$\alpha<\lambda$, denote$I_\alpha:=\{ \beta\in(\alpha,\lambda)\mid c(\alpha,\beta)=1\}$. Subclaim. At least one of the following holds: there exists an infinite subset$B\subseteq\lambda$for which$c“^2=\{1\}\$; there ...