Logic Axioms

Quiz 5: Axiom Proofs

Name:

“The way I see it every life is a pile of good things and bad things. The good things don’t always soften the bad things, but vice-versa, the bad things don’t necessarily spoil the good things or make

them unimportant.” Dr. Who

Axiom 1: There exists at least one doctor

Axiom 2: Each doctor travels with exactly two companions

Axiom 3: Every pair of companions travels with one common doctor

Axiom 4: For each doctor, there are exactly two companions that do not travel with him.

Primitive Terms: Companion, doctor, travels

1. (4 points) For every pair of companions, there is at least one doctor that does not travel with them.

Solution: Let c1 and c2 be an arbitrary pair of companions. By Axiom 3, c1 and c2 travel with a common doctor d1. Now by Axiom 4, there are two companions c3 and c4 that do not travel with d1. These cannot be c1 and c2, since d1 travels with them. By Axiom 3, c3 and c4 must travel with a common doctor d2. So we see for c1 and c2 there is a doctor d2 that does not travel with them.

“You know that in 900 years in time and space I’ve never met anyone who wasn’t important before.” Dr. Who

Axiom 1: There exists at least one doctor

Axiom 2: Each doctor travels with exactly two companions

Axiom 3: Every pair of companions travels with one common doctor

Axiom 4: For each doctor, there are exactly two companions that do not travel with him.

Primitive Terms: Companion, doctor, travels

2. (6 points) There are exactly 6 doctors.

Solution: By Axiom 1, there exists at least one doctor, say d1. By Axiom 2, d1 must travel with two companions, c1 and c2. By Axiom 4, there are exactly two companions that do not travel with d1, say c3 and c4. By Axiom 3, c3 and c4 must travel with one common doctor, say d2. Now by Axiom 3, c1 and c3 must travel with a common doctor. This doctor cannot be d1 or d2 else a doctor would travel with more than two companions, violating Axiom 2. So c1 and c3 travel with d3. Likewise there must be a distinct doctor for each pair of companions. Since there are six pairs of companions, we have d4, d5, and d6. So there are at least six doctors.

Suppose there is a seventh doctor d7. By Axiom 2, d7 must travel with two companions. He cannot travel with two of c1, c2, c3 or c4, else Axiom 3 be violated for some pair of companions.

Case 1: Suppose d7 travels with c5 and one of c1, c2, c3 or c4. Without loss of generality, suppose it is c1. Then d7 does not travel with c2, c3 or c4 violating Axiom 4. So d7 cannot travel with c1 and c5.

Case 2: Suppose d7 travels with c5 and c6. Then d7 does not travel with c1, c2, c3 or c4 contradicting Axiom 4. So d7 cannot travel with c5 and c6

Since those are all possible cases d7 can travel with, d7 cannot travel with two companions, contradicting Axiom 4. So d7 cannot exists. Thus there are exactly six doctors.