Proof by contradiction: an Indirect proof technique

Introduction:

Mathematics proofs రెండు రకాలు: direct proofs and indirect proofs. ఒక్కొక్కసారి direct proof చేయడం కష్టంగా ఉంటుంది. అప్పుడు indirect proof technique ని వాడవలసి వస్తుంది. ఈ indirect proof technique లో proof by contradiction ని విరివిగా వాడుతారు. ఈ proof technique కాస్త కష్టంగా ఉంటుంది అర్థం చేసుకోవడానికి. కాబట్టి దాన్ని సులభతరం చేయడానికి ఈ బ్లాగ్ రాయబడినది.

ఎక్కడ దీనిని వాడుతారు?

ఈ proof by contradiction అనే indirect proof technique ని ఈ క్రింది పేర్కొన్న fields లో వాడవచ్చును.

• నిజజీవితంలో సంఘటనలు సామరస్యంగా తీర్చడానికి 

• Mathematics theorems prove చేయడానికి 

• Computer algorithms termination prove చేయడానికి 

• Judicial system cases గెలవడానికి 

ఈ క్రింది ఈ proof technique యొక్క template ఇవ్వబడింది.

Proof template:

To prove the statement P is true  by proof by contradiction.

1. Assume the statement (not P) is true

2. Derive a contradiction 

3. State that by law of excluded middle the statement P is true.

Real life example:

నేను ఒక పది సంవత్సరాల క్రితం ఒక రోజు పొద్దున్నే వాకింగ్ చేసి ఇంటికి వచ్చి కారు పార్కింగ్ చేసి కారును లాక్ చేసి వెడుతూండగా ఒక ముగ్గురు సాప్ట్వేర్ ఇంజనీర్ లు వచ్చి నన్ను అడ్డగించారు. నేను విస్తుపోయాను దేనికని. వాళ్ళలో కాస్త మేనజర్ గా కనిపిస్తున్న అతను ఈ రెడ్ కలర్ కారు నీదా అని అడిగాడు. అవును నాదే అన్నాను. వెంటనే నా గల్లా పట్టుకుని నీవు మీ గల్లీలో టర్నింగ్ తీసేటప్పుడు నా కార్ కి నీ కారు రాసుకుంది. నాది కొత్త కారు దానికి సన్నగా గీత పడింది. డబ్బు తీ అని మీదకి వచ్చాడు. నాకు నవ్వు వచ్చింది. వాళ్ళు మీదకు వచ్చి నా గల్లా పట్టుకున్నా నాకు కోపం రాలేదు పైపెచ్చు నువ్వు వచ్చింది. 

సరే. నీవు అలా కూర్చో కాస్త ఒక గ్లాసు నీళ్ళు త్రాగు అన్నాను. వాడు హిందీ లో అంటున్నాడు అరే నీవు చాలా షానేగానివి లాగా ఉన్నావు. చాలా లాజిక్ గా మాట్లాడుతున్నావు.

నేను నిజంగా గుద్ది ఉంటే నీకు ఇప్పుడే డబ్బు ఇస్తాను. నీవు worry కాకు అన్నాను. వాడు కాస్త cool అయ్యాడు.

నా మనస్సుకి తెలుసు నేను ఏ వెహికల్ని రాసుకుంటూ రాలేదు అని. దానిని వీడికి తర్కంతో prove చేయాలి అనుకున్నాను. సరే వీడికి proof by contradiction రుచి చూపిద్దాం అని మనస్సులో అనుకున్నాను.

నా మనస్సు లో నేను చెప్పుకున్న statement: నేను అతని vehicle ని రాసుకుంటూ వెళ్ళలేదు. ( ఇది మన statement P)

నా argument వాడికి: సరే! నేను నీ వెహికల్ ని రాసుకుంటూ వచ్చాను అనుకో. ( Not P)

ఇక నేను నా arguments తో contradiction చూపించాలి. దాంతో నా initial assumption wrong అవుతుంది. దాంతో నా original statement right అవుతుంది. ఇదే మన proof template చెబుతున్న strategy.

ఇక నా arguments దాడి మొదలైంది.

నీ వెహికల్ కి గీత పడింది అని నీవు చెప్పావు. నేను నమ్ముతున్నాను.

నా వెహికిల్ కూడా ఇనుముతో నే చేశారు. దానికి పెయింటింగ్ ఉంది. నీ కారుకి ఎడుమ వైపు గీత బడితే Newton third law ప్రకారం నా కారుకి కుడివైపు గీత పడాలి లేదా నీ కారుకి కుడివైపు గీత పడితే నా కారుకి ఎడుమ వైపు గీత పడాలి.

మీరు నా కారు చుట్టూ తిరిగి చూపించండి ఆ పడిన గీతను. అలా చూపిస్తే కనుక నేను వెంటనే మీకు నష్టపరిహారం చెల్లిస్తాను అని అన్నాను.

వాళ్ళ ముగ్గురూ కారు చుట్టూ మూడూ సార్లు తిరిగి ఏ గీత చూపించలేక పోయారు. దాంతో వాళ్ళు contradictionని ఎదురుకున్నారు. వారి కోపం ఆవిరైపోయింది. 

 (Law of excluded middle: దీని అర్థం ఏమిటంటే మన statements true అన్నా అవ్వొచ్చు లేదా false అయినా అవ్వొచ్చు. ఒకేసారి true and false కాదు.)

