1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear Algebra with Proof by Contradiction

  1. Aug 24, 2016 #1
    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##
    It leads to contradiction.

    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. jcsd
  3. Aug 24, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Aug 24, 2016 #3
    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
  5. Aug 24, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Linear Algebra with Proof by Contradiction
  1. Linear Algebra Proof (Replies: 8)

  2. Linear Algebra proof (Replies: 21)

Loading...