Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Section 8.1 Basics and examples

🔗
Any mathematical system must have a starting point; we cannot create something out of nothing. The starting point of a mathematical system (or any logical system, for that matter) is a collection of basic terminology accompanied by a collection of assumed facts about the things the terminology describes.
🔗
primitive term
🔗
a label for an object or action that is left undefined
axiom
🔗
a statement (usually involving primitive terms or terms defined in terms of primitive terms) that is held to be true without proof
axiomatic system
🔗
a collection of primitive terms and axioms
🔗

Example 8.1.1. An axiomatic system.

🔗

Primitive terms.

🔗
  • 🔗
    woozle (noun),
  • 🔗
    dorple (noun),
  • 🔗
    snarf (verb).
🔗

Axioms.

🔗
  1. 🔗
    There exist at least three distinct woozles.
  2. 🔗
    A woozle snarfs a dorple if and only if the dorple snarfs the woozle.
  3. 🔗
    Each pair of distinct woozles snarfs exactly one dorple in common.
  4. 🔗
    There is at least one trio of distinct woozles that snarf no dorple in common.
  5. 🔗
    Each dorple is snarfed by at least two distinct woozles.
🔗

Remark 8.1.2.

🔗
In the axiomatic system of Axiom 8.1.1, Axiom 1 is redundant as we may infer from Axiom 4 that there exist three distinct woozles. But there is no harm in including this axiom for clarity. As well, we will later investigate the effect of altering it.
🔗
The axiomatic system of Example 8.1.1 seems like nonsense, but we can actually prove things from it.
(In this proof, all references to axioms refer to the axioms of Example 8.1.1.)
By Axiom 4, there exists a trio w1,w2,w3 of distinct woozles that snarf no dorple in common. Breaking this trio into various pairs and applying Axiom 3, we see that there exists a dorple d1 that w1 and w2 both snarf in common, there also exists a dorple d2 that w1 and w3 both snarf in common, and there also exists a dorple d3 that w2 and w3 both snarf in common. These snarfing relationships are illustrated in the diagram below.
A diagram of woozles snarfing dorples.
Now, suppose d1 and d2 were actually the same dorple — then all three woozles would snarf it in common.
A diagram of woozles snarfing dorples, assuming two of the dorples coincide.
As this would contradict our initial assumption, it must be the case that d1 and d2 are distinct. Similar arguments allow us to also conclude that d1≠d3 and d2≠d3.
🔗
It is often useful to give names to important properties of objects.
🔗
defined term
🔗
a label for an object or action that is defined in terms of primitive terms, axioms, and/or other defined terms
definition
🔗
an formal explanation of the meaning of a defined term
🔗

Example 8.1.4. Making a definition.

🔗
🔗
Here is a definition relative to the axiomatic system of Example 8.1.1.
snarf buddies
🔗
two distinct dorples that snarf a common woozle
🔗
A definition allows us to more succinctly communicate ideas and facts about the objects of an axiomatic system.
Suppose d1,d2 are snarf buddies. By contradiction, suppose they snarf more than one woozle in common: let w1,w2 be distinct woozles both snarfed by d1 and d2. By Axiom 2, each of w1,w2 snarfs each of d1,d2. But this contradicts Axiom 3, as two distinct woozles cannot snarf more than one dorple in common.
🔗
🔗
Suppose we replace Axiom 1 in the system of Example 8.1.1 with the following.
  1. 🔗
    There exist exactly three distinct woozles.
🔗
In the new, modified axiomatic system, our previous two theorems (Theorem 8.1.3 and Theorem 8.1.5) remain true, because it is still true that there exist at least three distinct woozles. But we can now also prove the following.
You are asked to prove this in the exercises.
🔗
A nonsense system like the one in Example 8.1.1 is just that — nonsense — and not much use unless there are actual examples to which the developed theory can be applied.
model
🔗
a system obtained by replacing the primitive terms in an axiomatic system with more “concrete” terms in such a way that all the axioms are true statements about the new terms
🔗
If we agree that the axiom statements are still all true with the new terms, then any theorems proved under the abstract system are still valid in the new model system.
🔗

Example 8.1.7. A model for the woozel-dorple system.

🔗
Again consider the axiomatic system of Example 8.1.1, still using the modified version of Axiom 1. Let the three distinct woozles be the points (0,0), (1,1), and (2,0) in the Cartesian plane. Let dorple now mean line in the plane, and let snarf now mean lies on. Convince yourself that the axioms of the system are all true with this interpretation of the primitive terms.
🔗
Theorem 8.1.6 now says that there exist exactly three distinct lines in the plane which fit into our axiomatic system; can you find their equations?
A diagram of woozles snarfing dorples.
🔗

Remark 8.1.8.

🔗
Using nonsense terms like woozle, dorple, and snarf for the primitive terms in an axiomatic system is usually not a good idea, as it takes all intuition out of the process of discovering statements that can be deduced from the axioms. It would have been much better if we had used the words point instead of woozle, line instead of dorple, and lies on instead of snarfs as our primitive terms, to be able to use our intuition about how such objects interact. In such a case, the axioms we choose should be a reflection of our idea of the simplest possible properties about the primitive terms, properties that everyone could reasonably agree are “true” without proof. However, for the theorems deduced from such an axiomatic system to have the widest possible applicability, we should leave the words point and line as truly primitive, undefined terms — that is, point and line should not be taken to mean point in the plane and line in the plane, as in the example above, but rather just left as some abstract, intuitive idea of point and line.
<Prev^TopNext>