By the law of excluded middle,  proof మొదట్లో చేసిన assumption  wrong అని తేలింది. అంటే ఆ accident చేసింది నేను కాదు. కాబట్టి నా కారు నీ కారు ని గుద్ద లేదు అని వాళ్ళకి prove చేశాను. దాంతో వాళ్ళు తలొంచుకుని అక్కడి నుండి వెళ్ళిపోయారు. 

ఈ విధంగా మనం ఈ proof techniqueని నిజ జీవితంలో దారిన పోయే శని తగులుకున్నప్పుడు వాడవచ్చును.

Judicial system ఈ technique ని ఏలా వాడుతారు?

రాము అనే మంచి వ్యక్తి రావణ్ అనే మరో వ్యక్తితో వ్యాపారం చేస్తూ ఉంటాడు. ఈ రావణ్ అనే వ్యక్తి అంత మంచివాడు కాడు. వీడు రాముని వ్యాపారంలో మోసం చేస్తూ ఉంటాడు. ఈ విషయం వారి పద్దులు చూసే వ్యక్తికి తెలుసు. అతను రావణ్ ని హెచ్చరిస్తాడు ఈ విషయం రాముకి చెబుతానని. అంతే రావణ్ అతనిని eliminate చేయాలని పధకం పన్నుతాడు. ఈ పాపం రాము‌ మీద వెయ్యాలి అనుకుంటాడు.

ఒక రోజు రాత్రి రావణ్ ఈ పద్దులు రాసే వ్యక్తిని ఆఫీసుకి పిలిచి లేపేస్తాడు. ఈ సమాచారం రాముకి ఒక మూడవ‌ వ్యక్తి ద్వారా ఇప్పిస్తాడు. రాము హుటాహుటిన వస్తాడు అక్కడికి. అంతలో పోలీసులు వచ్చి అతని arrest చేస్తారు. రాము ఎంత అరచి గీపెట్టినా వారు వినిపించుకోరు. రాము తన స్నేహితుడు లాయరు అయిన బాలుకి కబురు పెడతాడు. బాలు వెంటనే రంగంలోకి దిగుతాడు. అసలు విషయం తెలుసుకుంటాడు. ఇక ఈ కేసు తాను కోర్టులో వాదించి తన స్నేహితుడు నిర్దోషి అని నిరూపించాలి అనుకుంటాడు. అతను ఈ proof by contradiction technique వాడుదామిని అనుకుంటాడు.

Statement: రాము నిరపరాది. (P)

Proof:

రాము హంతకుడు ( not P).

హత్య జరిగిన సమయం 7 PM పోలీసు మెడీకల్ టీం ప్రకారం.

ఆ రోజు ఆ సమయంలో రాము వాళ్ళ ఇంకో మిత్రని కొడుకు పుట్టిన రోజు పండుగ ఫంక్షన్ లో సిటీలో ఒక ఫంక్షన్ హాలులో ఉన్నట్టు వీడియో క్లిప్పింగ్స్ ఉన్నాయి.

దీంతో ఒక మనిషి ఒకే రోజు ఒకే సమయానికి రెండు చోట్ల ఉండలేడు కాబట్టి. రాము హత్య జరిగిన సమయంలో అక్కడ లేడు అని మన బాలు evidence ద్వారా prove చేశాడు కోర్టులో.

దీంతో judge by proof by contradiction ప్రకారం రాము నిరపరాది అని తన judgement ఇచ్చాడు.

దీనిని బట్టి ఈ proof by contradiction technique అనేది మన జీవితంలో చాలా పనికి వస్తుంది తెలుసుకున్నాం. కొన్ని పాత సినిమాలు కూడా ఈ technique మీదే పూర్తిగా రాయబడినాయి.

Proof by contradiction in Mathematics:

Example 1: Prove that 101 is an odd ( బేసి సంఖ్య) number.

Proof: మనం ఈ proof ని proof by contradiction ద్వారా prove చేస్తాం.

Step 1: negate the given statement and assume that as the starting statement for the proof.

101 ఒక బేసి సంఖ్య కాదు . అంటే 101 అనేది ఒక సరి సంఖ్య.

ఇది సరి సంఖ్య కాబట్టి మనం

2k = 101 అని రాయవచ్చును. ( ఇది సరి సంఖ్య definition మరియు ఇక్కడ k  అనేది ఒక integer set member)

2k -100 = 101 - 100 ( subtract 100 on either side of the above equation)

On the simplification of the above equation, we get

2(k-50) = 1.

మనం ఏదైనా అంకెని 2 తో కనుక multiply చేస్తే అది సరి సంఖ్య అవుతుంది. కాబట్టి 2(k-50) కూడా ఒక సరి సంఖ్యే. కానీ 1 కాదు.

2 (k-50) = 1

సరి సంఖ్య= బేసి సంఖ్య ( ఇది తప్పు కాబట్టి మనం ఒక contradictionని derive చేశాం ఇక్కడ).

కాబట్టి మన proof starting statement incorrect.  కాబట్టి proof by contradiction ద్వారా 101 బేసి సంఖ్య అనేది prove అయ్యింది.

Exercise: please write your proof in the comments section.

1. Prove that 51 is an odd number using proof by contradiction.