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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: