The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Solving Axiom Systems

Date: 02/11/2003 at 12:59:08
From: Jen
Subject: Solving axiom systems

Axiom 1. Any two distinct students belong to exactly two clubs in 
Axiom 2. There exist at least two students.
Axiom 3. For each club, there exists at most one student who doesn't 
         belong to it.
Axiom 4. Each student belongs to exactly four clubs.

Theorem 1. There exist exactly six clubs.
Theorem 2. At least one student belongs to each club.
Theorem 3. For each student, there exist exactly two clubs to which 
he does not belong.

I have to prove the theorems with the axioms and I have no idea how 
to do it.

Date: 02/16/2003 at 05:32:37
From: Doctor Jacques
Subject: Re: Solving axiom systems

Hi Jen,

We will prove theorem 1 in two steps:

Lemma 1.1 : there are at least 6 clubs

By A.2, there are at least two students. The first student is a member 
of 4 clubs (A.4). By A.1, the second student is a member of exactly 
two of these clubs. As he is a member of 4 clubs (A.2), there must be 
at least two other clubs.

Lemma 1.2 : there are at most 6 clubs.

Assume by contradiction that there are at least 7 clubs. Pick one 
student (A.2 allows this), and call it "a".

Number the clubs from 1 to n (n >= 7), in such a way that "a" is a 
member of clubs 1 through 4 and no other club (A.4).

As "a" is not a member of clubs 5, 6, and 7, every student other than 
"a" (there is at least one such student, by A.2) is a member of these 
clubs (A.3). Each of these other students must share two clubs with 
"a" (A.1), and thus be a member of two clubs in the set {1..4}. This 
makes each such student a member of at least 5 clubs, which 
contradicts A.4

Theorem 1 follows then from these two lemmas.

Theorem 2 is a consequence of A.2 and A.3 - I'll let you show that.

Theorem 3 follows immediately from Theorem 1 and A.4 - I'll let you 
show it too.

Extra credit

Can you show that there are at most three students ?

A possible course of attack would be:

Assume that there are s students. Make a rectangular (s*6) table, 
where rows correspond to students and columns correspond to clubs. Put 
a mark in each square for which the student belongs to the club, and 
estimate the number of marks in two different ways (by row first or by 
column first).

Does this help?  Write back if you'd like to talk about this some 
more, or if you have any other questions.

- Doctor Jacques, The Math Forum 
Associated Topics:
High School Logic

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.