## Can you solve the prisoner hat riddle?

You and nine other individuals have been captured by super-intelligent alien overlords. The aliens think humans look quite tasty, but their civilization forbids eating highly logical and cooperative beings. Unfortunately, they’re not sure whether you qualify, so they decide to give you all a test. Can you solve this hat riddle? Alex Gendler shows how.

## Three Logic Problems

Here are three challenging logic problems to try out. Good luck!

## The Burning Island Puzzle

A man is stranded on an island covered in forest.

One day, when the wind is blowing from the west, lightning strikes the west end of the island and sets fire to the forest. The fire is very violent, burning everything in its path, and without intervention the fire will burn the whole island, killing the man in the process.

There are cliffs around the island, so he cannot jump off.

How can the man survive the fire? (There are no buckets or any other means to put out the fire).

## The Black And White Hats Problem

Cannibals ambush a safari in the jungle and capture three men. The cannibals give the men a single chance to escape uneaten.

The captives are lined up in order of height, and are tied to stakes. The man in the rear can see the backs of his two friends, the man in the middle can see the back of the man in front, and the man in front cannot see anyone. The cannibals show the men five hats. Three of the hats are black and two of the hats are white.

Blindfolds are then placed over each man’s eyes and a hat is placed on each man’s head. The two hats left over are hidden. The blindfolds are then removed and it is said to the men that if one of them can guess what color hat he is wearing they can all leave unharmed.

The man in the rear who can see both of his friends’ hats but not his own says, “I don’t know”. The middle man who can see the hat of the man in front, but not his own says, “I don’t know”. The front man who cannot see ANYBODY’S hat says, “I know!”

How did he know the color of his hat and what color was it?

## The 5 Pirates Puzzle

5 pirates of different ages have a treasure of 100 gold coins.

On their ship, they decide to split the coins using this scheme:

The oldest pirate proposes how to share the coins, and ALL pirates (including the oldest) vote for or against it.

If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.

As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard.

Assuming that all 5 pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen?

## Peano’s Postulates

The Natural Numbers,  = {1, 2, 3, …}, can be built from five basic axioms, as follows:

1.  There is a natural number 1; that is, 1 ∈ .

2.  If n ∈ , then there is another number called the successor of n and written as S(n) that is also a natural number; that is:  n ∈   S(n) ∈ .

3.  Two different numbers have different successors; that is:  m  n  S(m)  S(n).

4.  Every natural number but 1 is the successor of some (other) number; that is:

n ∈ , n  1 m ∈  S(m) = n.

5.  The Principle of Mathematical Induction:  All natural numbers are formed in this way—either 1, or a successor.  More formally,

If there is a subset S of natural numbers such that 1 ∈ S and n ∈ S  S(n) ∈ S, then S is the set of Natural Numbers, that is S = .

Define addition:  n + 1 = S(n).

Can prove addition follows commutative and associative laws.

Define subtraction to be S(n) – 1 = n.

## Algebraic Structures — Field

Mathematics does not deal so much in numbers, but in “mathematical structures.”  These are basically abstract concepts that fit together according to certain rules or patterns.

One abstract concept that is very important is that called a Set.  A set in mathematics is a very abstract concept, but unless we are involved in higher mathematics, a set is something very similar to what we call a “collection” in everyday English.  Since we are not involved in higher math in this course, we will consider a set to be a collection of some objects (often numbers, but it could be a collection of other things, such as functions, triangles, etc.).  Many books will define a set to be a collection.  This definition is not correct, so as a matter of honesty, we point to that it is not correct.  However, the differences between a set and a collection are so subtle and abstract, we need get involved, but will consider a set to be a collection.

Another important concept is that of an operation—it means a process where some members of a set are combined together to get something new, like mixing flour and water to get dough.  In mathematics, in dealing with numbers, the most common operations are addition, subtraction, multiplication, and division.  There are others, of course, but we need not be concerned with them.  In dealing with functions, the most important operations are there are these four and a FIFTH operation that is important, called composition.  We studied it in class–f◦g means f(g(x)).

An operation is called binary, if, by definition we must always combine exactly two things together.  All the above operations are binary.  Note we cannot combine three numbers with addition together, for example, we cannot add 2+3+4 all at once.  We must first add only two numbers together, get a temporary answer, and then we add the third number to this temporary answer.  This means the operation is binary—we can only deal with two at a time, although we can keep adding more numbers to our answer after we get it.

An operation is called unique, if, unlike tossing a pair of dice, for example, combining the same two inputs always produces the same output.

1. The sum of any two real numbers a and b is a real number written a+b

This is called the Law of Closure for addition of Real numbers.

2. For all real numbers a, b, c:  (a+b)+c=a+(b+c)

This is called the Associative Law for addition of Real numbers.

3. There is a one unique real number called zero, written 0, such that a+0 = a and 0+a = a  for all real a.  (Note both parts are needed because Rule 5 does not necessarily hold in all systems.)   That is to say, that there is one and only one real number that can be used for I to make the following two equations come true:  For any Real number, a, a+I = a and I+a = a  for all real a.  (And of course, I is 0).

This is called the Additive Identity Law for addition of Real numbers.

4. For each real number a there is a real number called –a such that a+(-a)=0 and

(-a)+a = 0.  (Note both parts are needed because Rule 5 does not necessarily hold in all systems.)

This is called the Inverse Law for addition of Real numbers.

5. a+b=b+a

This is called the Commutative Law for the addition of Real numbers.

Rules for multiplication:

1. The product of any two real numbers is a real number written ab or ab

2. For all real numbers a, b, c:  (ab) c=a (bc)

3. There is a real number called one, written 1, such that a1=a and 1a=a for all real a.  (Note both parts are needed because Rule 5 does not necessarily hold in all systems).

4. For each real number a0,  there is a real number called 1/a such that
a (1/a)=1 and (1/a) a= 1.   1/a is also written as a-1.  (Note both parts are needed because Rule 5 does not necessarily hold in all systems.)

5. ab=ba

Rule 11 connecting addition and multiplication:

a(b+c)=ab+ac

Rule 1 is called the Law of Closure.

Rule 2 is called the Associative Law.

Rule 3 is called the Identity Law.

Rule 4 is called the Inverse Law.

Rule 5 is called the Commutative Law.

Rule 11 is called the Distributive Law.  (Adding columns and rows—switching order.)

Note:

1.  Rule 2 does not make sense unless Rule 1 is first established.

2.  Rule 4 does not make sense unless Rule 3 is first established.

3.  If a system has just one binary operation and the first four laws, it is called a “Group.”  Since Rule 5 is not necessarily true in an arbitrary group, it is necessary to state the identity and inverse laws on both sides.

4.  If a system has just one binary operation and the first five laws, it is called a Commutative Group or an Abelian Group.

5.  If a system has rule 2 and 5, then the General Associative Law is true, which says you can change the order and the parentheses any way you want.

6.  If a system has two binary operations and all 11 laws, then it is called a field.

You should be able to state these rules in the abstract—If S is a set, and if a, b, and c are any arbitrary members of S, and if * is a unique binary operation defined for the members of S, then (commutative law, for example, would be a*b = b*a.

Now some results or consequences of these rules:

1.  If a+c=a+b then b=c.  (This will be true in any group that has + as an operation.)

2.  If ab=ac, then b=c, providing a0  (This will be true in any group that has multiplication as an operation.)

3.  These laws enable us, if we are in a field,  to solve any equation of the following forms:

a+ x=b,

x+a=b,

ax=b (provided a0),

xa=b (provided a0), and

ax + b = c

4.  a0=0  for any Real number a.

5.  ab = 0 means a = 0 or b = o or both.

6.  The zero principle:  In a field, ab = 0if and only ifa = 0 or b = 0 or both.

This is a consequence of #4 and #5 above.  We needed all 11 laws (except for the commutative laws) to prove #3 and #4, so we see the zero principle will always hold in a field, but not necessarily in a group.

5 – 7

7.  (a)  b = (ab)  (Henceforth, we will omit the  for multiply, or use a dot instead.)

All the above represent the basic algebraic properties of a field.  There are many fields besides the real numbers.  Some are finite  and some are infinite, such as , , and –and there are many other examples of both finite and infinite fields not mentioned.  Any system that is a group will look a lot like our number system, , the real numbers.  However, any field will look even more like .

To characterize the Real Numbers mathematically, we need to say it is an infinite field with the following additional properties—these additional properties, however, are generally not considered “algebraic” properties, but “geometric” properties:

It is infinite, ordered, Archimedian, and complete.  These three properties are explained briefly below, but you are not responsible for them.

Ordered means given any two different numbers, then one is greater than the other (or equivalently, one is smaller than the other).

Archimedian means that given any small number, s, regardless of how small, and a big number, b, regardless of how big, then it is possible to add enough s’s together so that eventually the sum  s + s + … + s > b.  In other words there is a number n, so that ns > b.  For example, is s is 1/100 and b is 1,000,000 we can keep adding 1/100 + 1/100 etc. until eventually the sum is bigger than 1,000,000.  Equivalently, if n is any number larger than 100,000,000 then ns > b.

What is Russell’s Paradox?  What is the solution to it?

Background (you will need to know to understand the answer):

Russell’s Paradox arises when sets get “too big” and sets contain sets.  It is possible for sets to contain sets, but not all such combinations are acceptable.  We will now explain how the idea of a “set containing a set” can be problematic.

To start, first notice that many sets, even if they are infinite in size, can generally be expressed in English sentences containing a few words.  For example, “The set of all even numbers” is a sentence describing an infinite set—the even numbers—and the description should be very clear to anyone, even someone in the second grade.  Yet this description only takes six words!  (Side point:  In general mathematicians like to be very terse, and the brevity of mathematical statements can confuse people who are not used to paying attention to the detail and exact meaning of every word—an absolute necessity in mathematics.)  In spite of the tendency towards terseness, there are some sets that might take many words to describe, for example, consider this set:  “Let K = the set of all people who (1) were born in New York, (2) have red hair, (3) moved to California after age 10, (4) drive a Ford, (5) did not graduate college, (6) like to follow football games on television, (7) like Big Macs, (8) own a computer, etc. “  If we were to list 100 different conditions, even using terse wording, the description would certainly be over 100 words long.  Of course, it could be there is no person on earth who meets all 100 conditions, especially if some of them are rare, such as (over 6 feet 5 finches tall).  While that one condition might be met by some people, the number of people meeting this condition might be relatively small, so it could be there is no one who meets all 100 conditions.  If this is the case, then K, the set described is the empty set, but we would not know that without a survey unless we created a ridiculous condition, such as the person must be over 10 feet tall.  In short, this set could very well not be the empty set, but the description could be very long—over 100 words.

Now let H be the set of all sets that can be described in an English sentence containing less than 100 words.  By definition, the elements of H are themselves sets.  Clearly, the set K described above is not inside of H, because its description is too long.  However, all other sets mentioned above are sets that are inside of H—as well as many other sets, such as the set of real numbers, the set of rational numbers, the set of all people on earth, etc.  These sets are infinite, but their descriptions are short, so they are all inside of H.  In fact, the set H is also inside of H because the description of H above contained 17 words (which is certainly less than 100).  Thus we have something like the following H ={H, N, Z, Q, S, T, ….}  H is in fact a member of H!  This concept is counter-intuitive, because if we think a set as a collection, a collection cannot obviously contain itself.  So while it is nice to think of a set as a collection, the analogy breaks down when we deal with more complicated examples, as is so in this case.

The Answer as it Should Appear on a Test:

Now, here is Russell’s Paradox.  All the sets we have above, or “standard” sets, such as whole numbers, natural numbers, integers, etc. we will call “ordinary” sets.  However, any set, such as H, which contains itself, we will call an “extra-ordinary” set.

Let Obe the set of all ordinary sets.  Question:  Is O  ordinary or extra-ordinary?  We will find we have a problem (contradiction) or paradox, either way we look at it.  If O  is ordinary, then since O  contains all ordinary sets (by its very definition) then it must contain itself (since it is ordinary)—and by containing itself it would then become extra-ordinary—a contradiction!  Again, if O is extra-ordinary, then O  must contain itself, by the definition of the word “extra-ordinary.”  But this fact contradicts the definition of O , since O is supposed to contain only ordinary sets, not an extra-ordinary ones!  So as a result, we cannot decide whether O is ordinary or extra-ordinary.

What is the solution to Russell’s Paradox?

The solution to this paradox, is to redefine or rethink what we mean by sets.  They are not simply any collections, but they must be limited so they do not grow too big.  There are several ways to achieve this re-definition—but most are too sophisticated to explain here.  We will explain, briefly (not in detail) the simplest method here.

We start by defining some set, which we call U, the universal set.  U could be the real numbers, natural numbers, or any other set you want it to be.  However, we cannot just create “new” sets at random.  They must be formed by certain rules—for example, by taking elements from U, by taking subsets from U, or by taking unions or intersections, or complements of these sets.  So while we can make an infinite number of sets, and we can even create a set of subsets, we can’t create “higher levels” of sets containing sets, so we stay clear of this paradox.

Questions:  Let S be the set of all sets.  Does S exist?

Answer:  No.  It is too big.  The solution to Russell’s Paradox sets limits as to how big a set can get—and S violates those limits.  We need to have some “upper” set such as the real numbers, and all other sets are subsets of this upper set or universal set.

## Basic Definitions and Concepts

Philosophically and educationally there are a number of ways to introduce and teach mathematical ideas.  Most mathematicians, however, prefer to use Sets as the basic structure in math, and build all ideas from there, using sets to define everything.

At first, mathematicians used to look at sets as just collections of things, but Bertrand Russell, the famous British philosopher and logician, showed that viewing sets as collections is a bit naïve—if a set gets “too big” it is possible that contradictions will result.  Before we discuss what the problem is, we will use this simple or “naïve” view of sets and consider a set just to be a collection of things.

SETS

Here are some important ideas about sets:

1.  In describing sets we often use the word “all” or “only.”  Even if we use only one of those two words, or neither of them, we ALWAYS mean both.  For example, if we talk about the set of all positive even numbers less than 10 we mean the set {2, 4, 6, 8}.  (Notice, we generally put the members or elements of a set between two curly-cue brackets, and we put commas between the different members.)  This set, {2, 4, 6, 8}, is both ALL the positive even numbers less than 10 and ONLY the even numbers less than 10.   If we only say “the set of positive even numbers less than 10” and omit the word “all” we still mean this set.  If we say “the set of only positive even numbers less than 10,” we still mean this set.

2.   Repeating an item in a set, or changing the order does not change the set.   For example, the sets {2, 2, 4, 4, 4, 6, 8} and {8, 4, 6, 2} and {2, 8, 4, 6, 8} are all equal to each other and the set mentioned in the previous paragraph.

3.   There does not have to be any connection between items in the set or uniformity.  For example, we can form a set that consists of all red Cadillac’s, Mexican immigrants, and stars that are less than 100 light years from the sun.

4.  The things inside a set are called members or elements of the set.  And there is a special symbol to so indicate:  For example, we can write 2∈{2, 4, 6, 8} to mean that “two is a member of the set of all positive numbers less than 10.”   We can also indicate something is not a member of the set by using the same symbol with a line through it.  For example, 3∉ {2, 4, 6, 8}.

5.  We can also talk about one set being inside another set—that is to say, if every member of one set is inside another set, we use this symbol:⊂ .  For example,

{2, 8}⊂ {2, 4, 6, 8}.  This may be read as “The set {2, 8}is contained in (or inside of) the set {2, 4, 6, 8}.”  The set {2, 8} is called a subset of the set {2, 4, 6, 8}.  Therefore, we can also read the above expression as “The set {2, 8}is a subset of the set {2, 4, 6, 8}.”

6.  There are two types of subsets—proper and improper.  If someone starts with a set and “removes” some elements and “keeps” some elements, then the result is a proper subset.  For example, if the starting set is {2, 4, 6, 8} and one “keeps” 2 and 8 and “removes” 4 and 6, then what we have left is a proper subset, namely, {2, 8}.  It is possible, though, to “keep” everything and “remove” nothing.  In this case the “subset” is the full set,

{2, 4, 6, 8}.  This full set, when thought of as a subset is called an improper subset.  Similarly, one can “keep” nothing and “remove” everything, in which case the subset, is empty or has nothing in it.  It is written as {} (empty brackets) or as .  It is also called an improper subset, and called “the empty set.”  If we want set A to be a subset of set B, and we allow that A could be all of B or the empty set—that is A could be a proper or improper subset–we write A  B.  If we do not want to allow the possibility that A could be all of B (but we still allow the possibility that A could be the empty set) we write

A  B.  If we want A to be a subset of B but we do not want to allow the possibility that A could be empty, there is no special symbol for that—we just add a sentence that “A is not empty.”

7.  There is a difference whether we write 2∈{2, 4, 6, 8} or {2}⊂{2, 4, 6, 8}, even though they basically mean the same thing.  2 without any set brackets is just the number 2, and it is an element of the set.  {2} is an entire set.  You can look at is as being the number 2 put inside a basket or fancy package.   This mathematical statement “{2}⊂{2, 4, 6, 8}” says everything in the “basket” on the left is also inside the basket on the right—even though the basket on the left has only one item.  However, this statement “2∈{2, 4, 6, 8}” is not talking about two baskets.  It talks about one basket only.  It merely says the number 2 is a member of, or an item in, the “basket” on the right.

8.  A set can contain a set, but if we are not careful, we can get into trouble (Russell’s Paradox).  Here is an example of how a set can contain a set, without getting into trouble.

If we call S = {2, 4, 6, 8}, we can create a set T = {S, 1, 2, 3, 4}.  How many members are there in T?  There are 5.  One of them is a “basket” which contains 4 items—namely the set S.  But T only has 5 items in it, not 9, and not 7.  Note that we can write

{2, 4, 6, 8} ∈ T just like we can write {1}∈ T or {2}∈ T, because the set S is a member, not a subset.  Note that because 2 is in both S and T we can write 2∈ S and we can also write 2∈T (because 2 is also a member of T—a fact totally independent of whether or not S is also a member of T).  Similarly with 4 which is both a member of S and of T.  However, with 6, we can write 6 ∈ S, but we cannot also write 6∈T, because 6 is not a member of T.  Now we can also write 2∈ S ∈ T, which means “the element, 2, is a member of set S, and the set S is a member of the set T.”  Note that this last statement does not say whether or not 2 is in T.  It merely says that 2 is in S, and that S is in T.  Similarly, we can write 6 ∈ S ∈ T, which means that 6 is in S and that S is in T.  It does not say whether 6 is in T or not.  Be sure to spend the time necessary to understand carefully and exactly each of the examples just mentioned in this paragraph before going on.  Do not skim, and do not just read it.  Understand it slowly and carefully in detail.

9.  Now we will explain how the idea of a “set containing a set” can be problematic.

To start, first notice that many sets, even if they are infinite in size, can generally be expressed in English sentences containing a few words.  For example, “The set of all even numbers” is a sentence describing an infinite set—the even numbers—and the description should be very clear to anyone, even someone in the second grade.  Yet this description only takes six words!  (Side point:  In general mathematicians like to be very terse, and the brevity of mathematical statements can confuse people who are not used to paying attention to the detail and exact meaning of every word—an absolute necessity in mathematics.)  In spite of the tendency towards terseness, there are some sets that might take many words to describe, for example, consider this set:  “Let K = the set of all people who (1) were born in New York, (2) have red hair, (3) moved to California after age 10, (4) drive a Ford, (5) did not graduate college, (6) like to follow football games on television, (7) like Big Macs, (8) own a computer, etc. “  If I were to list 100 different conditions, even using terse wording, the description would certainly be over 100 words long.  Of course, it could be there is no person on earth who meets all 100 conditions, especially if some of them are rare, such as (over 6 feet 5 finches tall).  While that one condition might be met by some people, the number of people meeting this condition might be relatively small, so it could be there is no one who meets all 100 conditions.  If this is the case, then K, the set described is the empty set, but we would not know that without a survey unless we created a ridiculous condition, such as the person must be over 10 feet tall.  In short, this set could very well not be the empty set, but the description could be very long—over 100 words.

Now let H be the set of all sets that can be described in an English sentence containing less than 100 words.  By definition, the elements of H are themselves sets.  Clearly, the set K described above is not inside of H, because its description is too long.  However, all other sets mentioned above are sets that are inside of H—as well as many other sets, such as the set of real numbers, the set of rational numbers, the set of all people on earth, etc.  These sets are infinite, but their descriptions are short, so they are all inside of H.  In fact, the set H is also inside of H because the description of H above contained 17 words (which is certainly less than 100).  Thus we have something like the following H ={H, N, Z, Q, S, T, ….}  H is in fact a member of H!  This concept is counter-intuitive, because if we think a set as a collection, a collection cannot obviously contain itself.  So while it is nice to think of a set as a collection, the analogy breaks down when we deal with more complicated examples, as is so in this case.

Now, here is Russell’s Paradox.  All the sets we have above, or “standard” sets, such as whole numbers, natural numbers, integers, etc. we will call “ordinary” sets.  However, any set, such as H, which contains itself, we will call an “extra-ordinary” set.

Let Obe the set of all ordinary sets.  Question:  Is O  ordinary or extra-ordinary?  We will find we have a problem (contradiction) or paradox, either way we look at it.  If O  is ordinary, then since O  contains all ordinary sets (by its very definition) then it must contain itself (since it is ordinary)—and by containing itself it would then become extra-ordinary—a contradiction!  Again, if O is extra-ordinary, then O  must contain itself, by the definition of the word “extra-ordinary.” But this fact contradicts the definition of O , since O is supposed to contain only ordinary sets, not an extra-ordinary ones! So as a result, we cannot decide whether O is ordinary or extra-ordinary.

The solution to this paradox, is to redefine or rethink what we mean by sets.  They are not simply any collections, but they must be limited so they do not grow too big.  There are several ways to achieve this re-definition—but most are too sophisticated to explain here.  We will explain, briefly (not in detail) the simplest method here.

We start by defining some set, which we call U, the universal set.  U could be the real numbers, natural numbers, or any other set you want it to be.  However, we cannot just create “new” sets at random.  They must be formed by certain rules—for example, by taking elements from U, by taking subsets from U, or by taking unions or intersections, or complements of these sets.  So while we can make an infinite number of sets, and we can even create a set of subsets, we can’t create “higher levels” of sets containing sets, so we stay clear of this paradox.

## Abstract Thinking

What is abstract thinking, and why is it important in mathematics?   Name at least three advantages.

Let us start with an example:  If there are two rooms, room A and room B that are connected by a door, and a person starts in room A, but changes room every time a bell rings, then what room will the person be in if the bell rings three times?  256 times?  Most people get the answer to the first question by moving their finger three times and correctly conclude the person will be in room B.  Sometimes a person does not move a finger but mentally pictures the person going back and forth.  While this mental picturing is an example of abstract thinking, it only represents one level of abstraction that corresponds closely with a physical operation (going back and forth).  Other levels of abstraction exist.  Most people do not attempt to answer the question of “256 times” by going back and forth physically or mentally.  They rely on an additional layer of abstraction.  They realize that an odd number of rings of the bell puts the person in room B, and an even number of rings puts the person in room A.  Abstract thinking is an objective mental process whereby concepts rather than motion or physical objects or activity (or a mental picture thereof) are used to come to a conclusion.  There are many additional layers of abstraction used by mathematicians.

Abstract thinking is generally quicker than more concrete methods.  It also creates a deeper level of understanding.  Hence, it enables one to understand the essence of problem and from the principles involved, thereby, solve other problems similar to the original.  In addition, use of abstract thinking helps to “objectify” a problem and helps eliminate red-lining.