# Linear Algebra with Proof by Contradiction

1. Aug 24, 2016

### Devil Moo

This is a linear algebra question which I am confused.

1. The problem statement, all variables and given/known data

Prove that "if the union of two subspaces of $V$ is a subspace of $V$, then one of the subspaces is contained in the other".

3. The attempt at a solution

Suppose $U$, $W$ are subspaces of $V$. $U \cup W$ is a subspace of $V$. (statement A)

Suppose $U$ is not contained in $W$ and vice versa. (statement B)

Let $u \in U, \not\in W$ and $w \in W, \not\in U$.

$u \in U \cup W, w \in U \cup W$
$u + w \in U \cup W$
$u + w \in U$ or $u + w \in W$

Suppose $u + w \in U$ (statement C)

$u + w + (-u) \in U$
$w \in U$

Which one does it conclude? (if A is true, then B is false) or (if A and B are true, then C is false)

2. Aug 24, 2016

### andrewkirk

It's the second one: (if A and B are true, then C is false)

Since you have proven C false, you can conclude that $u+v\in W$. By similar steps to before you can also conclude that that is false.

You can then, with a few more steps, conclude that at least one of A or B must be false.

Arguments of this kind are much easier to understand and control if you grasp the notion of Conditional Proof or sub-proof. Every time you make a new assumption, you are opening a new sub-proof. When you reach a contradiction, you close that sub-proof, concluding the opposite of the assumption that you used to open it. It is not unusual to have several nested levels of proof. In your case there are three levels.

3. Aug 24, 2016

### Devil Moo

For the proof by contradiction about $\sqrt 2$ is a irrational number, we conclude that it is true once we find the contradiction.
In this case, why can't I conclude that $u + v \in W$ is true?

Is $not (u + v \in U) = u + v \in W$ wrong?

Last edited: Aug 24, 2016
4. Aug 24, 2016

### andrewkirk

You can. Read the second line of my post again.

Then you go on to prove that it is also false, which is a second contradiction, which tells you that either A or B must be false.