1

I am working on a proof puzzle about beads and wires. We are given 4 axioms about the objects you can create with beads and wires.

  • Axiom 1. You must have exactly 3 beads.
  • Axiom 2. There is exactly one wire between each pair of beads.
  • Axiom 3. Not all beads can be on the same wire.
  • Axiom 4. Any pair of wires has at least one bead in common.

We are asked to prove the following theorem:

Theorem. No bead can be on all wires for all possible bead-wire models.

I am new to proofs and have only had some experience doing simple proofs based on real numbers. Therefore, I am having issues on how to rigorously use these axioms about beads and wires in a way of proving the theorem.

So far, I can see that if one bead is on all wires, that if you follow Axiom 2 and Axiom 4 that you would need more that 4 beads if you don’t have all beads on one wire (contradicting Axiom 1).

I am just having issues of how to rigorously represent these objects and make that into a proof instead of just a visual intuition.

Any help with how to get started would be much appreciated!

Blue
  • 75,673
qmild
  • 51
  • I don't know whether it is your transcription or the original problem, but the statement of the theorem seems not (or at least not clearly) what is meant. It should be "For all possible bead–wire models, no bead can be on all wires" ($\forall\text{model $M$},\exists\text{bead $b$},\ \lnot(\text{$b$ is on all wires in model $M$})$); what you have written, "No bead can be on all wires for all possible bead–wire models", can at least plausibly be read as $\lnot(\exists\text{bead $b$},\ \forall\text{model $M$},\ \text{$b$ is on all wires in model $M$})$, which is disproven just by finding an $M$. – LSpice Oct 15 '19 at 19:41
  • Ha, in my nitpicking comment I (inevitably) made my own error; the first statement "$\forall\text{model $M$},, \exists\text{bead $b$},, \lnot(\text{$b$ is on all wires in model $M$})$" should have been "$\forall\text{model $M$},, \lnot(\exists\text{bead $b$},\ \text{$b$ is on all wires in model $M$})$". – LSpice Oct 15 '19 at 19:49

2 Answers2

1

Sketch:

Label the beads $B_1,B_2,B_3$ and suppose that $B_1$ was on all the wires, we will derive a contradiction.

Let $W_{ij}$ be the unique wire containing both $B_i,B_j$, for $i\neq j$.

If $W_{12},W_{23}$ were the same wire then all three beads would be on that one wire, which would contradict Axiom $3$. Thus those two wires are different.

But if $B_1$ were on all the wires then it would have to be on $W_{23}$. Hence $W_{23}$ connects $B_1$ and $B_2$ so, by Axiom $2$ we must have $W_{12}=W_{23}$.

I don't believe Axiom $4$ is needed in this proof.

lulu
  • 70,402
  • Axiom 1 is used in the statement "If $W_{12}$, $W_{23}$ were the same wire then all three beads would be on that one wire" (you even explicitly refer there to the fact that there are three!). – LSpice Oct 15 '19 at 19:38
  • @LSpice Well, as I note in the post, I need a much weaker form of Axion $1$. That is, I need that there are $\textit {at least}$ $3$ beads. I do not need the full strength of Axiom $1$. – lulu Oct 15 '19 at 19:40
  • You do need the full strength of Axiom 1, because you conclude from the fact that three beads are on $W_{12} = W_{23}$ that all beads are on that wire. (That you are using this at least for this specific proof can be seen by taking a model of Axioms 2–4 in which Axiom 1 fails and $W_{12} = W_{23}$; for example, projective space over $\mathbb R$, with beads and wires properly interpreted.) – LSpice Oct 15 '19 at 19:42
  • 1
    @LSpice. Ah, thank you. You are entirely correct. I will edit accordingly. – lulu Oct 15 '19 at 19:47
0

Suppose there is a bead that is on all the wires.

By axiom $1$ there are two other beads.

By axiom $2$ there is a wire containing both these beads.

By axiom $3$ the first bead cannot be on this wire.

Donald Splutterwit
  • 36,613
  • 2
  • 26
  • 73
  • Notice that there's no need for a contradiction obtained by starting with the supposition that there is a bead on all the wires; you can just fix any bead, note that it is not on the wire connecting the other two beads, and conclude that it is therefore not on all wires. – LSpice Oct 15 '19 at 19:46