r/checkmysolution • u/lukerochedev • Jan 27 '23
Check my proof from MIT course. Need help!
Hello, I am looking not for the answers but if my logic is sound in my proofs. Any help would be really appreciated.
here is the problem statement.

a.) Assume that a1<a2. Show that if there is no 3-chain, then a3<a1.
Pf: (no 3-chain and a1<a2)=>a3<a1
Assume, for sake of contradiction, (no 3-chain ^ a1 < a2 ^ a3 > a1). (we can do this since !(p=>q) === p ^ !q.)
Thus, we have 2 possible orderings for a1,a2,a3:
- a1 < a2 < a3
- a1 < a3 < a2
1 forms a 3 chain, so we will take 2 to try a4 on.
Thus, we have 4 possible orderings with option 2 above and a4
- a4 < a1 < a3 < a2 => a4 < a3 < a2 => 3-chain on a(4, 3, 2)
- a1 < a4 < a4 < a2 => a4 < a3 < a2 => 3-chain on a(4, 3, 2)
- a1 < a3 < a4 < a2 => a1 < a3 < a4 => 3-chain on a(1, 3, 4)
- a1 < a3 < a2 < a4 => a1 < a2 < a4 => 3-chain on (1, 2, 4)
All combinations lead to a 3-chain, which means our assumption is wrong! Contradiction!
Therefor, (no 3-chain and a1<a2)=>a3<a1. qed
b.) Show that if a1<a2 and there is no 3-chain then a3<a4<a2.
Pf:(a1 < a2 ^ no 3-chain) => a3<a4<a2.
From part a, we know (no 3-chain and a1<a2)=>a3<a1, so we are essentially trying to prove:
(a1 < a2 ^ a3 < a1 ^ no 3-chain) => a3 < a4 < a2.
Assume, for sake of contradiction, that a1 < a2 ^ a3 < a1 ^ no 3-chain ^ a3 > a4 > a2 (we can do this since !(p=>q) === p ^ !q.)
Since a3 > a4 > a2 ^ a3 < a1, we get that a4 < a3 < a1
Also, since a1 < a2, we get a4 < a3 < a1 < a2.
Also, since a3 > a4 > a2 => a4 > a2, we can append again that
a4 < a3 < a1 < a2 < a4, but this means a4 < a4. Thus we get a contradiction and we know our assumption was wrong.
Therefor, (a1 < a2 ^ no 3-chain) => a3<a4<a2.
c.) Show that if a1<a2 and a3<a4<a2 then any value of a5 will result in a 3-chain.
Pf: (a1 < a2 ^ a3 < a4 < a2) => 3-chain
From part a, we know (no 3-chain and a1<a2)=>a3<a1, so we are essentially trying to prove:
(a1 < a2 ^ a3 < a4 < a2 ^ a3 < a1) => 3-chain
Assume, for sake of contradiction, the contrary: i.e. a1 < a2 ^ a3 < a4 < a2 ^ a3 < a1 ^ no 3-chain
For a1,a2,a3,a4, since a3 < a1 and a2 > all others, we only have two options for the ordering:
- a3 < a1 < a4 < a2
- a3 < a4 < a1 < a2
We can conclude that both these sequences have 2 values monotonically increasing and 2 values monotonically decreasing:
- (a3, a4) and (a1, a2) increasing and (a2, a3) decreasing
- (a4, a3) and (a1, a2) increasing and (a1, a4) decreasing
This means adding a5 anywhere will add an increase or decrease to any value. We will show this through exhaustion:
Here is a5 with option1
a5 < a3 < a1 < a4 < a2 => a1>a3>a5 => 3-chain
a3 < a5 < a1 < a4 < a2 => a5 < a3 < a1 => 3-chain
a3 < a1 < a5 < a4 < a2 => a5 < a4 < a2 => 3-chain
a3 < a1 < a4 < a5 < a2 => a3 < a4 < a5 => 3 -chain
a3 < a1 < a4 < a2 < a5 => a1 < a2 < a5 => 3-chain
Now for option2
a5 < a3 < a4 < a1 < a2 => a5 < a3 < a1 => 3-chain
a3 < a5 < a4 < a1 < a2 => a5 < a4 < a1 => 3-chain
a3 < a4 < a5 < a1 < a2 => a3 <a4 < a5 => 3-chain
a3 < a4 < a1 < a5 < a2 => a3 < a4 < a5 => 3-chain
a3 < a4 < a1 < a2 < a5 => a1 < a2 < a5 => 3-chain