دنباله‌های بازنشناختنی - ویکی‌پدیا، دانشنامهٔ آزاد

این مقاله به دلیل در جمله بندی نیازمند تمیزکاری است. لطفاً تا جای امکان آن‌را از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد.

ترجمهٔ عنوان این مقاله دارای منبع نیست. ویرایش‌گران طبق سیاست تحقیق دست‌اول ممنوع نمی‌توانند اصطلاحات زبان‌های دیگر را بدون منبع ترجمه کنند و از طرف دیگر بر اساس شیوه‌نامه در اکثر مواقع نمی‌توانند عنوان مقاله را با عنوان اصلی آن در الفباهای غیر فارسی و عربی ثبت کنند. اگر برای عنوان فعلی این مقاله، یک معادل مناسب از منابع معتبر یافتید، با ذکر آن منبع و با شیوهٔ صحیح ارجاع، در متن مقاله قرار دهید و سپس مقاله را انتقال دهید. اگر نمی‌دانید چطور انتقال را انجام یا به‌درستی به منابع ارجاع دهید، در صفحهٔ بحث این مقاله درخواست خود را با قراردادن این متن بیان کنید: {{درخواست انتقال}} ''معادل مناسبی که در نظر گرفته‌اید همراه منبعی که این معادل را در آن دیده‌اید'' ~~~~

این نوشتار یا بخش، مفهوم کامل و روشن را نمی‌رساند. لطفاً با ویرایش کردن یا افزودن جزئیات بیشتر به بهبود مقاله کمک کنید و سپس این برچسب را بردارید.

این مقاله نیازمند ویکی‌سازی است. لطفاً با توجه به راهنمای ویرایش و شیوه‌نامه، محتوای آن را بهبود بخشید. (مه ۲۰۱۶)

دنباله‌های بازنشناختنی[ویرایش]

در ریاضیات، در نظریهٔ مدلها، منظور از یک دنباله‌ٔ بازنشناختنی، یا یک دنبالهٔ تمیزداده‌نشدنی، یا یک دنباله‌ٔ متشکل از اعضای از هم بازنشناخته‌شدنی، دنباله‌ای است که تایپ هر چندتایی‌ِ متشکل از اعضای آن، تنها به ترتیب قرار گرفتن آن اعضا وابسته باشد. به بیان دیگر، دنبالهٔ ${\displaystyle (a_{i})_{i\in \omega }}$ از عناصرِ ${\displaystyle a_{i}}$ در مدل هیولا روی مجموعهٔ ${\displaystyle A}$ از پارامترها بازنشناختنی است، هرگاه برای هر تعداد متناهی از اندیسهای ${\displaystyle i_{1},\ldots ,i_{n}}$ تایپ کامل ${\displaystyle tp(a_{i_{1}},\ldots ,a_{i_{n}}/A)}$ تنها به تایپ «بدون‌سورِ» اندیسهای ${\displaystyle i_{1},\ldots ,i_{n}}$ در زبانِ ${\displaystyle \{=,<\}}$ بستگی داشته باشد. برای مثال در تئوری ترتیب‌های خطیِ چگال بدون ابتدا و انتها (دی‌اِلْ‌اُ) هر دنباله‌ٔ صعودی، روی مجموعه‌ٔ تهی بازنشناختنی است. نیز در این تئوری، برای هر مجموعه‌ٔ ${\displaystyle A}$ هر دنباله‌ٔ صعودی که همه‌ٔ اعضای آن در شکافی از ${\displaystyle A}$ واقع شود، روی ${\displaystyle A}$ بازنشناختنی است. برای مثالی دیگر، فرض کنید ${\displaystyle M}$ یک میدان بستهٔ جبری باشد و ${\displaystyle (a_{i})_{i\in \omega }}$ دنباله‌ای از عناصرِ متعالی روی ${\displaystyle M}$. این دنباله نیز روی ${\displaystyle M}$ بازنشناختنی است. در واقع تایپهای شکل‌گرفته از اعضای این دنباله، تنها به تایپ اندیسهای متناظرشان در زبان ${\displaystyle \{=\}}$ وابسته‌اند و از این رو این دنباله را می‌توان «بسیاربازنشناختنی» خواند. به‌طور کلی، در تئوری‌های ثابت، هر دنباله‌ٔ بازنشناختنی، بسیار بازنشناختنی است.

تعریف[ویرایش]

دنباله‌ی ${\displaystyle (a_{i})_{i\in \omega }}$ را که در آن هر ${\displaystyle a_{i}}$ یک چندتایی (نه لزوماً متناهی) در مدل هیولاست، روی مجموعه‌ٔ پارامترِ ${\displaystyle A}$ بازنشناختنی می‌خوانیم هرگاه برای هر ${\displaystyle i_{1}<i_{2}<\ldots <i_{n}\in \omega }$ داشته باشیم ${\displaystyle a_{i_{1}}\ldots a_{i_{n}}\equiv _{A}a_{1}\ldots a_{n}}$؛ یعنی ${\displaystyle tp(a_{i_{1}}\ldots a_{i_{n}}/A)=tp(a_{1}\ldots a_{n}/A)}$.

وجود و نحوه‌ٔ به دست آوردن دنباله‌های بازنشناختنی[ویرایش]

در هر تئوریِ کاملی می‌توان در مدل هیولا دنباله‌ای بازنشناختنی پیدا کرد. برای اثباتِ این امر، از لمی ترکیبیاتی به نام «لم رمزی» استفاده شود. بیان نظریهٔ مدلی این لم به «لمِ استاندارد» موسوم است که در زیر آمده‌است.

لم استاندارد[ویرایش]

فرض کنید ${\displaystyle (a_{i})_{i\in \omega }}$ دنباله‌ای دلخواه در مدل هیولا باشد و ${\displaystyle A}$ مجموعه‌ای باشد از پارامترها. آن‌گاه یک دنبالهٔ ${\displaystyle (b_{i})_{i\in \omega }}$ بازنشناختنی روی ${\displaystyle A}$ چنان یافت می‌شود که تایپِ اهغن‌موستوفسکیِ دنباله‌ی ${\displaystyle A}$ را برآورد. به بیان دیگر، دنباله‌ٔ ${\displaystyle (b_{i})_{i\in \omega }}$ دارای این ویژگی است که برای هر ${\displaystyle n\in \omega }$ و برای هر فرمولِ ${\displaystyle \phi (x_{1},\ldots ,x_{n},y)}$ و برای هر پارامترِ ${\displaystyle a\in A}$، اگر برای هر ${\displaystyle i_{1}<\ldots <i_{n}\in \omega }$ داشته باشیم ${\displaystyle \models \phi (a_{i_{1}},\ldots ,a_{i_{n}},a)}$ آن‌گاه داریم ${\displaystyle \models \phi (b_{1},\ldots ,b_{n},a)}$. نیز به بیان دیگر، دنباله‌ٔ ${\displaystyle (b_{i})_{i\in \omega }}$ دارای این ویژگی است که برای هر فرمولِ ${\displaystyle \phi (x_{1},\ldots ,x_{n},y)}$ و هر ${\displaystyle a\in A}$ از ${\displaystyle \models \phi (b_{1},\ldots ,b_{n},a)}$ نتیجه می‌شود که اندیسهای${\displaystyle i_{1}<\ldots <i_{n}}$ از دنباله‌ٔ اولیه موجودند که ${\displaystyle \models \phi (a_{i_{1}},\ldots ,a_{i_{n}},a)}$
دنبالهٔ حاصل از لم استاندارد، «موضعاً» و حول هر فرمول، شبیه دنباله‌ٔ اولیه است و تضمینی وجود ندارد که تایپهای اعضای آن در دنبالهٔ اولیه موجود باشند. برای به دست آوردن دنباله‌ای که تایپ اعضایش در دنباله‌ٔ اولیه موجود باشد، عموماً از نسخه‌ٔ بهبودیافته‌ای از لم استاندارد، موسوم به «لم شلاخ» استفاده می‌شود که در زیر آمده‌است. شایانِ یادآوری است که از لوازم این لم، در دست داشتن دنباله‌ای باندازه طولانی است.

لم شلاخ[ویرایش]

برای هر مجموعهٔ پارامترِ ${\displaystyle A}$ یک کاردینالِ ${\displaystyle \lambda }$ موجود است به‌طوری‌که برای هر دنباله‌ٔ ${\displaystyle (a_{i})_{i\in I}}$ که در آن ${\displaystyle |I|=\lambda }$ بتوان دنباله‌ٔ بازنشناختنیِ ${\displaystyle (b_{i})_{i\in \omega }}$ را چُنان یافت که برای هر ${\displaystyle n\in \omega }$ اندیسهای ${\displaystyle i_{1}<\ldots <i_{n}\in I}$ پیدا شوند که ${\displaystyle b_{1}\ldots b_{n}\equiv _{A}a_{i_{1}}\ldots a_{i_{n}}}$.

آرایه‌های بازنشناختنی[ویرایش]

ایدهٔ ازهم‌بازشناخته‌نشدن را می‌توان از دنباله‌ها به آرایه‌ها تعمیم داد. در آرایه‌ها نیز چند نوع بازنشناختنی بودن می‌توان تعریف کرد.
آرایه‌ی ${\displaystyle (a_{ij})_{i,j\in \omega }}$ را بازنشناختنی متقابل می‌خوانیم هرگاه هر سطرِ ${\displaystyle (a_{ij})_{j\in \omega }}$ از آن، روی بقیه‌ٔ آرایه، یعنی روی ${\displaystyle (a_{kj})_{k\not =i,j\in \omega }}$ دنباله‌ای بازنشناختنی باشد. معادلاً آرایه‌ٔ ${\displaystyle (a_{ij})_{i,j\in \omega }}$ بازنشناختنی متقابل است، هرگاه برای هر دو سطرِثابت‌گرفته‌شده‌ٔ ${\displaystyle i_{1},i_{2}}$ تایپ چندتاییِ ${\displaystyle a_{i_{1}j_{i_{1}}^{1}}\ldots a_{i_{1}j_{i_{1}}^{m}}a_{i_{2}j_{i_{2}}^{1}}\ldots a_{i_{2}j_{i_{2}}^{m}}}$ تنها به تایپِ اندیسهای ${\displaystyle j_{i_{1}}^{1},\ldots ,j_{i_{1}}^{m}}$ و ${\displaystyle j_{i_{2}}^{1},\ldots ,j_{i_{2}}^{m}}$ در زبان ${\displaystyle \{=,<\}}$ بستگی داشته باشد.
دنباله‌ٔ ستونهای یک آرایه‌ٔ بازنشناختنیِ متقابل، دنباله‌ای بازنشناختنی (از دنباله‌ها) است. آرایه‌های بازنشناختنی متقابل نیز دارای «ساختاری رمزی» هستند. یعنی اگر آرایه‌ٔ دلخواهِ ${\displaystyle (a_{ij})_{i,j\in \omega }}$ داده شده باشد، می‌توان با کمک لم استاندارد، آرایه‌ٔ ${\displaystyle (b_{ij})_{i,j\in \omega }}$ را چنان یافت که ${\displaystyle (b_{ij})_{i,j\in \omega }\models EM((a_{ij})_{i,j\in \omega })}$؛ بدین معنی که ${\displaystyle (b_{ij})_{i,j\in \omega }}$ چنان است که برای هر دو شماره‌ٔ ${\displaystyle i_{1},i_{2}}$ از سطرها و هر فرمولِ ${\displaystyle \phi }$، از این که ${\displaystyle \models \phi (b_{i_{1}1}\ldots b_{i_{1}m}b_{i_{2}1}\ldots b_{i_{2}m})}$ نتیجه شود که اندیسهای ${\displaystyle j_{i_{1}}^{1}<\ldots <j_{i_{1}}^{m},j_{i_{2}}^{1},\ldots <j_{i_{2}}^{m}}$ برای سطرهای آرایه‌ٔ ${\displaystyle (a_{ij})_{i,j\in \omega }}$ پیدا می‌شوند که ${\displaystyle \models \phi (a_{i_{1}j_{i_{1}}^{1}}\ldots a_{i_{1}j_{i_{1}}^{m}},a_{i_{2}j_{i_{2}}^{1}},\ldots a_{i_{2}j_{i_{2}}^{m}})}$.
به این ترتیب، نیز آرایه‌ی ${\displaystyle (a_{ij})_{i,j\in \omega }}$ را بسیاربازنشناختنی می‌خوانیم هرگاه دنباله‌ٔ سطرهای آن (همچون دنباله‌ای از دنباله‌ها) و دنبالهٔ ستونهای آن (همچون دنباله‌ای از دنباله‌ها) هر دو بازنشناختنی باشند.

پانویس[ویرایش]

منابع[ویرایش]