We have a problem instance P, and our greedy choice was p_hat.

We've already proven the greedy choice property, 
    there is some OPTIMAL solution PI* that uses p_hat.

Also, we've proven (by inspection) that after making greedy first
choice
p_hat for P, we are left with smaller instance P' of scheduling
problem.

What is left is to prove:

If PI' is an opt solution to P', 
  then PI' union {p_hat} is an optimal solution to P.

Proof.
  (One way to prove A --> B is to "assume A, then prove B".)

  Assume PI' is an optimal solution to P'.


  Under this assumption, prove: 
  PI is optimal solution to P.  
      (where PI is PI' union {p_hat})
  Proof by contradiction:

    Assume PI is not optimal solution to P.
     
       Recall, from the greedy choice property (which we already
       proved),
       there is some OPTIMAL solution PI* that uses {p_hat}.
    |PI*| > |PI|,    because PI is not
    optimal.

    |PI* - {p_hat}| > |PI - {p_hat}|
    |PI* - {p_hat}| > |PI'|

    but since PI* uses p_hat, PI* - {p_hat} is a solution to P'.

  So PI* - {p_hat} is a better solution to P' than PI'
  which is a contradiction, because PI' is assume to be optimal
  solution to P'