دنباله‌های بازنشناختنی

دنباله‌های بازنشناختنی
در ریاضیات، در نظریه مدلها،
منظور از یک
دنباله‌ بازنشناختنی، یا یک دنباله تمیزداده‌نشدنی، یا یک دنباله‌ متشکل از اعضای از هم بازنشناخته‌شدنی، دنباله‌ای است که تایپ هر چندتایی‌ متشکل از اعضای آن، تنها به ترتیب قرار گرفتن آن اعضا وابسته باشد. به بیان دیگر، دنباله
(a_i)_{i\in \omega
از عناصر
a_i
در مدل هیولا
روی مجموعه
A
از پارامترها
بازنشناختنی است، هرگاه برای هر تعداد متناهی از اندیسهای
i_1,\ldots,i_n
تایپ کامل
tp(a_{i_1,\ldots,a_{i_n/A)
تنها به تایپ «بدون‌سور» اندیسهای
i_1,\ldots,i_n
در زبان
بستگی داشته باشد.
برای مثال در تئوری ترتیب‌های خطی چگال بدون ابتدا و انتها (دی‌ال‌ا) هر دنباله‌ صعودی، روی مجموعه‌ تهی بازنشناختنی است. نیز
در این تئوری،
برای هر مجموعه‌
A
هر دنباله‌ صعودی که همه‌ اعضای آن در شکافی از
A
واقع شود،
روی
A
بازنشناختنی است. برای مثالی دیگر، فرض کنید
M
یک میدان بسته جبری باشد و
(a_i)_{i\in \omega
دنباله‌ای از عناصر متعالی روی
M
این دنباله نیز روی
M
بازنشناختنی است. در واقع تایپهای شکل‌گرفته از اعضای این دنباله، تنها به تایپ اندیسهای متناظرشان در زبان
وابسته‌اند و از این رو این دنباله را می‌توان «بسیاربازنشناختنی» خواند. به‌طور کلی، در تئوری‌های ثابت، هر دنباله‌ بازنشناختنی، بسیار بازنشناختنی است.
تعریف
دنباله‌ی
(a_i)_{i\in\omega
را که در آن هر
a_i
یک چندتایی
(نه لزوما متناهی)
در مدل هیولاست، روی مجموعه‌ پارامتر
A
بازنشناختنی
می‌خوانیم هرگاه برای هر
i_1<i_2<\ldots<i_n\in \omega
داشته باشیم
a_{i_1\ldots a_{i_n\equiv_A a_1\ldots a_n ؛
یعنی
tp(a_{i_1\ldots a_{i_n/A)=tp(a_1\ldots a_n/A) .
وجود و نحوه‌ به دست آوردن دنباله‌های بازنشناختنی
در هر تئوری کاملی می‌توان در مدل هیولا دنباله‌ای بازنشناختنی پیدا کرد. برای اثبات این امر، از لمی ترکیبیاتی به نام «لم رمزی» استفاده شود. بیان نظریه مدلی این لم به
«لم استاندارد» موسوم است که در زیر آمده‌است.
لم استاندارد
فرض کنید
(a_i)_{i\in \omega
دنباله‌ای دلخواه در مدل هیولا باشد
و
A مجموعه‌ای باشد از پارامترها. آن‌گاه یک دنباله
(b_i)_{i\in\omega
بازنشناختنی روی
A
چنان یافت می‌شود که تایپ اهغن‌موستوفسکی دنباله‌ی
A
را برآورد. به بیان دیگر، دنباله‌
(b_i)_{i\in \omega
دارای این ویژگی است که
برای هر
n\in\omega
و
برای هر فرمول
\phi(x_1,\ldots,x_n, y)
و برای هر پارامتر
a\in A
اگر برای هر
i_1<\ldots<i_n\in \omega
داشته باشیم
\models \phi(a_{i_1,\ldots,a_{i_n,a)
آن‌گاه داریم
\models \phi(b_1,\ldots,b_n,a)
نیز به بیان دیگر، دنباله‌
(b_i)_{i\in \omega
دارای این ویژگی است که برای هر فرمول
\phi(x_1,\ldots, x_n,y)
و هر
از
\models \phi(b_{1,\ldots,b_{n,a)
نتیجه می‌شود که
اندیسهای
i_1
از دنباله‌ اولیه موجودند که
\models \phi(a_{i_1,\ldots,a_{i_n,a)
دنباله حاصل از لم استاندارد، «موضعا» و حول هر فرمول، شبیه دنباله‌ اولیه است و تضمینی وجود ندارد که تایپهای اعضای آن در دنباله اولیه موجود باشند.
برای به دست آوردن دنباله‌ای که تایپ اعضایش در دنباله‌ اولیه موجود باشد، عموما از نسخه‌ بهبودیافته‌ای از لم استاندارد، موسوم به «لم شلاخ» استفاده می‌شود که در زیر آمده‌است. شایان یادآوری است که از لوازم این لم، در دست داشتن دنباله‌ای باندازه طولانی است.
لم شلاخ
برای هر مجموعه پارامتر
A
یک کاردینال
\lambda
موجود است به‌طوری‌که برای هر
دنباله‌
(a_i)_{i\in I
که در آن
\lambda
بتوان دنباله‌ بازنشناختنی
(b_i)_{i\in \omega
را چنان یافت که برای هر
n\in\omega
اندیسهای
i_1<\ldots<i_n\in I
پیدا شوند که
b_{1\ldots b_{n\equiv_A a_{i_1\ldots a_{i_n
آرایه‌های بازنشناختنی
ایده ازهم‌بازشناخته‌نشدن را می‌توان از دنباله‌ها به آرایه‌ها تعمیم داد. در آرایه‌ها نیز چند نوع بازنشناختنی بودن می‌توان تعریف کرد.
آرایه‌ی
(a_{ij)_{i,j\in \omega
را بازنشناختنی متقابل می‌خوانیم هرگاه
هر سطر
(a_{ij)_{j\in \omega
از آن، روی بقیه‌ آرایه، یعنی روی
(a_{kj)_{k\not=i, j\in \omega
دنباله‌ای
بازنشناختنی باشد. معادلا آرایه‌
(a_{ij)_{i,j\in \omega
بازنشناختنی متقابل است، هرگاه برای هر دو سطرثابت‌گرفته‌شده‌
i_1,i_2
تایپ
چندتایی
a_{i_1j^1_{i_1\ldots a_{i_1j^m_{i_1a_{i_2j^1_{i_2\ldots a_{i_2j^m_{i_2
تنها به تایپ اندیسهای
و
در زبان
بستگی داشته باشد.
دنباله‌ ستونهای یک آرایه‌ بازنشناختنی متقابل، دنباله‌ای بازنشناختنی (از دنباله‌ها) است. آرایه‌های بازنشناختنی متقابل نیز دارای «ساختاری رمزی» هستند. یعنی اگر
آرایه‌ دلخواه
(a_{ij)_{i,j\in \omega
داده شده باشد، می‌توان با کمک لم استاندارد، آرایه‌
(b_{ij)_{i,j\in \omega
را چنان یافت که
(b_{ij)_{i,j\in \omega\models EM((a_{ij)_{i,j\in \omega) ؛
بدین معنی که
(b_{ij)_{i,j\in \omega
چنان است که برای هر دو
شماره‌
i_1,i_2
از سطرها و هر فرمول
\phi ،
از این که
نتیجه شود که اندیسهای
برای سطرهای
آرایه‌
(a_{ij)_{i,j\in \omega
پیدا می‌شوند که
به این ترتیب، نیز
آرایه‌ی
را بسیاربازنشناختنی می‌خوانیم هرگاه
دنباله‌ سطرهای آن (همچون دنباله‌ای از دنباله‌ها) و دنباله ستونهای آن (همچون دنباله‌ای از دنباله‌ها) هر دو بازنشناختنی باشند.