دنباله فیبوناچی به عنوان یک عملکرد

با گذشت سالها ، مقالات موجود در این وبلاگ طیف گسترده ای از مخاطبان ، از حقایق سرگرم کننده (ضرب غیر شماره ها) ، تا سطح کارشناسی (اولین قضیه ایزومورفیسم ، به طور شهودی) ، برای فارغ التحصیلی (یک عملگر؟) را به خود اختصاص داده است. به سطح تحقیقمقاله امروز بیشتر در مورد واقعیت جالب چیزها است ، همراه با-مانند اکثر مقاله ها در اینجا-چشم به نظریه دسته بندی.

So here's a fun fact about greatest common divisors (GCDs) and the Fibonacci sequence $F_1,F_2,F_3,ldots$, where $F_1=F_2=1$ and $F_n:=F_ + F_$ for $n>1 $برای همه $ n ، m geq 1 $ ،

به قول ، بزرگترین تقسیم کننده مشترک اعداد فیبوناچی $ N $ TH و $ M $ TH $ TH $ شماره فیبوناچی است که شاخص آن بزرگترین تقسیم کننده مشترک $ N $ و $ M $ است.(این یک اثبات است.) با دیدن این ، "حواس اسپیدی" شما ممکن است سوزننده شود. مطمئناً برخی از نقشه های حفظ ساختار در پس زمینه وجود دارد و این هویت به معنای خاص بودن خاص است. اما آن نقشه چیست؟و چه ساختاری را حفظ می کند؟و روش رسمی برای توصیف خاصیت خوب آن چیست؟

پاسخ کوتاه این است که اعداد طبیعی $ Mathbb = <1,2,3,ldots>$ یک مجموعه (POSET) که تا حدی سفارش داده شده است ، و عملکرد $ f colon mathbb to mathbb $ تعریف شده توسط $ n mapsto f_n: = f (n) $ حفظ می شود: $ f_n wedge f_m = f = f wedge f_m = F(n wedge m) $. هنگام مشاهده $ Mathbb $ از این منظر ، ملاقات دو عدد طبیعی دقیقاً GCD آنها است: $ n wedge m = text (n ، m). $ $ اکنون ، یک پستی که در آن هر زیر مجموعه محدود غیرقانونی ملاقات داردبه نام Meet-Semilattice و اعداد طبیعی نمونه ای هستند. همیشه می توانید GCD از زیر مجموعه محدود از اعداد طبیعی را پیدا کنید. و یک عملکرد حفظ جلسات بین ملاقات-ستمیلتیس ، مانند $ F $ در بالا ، به عنوان یک همورفیسم ملاقات-ستمیلتیس نامیده می شود.

کوتاه و شیرین.

اما posets ، ملاقات ها و همورفیسم های ملاقات با ستاد و ستیز همه می توانند در زبان تئوری دسته بندی دوباره بیان شوند: Posets دسته بندی هستند. جلسات محدودیت های طبقه بندی شده ای هستند و همورفیسم های ملاقات-ستمیلتینگ با یک خاصیت خوب ، تانکتور هستند. این تغییر چشم انداز کمی بیش از حد است ، اما فکر کردن در مورد آن جالب است!

به طور خاص ، دسته اعداد طبیعی که در زیر تعریف خواهیم کرد ، یکی از نمونه های مقدماتی مورد علاقه من است. علاوه بر این ، عدم موفقیت این ایده ها ، ما را از طریق تور ایده های اساسی که قبلاً در وبلاگ مورد بحث قرار گرفته بود - دسته بندی ها ، Functors و محدودیت های طبقه بندی شده - که ممکن است برای هر کسی که موضوع را یاد بگیرد مفید است.

بنابراین بیایید شروع کنیم! من می خواهم به شما نشان دهم که چگونه اعداد طبیعی یک دسته با یک خاصیت خوب را تشکیل می دهند: این همه محدودیت دارد. علاوه بر این ، هویت $ متن (f_n ، f_m) = f_< ext(n,m)>$ روش دیگری برای گفتن عملکرد Fibonacci ما $ f colon mathbb to mathbb $ یک عملکرد است که محدودیت ها را حفظ می کند ، به این معنی است که این یک عملکرد مداوم است.

بیایید این ادعاها را یک به یک انجام دهیم.

اعداد طبیعی $ Mathbb $ یک دسته است.

مقوله ای را در نظر بگیرید که اشیاء آن اعداد طبیعی $ Mathbb = است<1,2,3,ldots>$ و مورفیسم های آن توسط تقسیم پذیری داده می شود. یعنی با توجه به دو شماره طبیعی $ n $ و $ m $ ، اگر و فقط اگر $ n $ به طور مساوی $ m $ تقسیم شود ، یک $ n to m $ وجود دارد. من چند شیء و مورفیسم (غیر شناسایی) را در زیر ترسیم کرده ام ، اما بی نهایت موارد دیگر نیز وجود دارد.

سریع این است که این موضوع را در واقع یک مقوله تعریف کند: یک مورفیسم هویت $ n to n $ برای هر $ n در mathbb $ وجود دارد زیرا $ n $ به طور مساوی به خود تقسیم می شود ، و ترکیب مورفیسم $ n به m بهP $ از انتقال قابلیت تقسیم پیروی می کند.

در حقیقت ، با نگاه به زیر کاپوت ، تقسیم پذیری یک سفارش جزئی در مجموعه $ Mathbb $ را تعریف می کند. یعنی این یک رابطه بازتابنده ، ضد متقارن و گذرا است. مجهز به این جزئی ، مجموعه $ Mathbb $ یک poset است. از طرف دیگر ، همانطور که اخیراً نشان داده ایم ، می توانیم $ Mathbb $ را به عنوان دسته مشاهده کنیم: مورفیسم هویت $ n to n $ توسط انعکاس $ n mid n $ ارائه می شود ، و ترکیب $ n to m to p$ با انتقال ارائه می شود. در حقیقت ، این یک دسته بسیار ساده است: بین هر دو شیء حداکثر یک مورفیسم وجود دارد. هر poset که به عنوان یک گروه مشاهده می شود ، این خاصیت را دارد.

در آنچه در ادامه می آید ، بیایید وقتی فکر می کنیم $ Mathbb $ به عنوان یک poset یا یک دسته باشد ، انعطاف پذیر باشیم - که بین این دو نشستن بین این دو تغییر در چشم انداز است.

دسته $ Mathbb $ دارای محدودیت های محدود است که توسط GCD داده شده است.

همانطور که مدتها پیش مورد بحث قرار گرفتیم ، محدودیت ها و کلیمیت ها در نظریه دسته یک (و به نوعی) کارآمدترین روش برای ساخت اشیاء جدید ریاضی از قدیمی هستند.

به عنوان مثال ، با توجه به یک دسته از اعداد طبیعی ، چگونه می توانیم آنها را برای تهیه شماره جدید ترکیب کنیم؟امکانات زیادی وجود دارد: ما می توانیم آنها را اضافه کنیم ، آنها را کم کنیم ، آنها را ضرب کنیم ، آنها را تقسیم کنیم ، GCD خود را محاسبه کنیم و غیره. آخرین گزینه کاملاً متفاوت از بقیه است زیرا چیزی به نام خاصیت جهانی را برآورده می کند.

ما به جزئیات نخواهیم رسید ، اما به یاد بیاورید که GCD $ n $ و $ m $ ملاقات آنها در poset $ mathbb $ است. بنابراین نه تنها GCD پایین تر از $ n $ و $ m $ است ، بلکه این تعداد زیادی از مرزهای پایین است."EST" در اینجا همان چیزی است که ما را به یک خاصیت جهانی که در پس زمینه قرار دارد سرنخ می کند. در واقع ، از نظر تئوری دسته ، متن text (n ، m) $ محصول طبقه ای از $ n $ و $ m $ نامیده می شود ، که یک ساخت و ساز کلی است که در تمام چشم انداز ریاضی ظاهر می شود. نمونه های دیگر محصولات عبارتند از ، ملاقات با Posets به طور کلی ، محصول دکارتی مجموعه های $ x times y $ ، مجموع مستقیم فضاهای بردار با ابعاد محدود $ v oplus w $ ، محصول دکارتی فضاهای توپولوژیکی (سلام ضرب غیراعداد!) ، و موارد دیگر.

در حقیقت ، نه تنها $ text (n ، m) $ محصول $ n $ و $ m $ ، بلکه بازپرداخت آنها ، حد معکوس آنها و تساوی آنها است! اینها همه نمونه هایی از سازه های عمومی تر به نام محدودیت های طبقه بندی شده است. در یک پوزت که به عنوان یک دسته تلقی می شود ، این سازه های مختلف همزمان با یکدیگر اتفاق می افتد. به طور خاص ، در دسته ما $ Mathbb $ ، همه این اصطلاحات بلند به سادگی به GCD تبدیل می شوند. ما قبلاً این موضوع را با جزئیات مورد بحث قرار داده ایم.

اکنون ، به یاد بیاورید که POSET $ Mathbb $ یک Meet-Semilattice است ، که نامی است که به پوزکت هایی داده می شود که در آن ملاقات هر زیر مجموعه محدود غیر خالی وجود دارد. جای تعجب نیست که این مفهوم در تئوری دسته بندی تعمیم دارد. در آنجا ، ملاقات ها با محدودیت ها جایگزین می شوند ، و مقوله ای که در آن حد هر مجموعه محدود از اشیاء (به نام نمودار ، به طور رسمی تر) وجود دارد ، یک دسته کامل کامل نامیده می شود. بنابراین هر ملاقات-سومیلات با بیشترین عنصر ، مانند $ Mathbb $ ، نمونه ای از یک دسته کامل است.*

دنباله فیبوناچی یک عملکرد است.

حال بیایید عملکرد $ f colon mathbb to mathbb $ تعریف شده با اختصاص به هر شماره طبیعی $ n $ n $ th $ th fibonacci ، $ f (n): = f_n $. هنگام مشاهده $ Mathbb $ به عنوان یک دسته ، $ f $ یک عملکرد دهنده است. این از این واقعیت است که $ $ n mid m Quad text quad f_n mid f_m $ $ برای همه $ n ، m geq 1 $ یا به طور معادل ، که برای هر $ n geq 1 $ ، یکی $f_ mid f_ $ برای همه $ k in mathbb $ ، که می تواند با القاء در $ n $ اثبات شود. برای دیدن این موضوع ، بدانید که یک عملکرد بین دسته ها ، تکلیف روی اشیاء (این قسمت $ n mapsto f_n $) و در مورفیسم است. دومی برای هر مورفیسم $ n به m $ ما به یک مورفیسم $ f_n به f_m $ نیاز داریم. اما این دقیقاً دلالت قابل تقسیم در بالا است. انعطاف پذیری و انتقال تقسیم تقسیم بیشتر است که $ $ مورفیسم هویت و همچنین ترکیب را حفظ می کند.

به طور کلی ، Functors بین Posets که به عنوان دسته ها مشاهده می شوند ، دقیقاً توابع حفظ نظم هستند.

و اکنون ما برای خط پانچ آماده هستیم!

این عملکرد مداوم است.

در تئوری دسته ، یک عملکرد بین دسته $ f colon mathsf to mathsf $ در صورت حفظ محدودیت ها ، مداوم نامیده می شود. به طور رسمی گفت: همانطور که در ابتدا گفته شد ، با چیزی به نام نمودار $ x $ در $ mathsf $ شروع می شود. سپس در صورت وجود ، محدوده $ متن x $ از آن نمودار را در $ mathsf $ محاسبه می کند ، و یکی می گوید $ f $ مداوم است اگر یک ایزومورفیسم $ f ( text x) cong lim (fx) وجود داشته باشد.$

به نظر می رسد که وقتی هر دو دسته $ Mathsf $ و $ Mathsf $ ملاقات با Semilattice هستند ، یک عملکرد مداوم بین آنها به چیزی ساده کاهش می یابد: یک همجنسگرایی ملاقات-ستمیلی. در مورد ما ، این به یک تابع $ f colon mathbb to mathbb $ است که ویژگی های زیر را برای همه $ n ، m geq 1 $ برآورده می کند:

1. [$ f $ یک functor است] با سفارش جزئی سازگار است: $ n mid m $ دلالت بر $ f (n) mid f (m) $ دارد.
2. [$ f $ محدودیت ها را حفظ می کند.] آن را حفظ می کند. یعنی یک برابری $ f (n wedge m) = f (n) wedge f (m). $

And as we noted earlier, meets $wedge$ in $mathbb$ are greatest common divisors! Thus, taking $F$ to be the Fibonacci sequence $nmapsto F_n$, the equality in item (2) brings us back to where we started: $F(nwedge m) = F(n) wedge F(m)$ is precisely the condition that $F_(n,m)>= متن (f_n ، f_m) $.

به طور خلاصه ، دنباله فیبوناچی $ n mapsto f_n $ را می توان به عنوان یک عملکرد مداوم مداوم از دسته کامل $ mathbb $ به خود تصور کرد. به عبارت ساده تر ، این یک همجنسگرایی ملاقات-ستمیلتیس بین اعداد طبیعی است که به عنوان یک poset تحت تقسیم پذیری مشاهده می شود.

اکنون ، من اولین کسی هستم که اعتراف می کنم - زبان طبقه بندی شده برای چنین ایده ساده ای بیش از حد بارگذاری شده است. اما جالب است که به دنیای انتزاع بپردازید ، و ببینید که چیزهای خاص چیزهای خاصی از چیزهای کلی تر هستند! و به هر حال ، هیچ چیز خاصی در مورد شماره های فیبوناچی در اینجا وجود ندارد - یک دنباله قابل تقسیم قوی می تواند از این طریق دوباره تجدید شود!

*با تشکر از یک خواننده برای گرفتن حذف اصلی (و نادرست) کلمه محدود.(نظر زیر را ببینید.)