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
common.
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

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).

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search