Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Exercises 8.3 Exercises

🔗

Reasoning in an abstract axiomatic system.

🔗
Exercises 1–5 concern the axiomatic system described in Example 8.1.1.
🔗

1.

🔗
Rewrite each axiom of the system and each subsequent theorem proved in Section 8.1, replacing the words woozle by point, dorple by line, and snarfs by lies on. Come up with a replacement for the terminology snarf buddies that is consistent with these replacement primitive terms. Do the statements make more sense now?
🔗

2.

🔗
Rewrite Theorem 8.1.5 as an “if … then …” statement. Then form the converse of this conditional. Now prove the converse.
🔗

3.

🔗
Prove each of the following statements. In your proofs, you may use as justification any combination of the five axioms in the system, Theorem 8.1.3 and Theorem 8.1.5 already proved in this chapter, and/or any of the statements of this exercise that you have already proved.
🔗
(a)
🔗
There is no dorple who snarfs all woozles.
🔗
(b)
🔗
Each woozle snarfs at least two distinct dorples.
🔗
(c)
🔗
Each dorple belongs to at least two distinct snarf buddy pairs.
🔗
(d)
🔗
There is no woolze who snarfs all dorples.
🔗
(e)
🔗
There is at least one trio of distinct dorples that snarf no woozle in common.
🔗
(f)
🔗
Each woozle belongs to a trio of woozles that snarf no dorple in common.
🔗
(g)
🔗
Every pair of woozles can be increased to a trio of woozles that snarf no dorple in common.
🔗
Note. Statement f and Statement g in Exercise 8.3.3 are indeed different statements and require separate proofs (and each of these statements is different from Axiom 4).
🔗

4.

🔗
Rewrite each statement in Exercise 8.3.3 using the replacement primitive terms point for woozle, line for dorple, and lies on for snarfs. Also replace snarf buddies by whatever terminology you came up with in Exercise 8.3.1.
🔗

5.

🔗
Now consider the system with the revised version of Axiom 1. Prove that there exist exactly three dorples.
Hint.
Start with the first diagram in the proof of Theorem 8.1.3. Now argue by contradiction: what do the axioms say would happen if you added a fourth dorple d4?
🔗

6.

🔗
Consider the following axiomatic system.
🔗

Primitive terms.

🔗
🔗

Axioms.

🔗
  1. 🔗
    There are at least three distinct wizards.
  2. 🔗
    If W1, W2 are distinct wizards, then W1 zaps W2 or W2 zaps W1.
  3. 🔗
    No wizard zaps itself.
  4. 🔗
    If W1, W2, W3 are wizards such that W1 zaps W2 and W2 zaps W3, then W1 zaps W3.
🔗

Notes.

🔗
  • 🔗
    Recall that in mathematics and logic, we always interpret “or” as inclusive or: one or the other or possibly both.
  • 🔗
    In Axiom 2 and Axiom 4, you should treat W1,W2,W3 as variables or placeholders that can be “substituted into”. These axioms are not stating facts about specific wizards; rather, they are stating facts about all wizards, and their relationships to each other through zapping. In particular, Axiom 4 could (in principle) be applied to a collection W1,W2,W3 of wizards where W1 and W3 are in fact the same wizard.
🔗
Prove the following statements based on this axiomatic system.
🔗

(a)

🔗
Principle of Non-Retaliation. If wizard A zaps wizard B, then B does not zap A.
🔗

(b)

🔗
Friends and Enemies Theorem. If A, B, and C are distinct wizards such that A zaps B, then A zaps C or C zaps B.
Hint.
You may wish to refer back to Activity 6.4.
🔗

(c)

🔗
Bully Theorem. Given four distinct wizards, exactly one of the four zaps all of the others.
Hint.
First argue there cannot be more than one of the four that zaps the other three. Then show there is at least one. You may need to consider several cases — draw diagrams to help.)
<Prev^TopNext>