# Hints Homework 8

**Problem 3**

Proceed as follows:

- Randomly -color the integers. Let be a -AP. Calculate the probability that is monochromatic.
- In HW 7, \#3 you computed the number of -APs in . Use this to show that the probability that a monochromatic -AP exists in is
- Argue that for large enough , will make this less than .

**Problem 4**

Here is a `template’: We show that is primitive recursive.

Then we argue as follows:

- We put with , the identity. is primitive recursive since (projection of a unary function in the first coordinate) is.
- We put , where . is primitive recursive since successor and projection are, and the primitive recursive functions are closed under substitution (4).
- By closure under primitive recursion (5), is primitive recursive, and defines .

Advertisements

Leave a Comment