Skip to content

Hints HW 6

September 29, 2011

Problem 1

This is the same argument as in class. Just replace {\{0,1\}^{\mathbb N}} by {\{0,1\}^\kappa}.

Problem 2

Again, generalize the argument from class. Consider the lexicographic ordering on {\{0,1\}^\kappa}, i.e. {f < g} iff {f(\alpha) < g(\alpha)} where {\alpha} is the least ordinal such that {f(\alpha) \neq g(\alpha)}. This is a linear order on {\{0,1\}^\kappa}.

Argue that {\{0,1\}^\kappa} with this ordering has no infinite decreasing or increasing sequence of length {\kappa^+}. For this, you have to “lift” the Pigeonhole Principle analysis to binary sequences of length {\kappa}.

Finally, define a {2}-coloring on {2^\kappa = |\{0,1\}^\kappa|} so that any {\kappa^+}-size homogeneous subset would give an increasing or decreasing sequence of length {\kappa^+}.

Problem 4

Assume for a contradiction there is such a decomposition {A = \bigcup A_i}, {B = \bigcup B_j}, and translations {a_1, \ldots, a_m} {b_1, \ldots, b_n}. Choose {N} much larger than {m,n,a_1, \ldots, a_m, b_1, \ldots, b_n}. Argue that

\displaystyle  	\bigcup (A_i \cap [-N,N]) + a_i

differs from {[-N,N]} only by a constant number of elements (independent of {N}). Do the same for the {B_i}, and use the fact that {{\mathbb Z} = A \cup B} to derive that

\displaystyle  	2 |[-N,N]| \leq |[-N,N]| + \text{constant},

which is impossible for large enough {N}.

Advertisements

From → Homework

Leave a Comment

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: