ریاضی را حرف بزن · راه کارشناسی ارشد

اثبات: چند نشانه که یک استدلال را حمل می‌کنند

اثبات داستانی است که هر خطش باید از خط‌های پیشین نتیجه شود. با چند نشانه می‌توان کل استدلال را در یک صفحه نوشت و خط به خط وارسی کرد.

پیش‌نویس: نوشتهٔ یک دستیار هوش مصنوعی؛ هنوز معلمی آن را بررسی نکرده است.

الفبا

هر نماد را همان‌طور که زیرش نوشته شده بلند بخوان.

$N := p_{۱} p_{۲} \dots p_{k} + ۱$ بخوان: فرض کنیم N برابر است با p یک در p دو در ... در p k، به‌علاوهٔ یکیعنی: «فرض کنیم» نامی تازه برای شیئی که همین حالا ساخته‌ایم معرفی می‌کند
$p ∣ N$ بخوان: p، N را عاد می‌کندیعنی: N مضربی صحیح از p است؛ از چپ به راست بخوان، اول کوچک‌تر
$P \Rightarrow Q$ بخوان: P نتیجه می‌دهد Q (یا: اگر P آن‌گاه Q)یعنی: هر وقت P درست باشد، Q هم درست است
$P \Rightarrow Q, P ∴ Q$ بخوان: P نتیجه می‌دهد Q و P برقرار است؛ پس Qیعنی: سه نقطه می‌گوید: این خط از خط‌های بالاتر ناگزیر نتیجه می‌شود
$(\neg P \Rightarrow ⊥) \Rightarrow P$ بخوان: اگر نقیضِ P به تناقض برسد، آن‌گاه Pیعنی: اثبات به برهان خلف: خلافش را فرض کن، به تناقض برس، پس حکم درست است
$P (۱) \land \forall n (P (n) \Rightarrow P (n + ۱)) \Rightarrow \forall n P (n)$ بخوان: P از ۱، و به ازای هر n، P از n نتیجه می‌دهد P از n به‌علاوهٔ یک؛ پس P از n به ازای هر nیعنی: استقرا: اولین مهره می‌افتد و هر مهره مهرهٔ بعدی را می‌اندازد
$■$ بخوان: پایان اثبات (حکم ثابت شد)یعنی: مربع سیاه پایان استدلال را نشان می‌دهد: حکم ثابت شد

داستان: چرا بزرگ‌ترین عدد اول وجود ندارد

زیرنویس:

روی هر سطر بزن تا کلمه‌هایش را ببینی.

$p_{۱} < p_{۲} < \dots < p_{k}, P = {p_{۱}, p_{۲}, \dots, p_{k}}$ فرض کنیم بزرگ‌ترین عدد اول وجود دارد. آن‌گاه همهٔ اعداد اول را می‌توان از کوچک به بزرگ فهرست کرد: p یک تا p k.
$N := p_{۱} p_{۲} \dots p_{k} + ۱$ فرض کنیم N حاصل‌ضرب کل فهرست، به‌علاوهٔ یک باشد.
$p_{i} ∣ p_{۱} p_{۲} \dots p_{k} \Rightarrow p_{i} ∤ N (i = ۱, \dots, k)$ هر عدد اول فهرست، حاصل‌ضرب را عاد می‌کند، پس نمی‌تواند N را که یکی بیشتر است عاد کند.
$N > ۱ \Rightarrow \exists q \in P, q ∣ N$ اما N از ۱ بزرگ‌تر است، پس مقسوم‌علیهٔ اولی مثل q دارد، و هر عدد اولی در فهرست است.
$q ∣ N \land q ∤ N \Rightarrow ⊥$ پس q، N را عاد می‌کند و q، N را عاد نمی‌کند. این تناقض است.
$∴ \forall p \in P, \exists q \in P, q > p$ بنابراین فرض ما نادرست بود: هر عدد اولی را برداری، عدد اولِ بزرگ‌تری هست.
$■$ پایان اثبات.
$۲ \cdot ۳ \cdot ۵ \cdot ۷ \cdot ۱۱ \cdot ۱۳ + ۱ = ۳۰۰۳۱ = ۵۹ \cdot ۵۰۹$ وارسی: شش عدد اول نخست ۳۰۰۳۱ را می‌دهند که اول نیست، ولی عامل‌های اولش ۵۹ و ۵۰۹ تازه‌اند.

این داستان با کلمه‌ها ۵۶۶ حرف است؛ با نمادها ۱۱۹.

بخوانش

چه می‌گوید؟

$P \Rightarrow Q$

$P (۵) \Rightarrow P (۶)$

$p ∣ ۱۲$

$A \Rightarrow ⊥ ∴ \neg A$

$N := ۲ \cdot ۳ \cdot ۵ + ۱$

$۳ ∤ ۱۰$

$\neg Q \Rightarrow \neg P$

$P (۱) \land P (۲) \land P (۳)$

$\forall n (P (n) \Rightarrow P (n + ۱))$

$۲ \in Q \Rightarrow ⊥ ∴ ۲ \in / Q$

$a ∣ b \land b ∣ c \Rightarrow a ∣ c$

$■$

بنویسش

کدام نمادنویسی همین را می‌گوید؟

اگر ۴ عدد n را عاد کند، آن‌گاه ۲ عدد n را عاد می‌کند.

حکم برای ۱ برقرار است و هر وقت برای n برقرار باشد برای n به‌علاوهٔ یک هم برقرار است؛ پس برای هر n برقرار است.

اگر فرضِ خلافِ P به تناقض برسد، آن‌گاه P برقرار است.

p عدد N را عاد می‌کند.

اگر n زوج باشد، آن‌گاه n به توان دو زوج است.

P نتیجه می‌دهد Q، و P برقرار است؛ پس Q.

فرض کنیم N برابر ۲ به توان n منهای ۱ باشد.

اگر فرضِ P به تناقض برسد، آن‌گاه P نادرست است.

حکم برای ۱ و برای ۲ برقرار است، و هر وقت برای n برقرار باشد برای n به‌علاوهٔ ۲ هم برقرار است؛ پس برای هر n برقرار است.

هر مضرب ۱۰ مضربی از ۵ است.

P برقرار است، و اثبات تمام است.

مهرهٔ اول می‌افتد: حکم برای n برابر ۱ برقرار است.

بسازش

کاشی‌ها را به ترتیب بزن. یکی از کاشی‌ها اضافه است.

اگر حکم برای n برقرار باشد، برای n به‌علاوهٔ یک هم برقرار است.

فرض کنیم N حاصل‌ضرب p یک تا p k، به‌علاوهٔ یک باشد.

P نتیجه می‌دهد Q، و P؛ پس Q.

اگر نقیضِ P به تناقض برسد، آن‌گاه P.

حکم برای ۱ برقرار است، و برای هر n از n به n به‌علاوهٔ ۱ منتقل می‌شود؛ پس برای هر n برقرار است.

۳ عدد ۱۲ را و ۱۲ عدد ۲۴ را عاد می‌کند؛ پس ۳ عدد ۲۴ را عاد می‌کند.

چالش‌ها

معماهای خلاقانه‌ای که همهٔ نمادهای این فصل را به کار می‌برند. عجله نکن؛ ساعتی در کار نیست.

1 چه کسی چه کسی را عاد می‌کند

سطرها مقسوم‌علیه‌اند و ستون‌ها عددها. هر جمله را داوری کن: درست یا نادرست؟

	$۶$	$۱۰$	$۱۵$	$۳۰$
$۲$	✓	✓		✓
$۳$	✓		✓	✓
$۵$		✓	✓	✓

تیک یعنی عددِ سطر، عددِ ستون را عاد می‌کند.

$\forall d : d ∣ ۳۰$
$\forall n : ۲ ∣ n$
$۳ ∣ ۱۰ \Rightarrow ۵ ∣ ۶$
$۳ ∣ ۱۵ \Rightarrow ۳ ∣ ۱۰$
$\exists n : ۲ ∣ n \land ۳ ∣ n \land ۵ ∣ n$

2 شش نشانهٔ یک استدلال

هر سطر را به معنایش وصل کن.

روی یک سطر بزن، بعد روی معنایش.

3 اشتباه وسوسه‌انگیز

از «اگر P آنگاه Q» و P می‌توانیم Q را نتیجه بگیریم. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

4 زنجیرهٔ دومینوها

استقرا: دومینوی اول می‌افتد و هر دومینو بعدی را می‌اندازد؛ پس همه می‌افتند. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

5 دومینوهای جاافتاده

دومینوی ۱ می‌افتد و هر دومینو آن را که دو جا جلوتر است می‌اندازد. چه می‌توان نتیجه گرفت؟

$P (۱), \forall n (P (n) \Rightarrow P (n + ۲)) ∴ ?$

6 بی‌معنایی از یک فرض

فرض کن P نادرست است و به تناقض برس. چه چیزی ثابت شده است؟

$(\neg P \Rightarrow ⊥) ∴ ?$

7 عددی اول که نداشتیم

فرض کنیم N به شکل زیر تعریف شده باشد. کدام یک N را عاد می‌کند؟

$N := ۳ \cdot ۵ \cdot ۷ + ۱, ? ∣ N$

8 برهانی دو خطی

هر مضرب ۶ مضربی از ۳ است. برهان را با نماد بنویس: اگر ۶ عدد n را عاد کند، آنگاه n = ۶k = ۳(۲k)، پس ۳ عدد n را عاد می‌کند. آن را درست تمام کن. بعد مقایسه کن.

نوشتهٔ تو

9 چهار عدد، چهار مقسوم‌علیه

در این جهان کوچک n فقط روی ۴ و ۶ و ۹ و ۱۲ می‌گردد. تیک نشان می‌دهد کدام کدام را عاد می‌کند. هر جمله را داوری کن.

	$۲ ∣ n$	$۳ ∣ n$	$۴ ∣ n$	$۶ ∣ n$
$۴$	✓		✓
$۶$	✓	✓		✓
$۹$		✓
$۱۲$	✓	✓	✓	✓

تیک یعنی عددِ ستون عددِ سطر را عاد می‌کند.

$\forall n : ۴ ∣ n \Rightarrow ۲ ∣ n$
$\forall n : ۲ ∣ n \Rightarrow ۴ ∣ n$
$\forall n : (۲ ∣ n \land ۳ ∣ n) \Rightarrow ۶ ∣ n$
$\forall n : ۶ ∣ n \Rightarrow ۴ ∣ n$
$\exists n : ۳ ∣ n \land ۲ ∤ n$
$\forall n : ۳ ∣ n \Rightarrow ۶ ∣ n$

10 اجزای یک ردیف دومینو

هر خط را به نقشش در اثبات به استقرا وصل کن.

روی یک سطر بزن، بعد روی معنایش.

11 چهار پیکان

چهار پیکان شبیه هم. هر یک را به آن‌چه واقعاً می‌گوید وصل کن.

روی یک سطر بزن، بعد روی معنایش.

12 تناقض چه چیزی را ثابت می‌کند

برهان خلف: اگر فرضِ نقیض P به بی‌معنایی برسد، آن‌گاه P برقرار است. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

13 یکی بیشتر از حاصل‌ضرب

فرض کنیم N حاصل‌ضرب اعداد اول فهرست به‌علاوهٔ یک باشد؛ آن‌گاه هیچ عدد اولِ فهرست N را عاد نمی‌کند. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

14 پنج عدد اول و یک غریبه

N یکی بیشتر از حاصل‌ضرب پنج عدد اول نخست است. چه نتیجه می‌شود؟

$N := ۲ \cdot ۳ \cdot ۵ \cdot ۷ \cdot ۱۱ + ۱ = ۲۳۱۱ ∴ ?$

15 نردبانی که از پلهٔ ۳ شروع می‌شود

مهرهٔ سوم می‌افتد و از ۳ به بعد هر مهره بعدی را می‌اندازد. چه می‌توان نتیجه گرفت؟

$P (۳), \forall n \geq ۳ (P (n) \Rightarrow P (n + ۱)) ∴ ?$

16 زمین خشک

اگر باران آمده باشد (R)، زمین خیس است (W). زمین خیس نیست. چه نتیجه می‌شود؟

$R \Rightarrow W, \neg W ∴ ?$

17 زوج به‌علاوهٔ زوج

مجموع دو عدد زوج زوج است. اثبات را بنویس: فرض کن a = ۲m و b = ۲n، جمعشان کن، ۲ را فاکتور بگیر و درست تمام کن. بعد مقایسه کن.

نوشتهٔ تو

18 بزرگ‌ترین عدد زوج وجود ندارد

فرض کن M بزرگ‌ترین عدد زوج باشد. آن‌گاه M + ۲ زوج و بزرگ‌تر است: تناقض. پس بزرگ‌ترین عدد زوج وجود ندارد. استدلال را بنویس. بعد مقایسه کن.

نوشتهٔ تو

داستان خودت را بگو

یک اثبات دوخطی برای چیزی کوچک بنویس — مجموع دو عدد زوج زوج است — فقط با نمادها: یک «فرض کنیم»، یک استلزام، یک «پس» و مربع سیاه.

فقط روی همین دستگاه نگه داشته می‌شود.

اثبات: چند نشانه که یک استدلال را حمل می‌کنند

الفبا

داستان: چرا بزرگ‌ترین عدد اول وجود ندارد

بخوانش

بنویسش

بسازش

چالش‌ها

1 چه کسی چه کسی را عاد می‌کند

2 شش نشانهٔ یک استدلال

3 اشتباه وسوسه‌انگیز

4 زنجیرهٔ دومینوها

5 دومینوهای جاافتاده

6 بی‌معنایی از یک فرض

7 عددی اول که نداشتیم

8 برهانی دو خطی

9 چهار عدد، چهار مقسوم‌علیه

10 اجزای یک ردیف دومینو

11 چهار پیکان

12 تناقض چه چیزی را ثابت می‌کند

13 یکی بیشتر از حاصل‌ضرب

14 پنج عدد اول و یک غریبه

15 نردبانی که از پلهٔ ۳ شروع می‌شود

16 زمین خشک

17 زوج به‌علاوهٔ زوج

18 بزرگ‌ترین عدد زوج وجود ندارد

داستان خودت را بگو

دانلود برای استفاده بدون اینترنت