14-240/Tutorial-October7
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Boris
Subtle Errors in Proofs
Check out these proofs:
Proof 1
Let [math]\displaystyle{ W_1 }[/math], [math]\displaystyle{ W_2 }[/math] be subspaces of a vector space [math]\displaystyle{ V }[/math]. We show that [math]\displaystyle{ W_1 \cup W_2 }[/math] is a subspace
[math]\displaystyle{ \implies W_1 \subset W_2 \or W_2 \subset W_1 }[/math].
- Assume that [math]\displaystyle{ W_1 \cup W_2 }[/math] is a subspace.
- Let [math]\displaystyle{ x \in W_1 }[/math], [math]\displaystyle{ y \in W_2 }[/math].
- Then [math]\displaystyle{ x, y \in W_1 \cup W_2 }[/math].
- Then [math]\displaystyle{ x + y \in W_1 \cup W_2 }[/math].
- Then [math]\displaystyle{ x + y \in W_1 \or x + y \in W_2 }[/math].
- Case 1: [math]\displaystyle{ x + y \in W_1 }[/math]:
- Since [math]\displaystyle{ x \in W_1 }[/math] and [math]\displaystyle{ W_1 }[/math] has additive inverses, then [math]\displaystyle{ (-x) \in W_1 }[/math].
- Then [math]\displaystyle{ (x+y)+(-x)=y \in W_1 }[/math].
- Case 2: [math]\displaystyle{ x + y \in W_2 }[/math]:
- Since [math]\displaystyle{ y \in W_2 }[/math] and [math]\displaystyle{ W_2 }[/math] has additive inverses, then [math]\displaystyle{ (-y) \in W_2 }[/math].
- Then [math]\displaystyle{ (x+y)+(-y)=x \in W_2 }[/math].
- Then [math]\displaystyle{ x \in W_2 \or y \in W_1 }[/math].
- Then [math]\displaystyle{ W_1 \subset W_2 \or W_2 \subset W_1 }[/math]. Q.E.D.
Proof 2
Let [math]\displaystyle{ V=\{(a_1, a_2):a_1, a_2 \in R\} }[/math]. Then [math]\displaystyle{ \forall (a_1, a_2), (b_1, b_2) \in V, \forall c \in R }[/math], define
[math]\displaystyle{ (a_1, a_2) + (b_1, b_2) = (a_1 + 2b_1, a_2 + 3b_2) }[/math] and [math]\displaystyle{ c(a_1, a_2)=(ca_1, ca_2) }[/math]. We show that [math]\displaystyle{ V }[/math] is not a vector
space over [math]\displaystyle{ R }[/math].
- We show that [math]\displaystyle{ V }[/math] is not commutative.
- Let [math]\displaystyle{ (a_1, a_2) = (0, 0) }[/math].
- Then [math]\displaystyle{ (0, 0) + (b_1, b_2) = (2b_1, 3b_2) \neq (b_1, b_2) }[/math].
- Then [math]\displaystyle{ V }[/math] is not commutative.
- Then [math]\displaystyle{ V }[/math] is not a vector space. Q.E.D.
Can you spot the subtle error in each?
In Proof 1, the equivalence of the "let" statement to the second last line and the last line is not obvious:
(1) Let [math]\displaystyle{ x \in W_1, y \in W_2 }[/math]. [Many lines] Then [math]\displaystyle{ x \in W_2 \or y \in W_1 }[/math].
(2) Then [math]\displaystyle{ W_1 \subset W_2 \or W_2 \subset W_1 }[/math].
Rewrite sentences (1) and (2) into a form that is easier to compare:
(1) [math]\displaystyle{ \forall x \in W_1, \forall y \in W_2, (x \in W_2 \or y \in W_1) }[/math].
(2) [math]\displaystyle{ ( \forall x \in W_1, x \in W_2) \or ( \forall y \in W_2, y \in W_1) }[/math].
For Proof 1 to be correct, we must show that sentences (1) and (2) are equivalent. Alternatively, alter the structure of Proof 1 into a proof by contradiction or into proof in which you assume that one of the conditions in the disjunction is satisfied.
In Proof 2, the only thing that is shown is that [math]\displaystyle{ (0, 0) }[/math] is not the additive identity. For Proof 2 to be correct, either plug in a vector that is not [math]\displaystyle{ (0, 0) }[/math] or show that [math]\displaystyle{ (0, 0) }[/math] is the additive identity by some other means, which introduces a contradiction.
