
{"id":20,"date":"2012-04-10T22:12:16","date_gmt":"2012-04-11T08:12:16","guid":{"rendered":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/?p=20"},"modified":"2013-01-25T12:21:27","modified_gmt":"2013-01-25T22:21:27","slug":"cannot-reduce-meet-to-join","status":"publish","type":"post","link":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/cannot-reduce-meet-to-join\/","title":{"rendered":"Cannot reduce meet to join"},"content":{"rendered":"<p>Here is an argument from Culver&#8217;s MA thesis from 2010.<\/p>\n<p>Suppose the sequence $(A_0\\wedge A_1,A_2\\wedge A_3,\\ldots)$ is $\\vee$-reducible to $A$.<br \/>\nLet&#8217;s look at the use of the $\\vee$-truth-table reduction for computing $A_8\\wedge A_9$.<br \/>\nWe claim that after seeing only $A_0,\\ldots,A_7$ we can rule out one possibility for $(A_8,A_9)$, thereby making money on $A$ and thus showing $A$ is not random.<\/p>\n<p>If the use is only $A_0,\\ldots,A_7$ then let&#8217;s say the reduction predicts $A_8\\wedge A_9=1$. Then we can rule out the pair $(0,1)$. If the reduction predicts $0$ we can rule out $(1,1)$.<\/p>\n<p>If the use is only $A_0,\\ldots,A_8$ then based on us looking at $A_0,\\ldots,A_7$ we can determine that the reduction predicts $1\\wedge A_9=1$ or we can determine that the reduction predicts $1\\wedge A_9=0$. Then we can rule out the pair $(1,0)$, or $(1,1)$, respectively.<\/p>\n<p>Finally, if the reduction uses all of $A_0,\\ldots,A_9$ then based on us looking at $A_0,\\ldots,A_7$ we can determine that the reduction predicts $1\\wedge 1=1$ and we can determine that the reduction predicts $1\\wedge 0=1$ and&#8230; the reduction cannot correctly predict the whole $\\wedge$ function or else $\\wedge$ would be an element of the clone $\\{\\vee\\}$.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Here is an argument from Culver&#8217;s MA thesis from 2010. Suppose the sequence $(A_0\\wedge A_1,A_2\\wedge A_3,\\ldots)$ is $\\vee$-reducible to $A$. Let&#8217;s look at the use of the $\\vee$-truth-table reduction for computing $A_8\\wedge A_9$. We claim that after seeing only $A_0,\\ldots,A_7$ we can rule out one possibility for $(A_8,A_9)$, thereby making money on $A$ and thus &hellip; <a href=\"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/cannot-reduce-meet-to-join\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Cannot reduce meet to join<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,5],"tags":[],"class_list":["post-20","post","type-post","status-publish","format-standard","hentry","category-computability","category-research"],"_links":{"self":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/20","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/comments?post=20"}],"version-history":[{"count":4,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/20\/revisions"}],"predecessor-version":[{"id":982085,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/20\/revisions\/982085"}],"wp:attachment":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/media?parent=20"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/categories?post=20"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/tags?post=20"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}