On Terrorists and Ultrafilters

One of the coolest puzzles ever:

Three Big-Endian terrorists have plated a bomb somewhere in Lilliput's Little-Endian quarter.
The police was able to capture them however they refuse to cooperate and deliver the location of the bomb.

The police chief decided ti separate them to three cells and every day to chose one to be electroshocked.

The terrorists are not able to control when the bomb will be detonated, however it's still can be exploded by other members of the terrorist organization or by chance.

If the bomb explodes the authorities will punish the terrorists by electrifying  two of them every day.

After infinity days (this is were it gets abstract) the terrorist die and go to heaven. Each of them
is brought before God separately and is asked whether the bomb has exploded or not.

If at least two terrorists answer rightfully they all go to heaven.
otherwise: hell it is!

Before entering the jail rooms the terrorists are given some time to plan a strategy to
go to heaven, after which they don't see one another and don't communicated.
(i.e each terrorist know only what happened to him after infinite days.)

Can they devise a winning strategy?

Formal Defenition


It is a little boring to convert this problem, but it usually makes problem brighter :

We are given three binary sequences . We know that excluding finitely many n; There are two possibilities:

1.          for all n.
2.          for all n.

Is it possible to find a function   such that

A. If case 1 occurs then at least two of the numbers are 0.

B. If case 2 occurs then at least two of the numbers  are 1 ?

We want to say that if we are terrorist we "see" a sequence of zeros and one

(0 represent a day without show and 1 otherwise) and we see "a lot" of 1s then we should say that the bomb has exploded.

This function exists but how can we prove it mathematically?

To understand it we must know a basic idea from Set Theory:
 Every binary sequence is equivalent to a subset of the natural numbers:

Therefore the first thing for the prisoners to do is to convert the sequence to a subset of the natural numbers.

Theorem:

There exist a function that satisfy to following properties:

A.

B. .

C.

Those two properties remind us the properties of the measure function, but two major differences:

there is no sigma-additivity (only finite sums) and the values are only 0,1.

We can conclude from (A-C) the following  properties:

Properties:

1.

From property (A)  the fact that only 0,1 value are allowed.

2.

3.

4.

( from (1) (from (3) (De-Morgan law)

First we show  how the existence of this function helps the terrorists to go to heaven:

Lets assume that the bomb didn't explode. we can prove that at least two of the terrorist have said no. (the terrorist say no if the function value is 0 on his subset)

since only one of them was electroshock everyday it means that the subset representing

their sequences are mutually disjoint! :

therefore at least two of them must say no!.

Lets assume that the bomb had exploded, them because of property (B) we can assume that is has exploded on the first day. Pick any two of the terrorists.

Every day, at least one of them was electroshock, therefore:

at least one of them must say yes !

because we picked any two terrorists it must mean that at least two of them said yes!

Why such function exists?- Axiom of Choice FTW!

Once again, we think of the function a little differently. We think of it as a collection of subsets of the natural numbers by :

What are the properties of this subset (we can conclude it from properties of the function)

i. (this means it is close to supersets)

ii.

iii.

iv.

Definition: 

A non empty collection of subsets that not contains the empty set satisfying properties i and ii is called filter. If it satisfy property iii as well it is called ultra-filter.

Ultra-filter do exists: for example is an ultra-filter however this

ultra-filter don't satisfy property iv.

Ultra-filters that do satisfy property iv are called non-principal or free ultra-filter, their existence must be assumed or be proven with AC.

Theorem:

Let be an infinite set, then there exist an free ultra-filter on .

Proof:

Every filter is contained in a maximal filter. (Zorn's Lemma)

We show that every maximal filter is an ultrafilter: Denote our maximal filter ; Notice that contains the all set since we can add it to the filter without interfering with the filter propertyies.

Because that it not contains the empty set, we know :

Else it could be shown with property (ii) that it contains the empty set.
Now we prove property (iii); Let us assume that , then because of the maximality :   (because the r.h.s is also a filter)
since contains , . This proves is an ultra-filter.

Now we can define the filter: (it is indeed a filter because is infinite)

This filter is contained in an ultrafilter .

The ultra-filter contains no finite subset - assume is finite, this means because of property iii of the ultra-filters. but which is a contradiction.

Quite remarkable, isn't it?