Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713
{"id":38,"date":"2016-05-07T23:47:37","date_gmt":"2016-05-07T23:47:37","guid":{"rendered":"http:\/\/babarber.uk\/?p=38"},"modified":"2016-05-07T23:47:37","modified_gmt":"2016-05-07T23:47:37","slug":"ultrafilter-quantifiers-and-hindmans-theorem","status":"publish","type":"post","link":"https:\/\/babarber.uk\/38\/ultrafilter-quantifiers-and-hindmans-theorem\/","title":{"rendered":"Ultrafilter quantifiers and Hindman’s theorem"},"content":{"rendered":"

A filter<\/em> on $\"\mathbb N\"$ is a consistent notion of largeness for subsets of $\"\mathbb N\"$ . “Largeness” has the following properties. <\/p>\n

\n
if $\"A\"$ is large and $\"A \subseteq B\"$ then $\"B\"$ is large<\/li>\n
if $\"A\"$ and $\"B\"$ are large then $\"A \cap B\"$ is large<\/li>\n
the empty set is not large<\/li>\n<\/ul>\n
At most one of $\"A\"$ and $\"A^\text{c}\"$ is large; an ultrafilter<\/em> is a filter which always has an opinion about which it is.<\/p>\n
\n
either $\"A\"$ or $\"A^\text{c}\"$ is large<\/li>\n<\/ul>\n
The usual notation for “ $\"A\"$ is large” is $\"A \in \U\"$ , where $\"\U\"$ is the ultrafilter. This casts ultrafilters as sets, rather than notions of largeness. To bring the notion of largeness to the foreground we can use ultrafilter quantifiers<\/em>; we write $\"\U(x)\ A(x)\"$ , read “for $\"\U\"$ -most $\"x\"$ , $\"A(x)\"$ holds” (where we have also identified $\"A\"$ with the predicate “is a member of $\"A\"$ “). <\/p>\n
\n
if $\"\U(x)\ \phi(x)\"$ and $\"\phi \implies \psi\"$ then $\"\U(x)\ \psi(x)\"$ <\/li>\n
if $\"\U(x)\ \phi(x)\"$ and $\"\U(x)\ \psi(x)\"$ then $\"\U(x)\ \phi(x) \wedge \psi(x)\"$ <\/li>\n
$\"\forall x\ \phi(x) \implies \U(x)\ \phi(x) \implies \exists x\ \phi(x)\"$ <\/li>\n
$\"\neg [\U(x)\ \phi(x)] \iff \U(x)\ \neg \phi(x)\"$ <\/li>\n<\/ul>\n
From this point of view $\"\forall x\ \phi(x)\"$ says that the set of elements with property $\"\phi\"$ is everything, and $\"\exists x\ \phi(x)\"$ that the set of elements with property $\"\phi\"$ is non-empty. $\"\U\"$ behaves like a mixture of $\"\forall\"$ and $\"\exists\"$ , with the considerable advantage that logical operations pass through $\"\U\"$ unchanged without having to worry about De Morgan’s laws.<\/p>\n
Adding ultrafilters<\/h2>\n
It turns out that the set of ultrafilters on $\"\mathbb N\"$ is a model for the Stone\u2013\u010cech compactification $\"\beta \mathbb N\"$ of $\"(\mathbb N, +)\"$ . $\"\mathbb N\"$ is embedded as the set of principal ultrafilters<\/em> (“ $\"A\"$ is large if and only if $\"n \in A\"$ “), and the addition on $\"\mathbb N\"$ extends to $\"\beta \mathbb N\"$ : <\/p>\n
<\/span> <\/span> $\"\[\U + \V = \{A : \{x : A-x \in \V\} \in \U\}.\]\"$ <\/p>\n
(Here $\"A-x\"$ should be interpreted as $\"(A-x) \cap \mathbb N\"$ .) But to use this addition with quantifiers all we need to know is that $\"(\U+\V)\ \phi(x) \iff \U(x)\ \V(y)\ \phi(x+y)\"$ . If you can see that from the first definition then your brain is wired differently from mine.<\/p>\n
It is a fact that there exist idempotent<\/em> ultrafilters, with $\"\U + \U = \U\"$ . Given such a $\"\U\"$ , we can play the following game. Suppose that $\"\U(x)\ \phi(x)\"$ . Then $\"(\U+\U)(x)\ \phi(x)\"$ , so $\"\U(x)\ \U(y)\ \phi (x+y)\"$ and therefore $\"\U(x)\ \U(y)\ \phi(x) \wedge \phi(y) \wedge \phi (x+y)\"$ (by ANDing with the original assertion, and the original assertion with the dummy variable $\"x\"$ replaced by $\"y\"$ ). In particular, $\"\exists x\ \U(y)\ \phi(x) \wedge \phi(y) \wedge \phi (x+y)\"$ . But now we can fix a good choice of $\"x\"$ and repeat the whole process with $\"\psi(y) = \phi(x) \wedge \phi(y) \wedge \phi (x+y)\"$ in place of $\"\phi\"$ to get that <\/p>\n
<\/span> <\/span> $\"\[\exists x\ \exists y\ \U(z)\ \phi(x) \wedge \phi(y) \wedge \phi (x+y) \wedge \phi(z) \wedge \phi(x+z) \wedge \phi(y+z) \wedge \phi (x+y+z).\]\"$ <\/p>\n
Iterating, we eventually obtain an infinite sequence $\"x_1, x_2, \ldots\"$ such that $\"\phi\"$ holds for every sum of finitely many of the $\"x_i\"$ . Together with the observation that whenever $\"\mathbb N\"$ is finitely coloured exactly one of the colour classes is $\"\U\"$ -large this proves Hindman’s theorem, that we can always find an infinite sequence $\"x_1, x_2, \ldots\"$ such that every sum of finitely many terms has the same colour.<\/p>\n
A version of this argument with more of the details filled in is on the Tricki<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
A filter on is a consistent notion of largeness for subsets of . “Largeness” has the following properties. if is large and then is large if and are large then is large the empty set is not large At most one of and is large; an ultrafilter is a filter which always has an opinion … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[30],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/38"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=38"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/38\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=38"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=38"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=38"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}