Logic Axioms
Learning Activity: Axiom System II
Name:
Primitive Terms: elements, set, contains
Axiom 1: There exists at least one set.
Axiom 2: For each element, there exists exactly one other element such that no set contains both.
Axiom 3: Each set contains exactly two elements.
Axiom 4: Each element is contained in exactly four sets.
Prove Theorem 1: There exist at least eight sets.
Solution:
Proof. By Axiom 1, there exists a set, we can call it s1. By Axiom 3, this set must contain exactly two elements. So it contains some element e1. Now Axiom 4 tells us each element is contained in exactly four set. Thus e1 is contained in three other sets, say s2, s3, and s4. By Axiom 2, there must be some other element e2 such that e2 is not in sets s1, s2, s3 or s4. But by Axiom 4, this element must be in sets s5, s6, s7, s8. So we have shown there are at least eight sets, s1 . . . s8.
Primitive Terms: elements, set, contains
Axiom 1: There exists at least one set.
Axiom 2: For each element, there exists exactly one other element such that no set contains both.
Axiom 3: Each set contains exactly two elements.
Axiom 4: Each element is contained in exactly four sets.
Prove Theorem 2: There exist at least four elements.
Solution:
Proof. By Axiom 1 there exists at least one set, we can call it s1. By Axiom 3, this set must contain exactly two elements, say e1 and e2. Now by Axiom 2, there must be some element e3, such that no set contains e1 and e3. Similarly by Axiom 2, there must be some element e4, such that no set contains e2 and e4. Now e3 and e4 must be different otherwise e4 would have two elements, e1 and e2 that have no sets in common, violating Axiom 2. Thus we have found at least four elements, e1, . . . e4.
Primitive Terms: elements, set, contains
Consider the Axioms:
Axiom 1: There exists at least one set.
Axiom 2: For each element, there exists exactly one other element such that no set contains both.
Axiom 3: Each set contains exactly two elements.
Axiom 4: Each element is contained in exactly four sets.
Prove Theorem 3: For each set, there exist at least two elements not contained in it.
Solution:
Proof. Let s1 be an arbitrary set. By Axiom 3, s1 contains two elements, say e1 and e2. Now by Theorem 2, there exists at least two more elements, e3 and e4. Now e3 and e4 cannot be contained in s1, else Axiom 3 would be violated. Thus there are at least two elements not contained in s1. Since s1 was arbitrary, the theorem holds for all sets.
OR
Proof. Let s1 be a set. By Axiom 3, this set contains two elements, say e1 and e2. By Axiom 2, there is exactly one other element, such that there is no set containing it and e1. Since e1 and e2 are both in set s1, this element cannot be e2, we can call it e3. Likewise by Axiom 2, there is exactly one one other element such that there is no set containing it and e2. Since e1 and e2 are contained in s1, that element cannot be e1. It cannot be e3, since e1 and e3 do not share a set. So if e2 and e3 did not share a set, it would violate Axiom 2. Thus this element is some other element, say e4.
We have now found two elements, e3 and e4 that are not contained in s1. Since s1 was an arbitrary set, the theorem holds for all sets.