## 403/503 – Homework 1

A collection ${\mathcal I}$ of subsets of ${\mathbb N}$ is called an independent family iff for any pairwise distinct $A_1,\dots,A_k,B_1,\dots,B_n$ in ${\mathcal I}$, we have that the set $A_1\cap\dots\cap A_k\cap({\mathbb N}\setminus B_1)\cap\dots\cap({\mathbb N}\setminus B_n)$ is infinite.

1. Show that there is an independent family of the same size as the reals. (This means that there is an independent family ${\mathcal I}$ for which there is a bijection between ${\mathcal I}$ and ${\mathbb R}$. If it is easier to think of it this way, you can use that ${\mathbb R}$ has the same size as the set $2^{\mathbb N}$ of infinite sequences of zeros and ones.)
2. Given a set $A\subseteq{\mathbb N},$ recall that its characteristic function is the map $\chi_A:{\mathbb N}\to\{0,1\}$ such that $\chi_A(n)=1$ if $n\in A,$ and $\chi_A(n)=0$ if $n\notin A.$ We can think of each $\chi_A$ as a vector in the space ${\mathbb R}^{\mathbb N}.$ Suppose now that ${\mathcal I}$ is an independent family, and show that $\{\chi_A\mid A\in{\mathcal I}\}$ is a linearly independent set. (Thus any basis for ${\mathbb R}^{\mathbb N}$ over ${\mathbb R}$ must have the same size as the reals.)
3. Consider ${\mathbb R}$ as a vector space over ${\mathbb Q},$ and show that any basis must have the same size as the reals.

### 3 Responses to 403/503 – Homework 1

1. Here is a `hint’ for the first problem: If $X$ is countable, it clearly suffices to find an independent family as required, but consisting of subsets of $X$ (so we replace each ${\mathbb N}\setminus B_i$ with $X\setminus B_i,$ of course).

Take $X=\{(a,A)\mid a\subseteq{\mathbb N}$ is finite, and $A\subseteq{\mathcal P}(a)\}.$ Check that $X$ is countable.

Now, given $S\subseteq{\mathbb N},$ let $t_S=\{(a,A)\in X\mid a\cap S\in A\}.$ The claim is that ${\mathcal I}=\{t_S\mid S\subseteq{\mathbb N}\}$ is as wanted.

Check that the assignment $S\mapsto t_S$ is injective.

To show that ${\mathcal I}$ satisfies the stronger independence requirement, suppose $X_1,\dots,X_n,Y_1,\dots,Y_m$ are infinite, pairwise distinct, subsets of ${\mathbb N}.$ Write $A=t_{X_1}\cap\dots\cap t_{X_n}\cap(X\setminus t_{Y_1})\cap\dots\cap(X\setminus t_{Y_m}).$ For each $1\le i\le n$ and $1\le j\le m$ let $\alpha_{ij}\in X_i\triangle Y_j.$ Show that for any finite $F\supseteq\{\alpha_{ij}\mid 1\le i\le n,1\le j\le m\}$ there is an ${\mathcal F}$ such that $(F,{\mathcal F})\in A.$

2. Hmm… Here is an easier way of arguing about the second problem (easier meaning that we do not need problem 1):

An almost disjoint family is a collection of subsets of ${\mathbb N}$ that are infinite, but the intersection of any two of them is finite. It is much easier (I think) to come up with an almost disjoint family of the same size as ${\mathbb R}$ than it is to come up with an independent family.

For example: For each real $r$ fix a sequence of (pairwise distinct) rationals converging to $r$ and let $A_r$ be the range of this sequence. Then $\{A_r\mid r\in{\mathbb R}\}$ is almost disjoint. (And, of course, ${\mathbb Q}$ is countable.)

To solve problem 2, one could start with an almost disjoint (rather than independent) ${\mathcal I}.$

3. For problem 3: a. If you assume the Continuum Hypothesis ${\sf CH}$ and answer the problem under this additional assumption, you get some partial credit, but to get full credit you need to answer the question independently of whether ${\sf CH}$ holds.

b. In case you need this, you may use that all bases have the same size. Again, one can solve the problem without appealing to this fact, but feel free to use it if you need it.

c. Also, in case you need it, feel free to assume the Schröder-Bernstein theorem: If $A$ and $B$ are sets and we have injections from $A$ into $B$ and from $B$ into $A,$ then $A$ and $B$ have the same size (i.e., there is a bijection between the two of them). Again, the problem can be solved without using this fact, but feel free to use it if you see the need.