คำจำกัด

ในทางคณิตศาสตร์โดยเฉพาะอย่างยิ่งในทฤษฎีภาษาเชิงรูปธรรมคำโปรไฟไนต์ (profinite words)เป็นการขยายแนวคิดของคำไฟไนต์ (finite words)ไปสู่ปริภูมิเชิงทอพอโลยีที่สมบูรณ์แนวคิดนี้ทำให้สามารถใช้ทอพอโลยีในการศึกษาภาษาและเซมิกรุป ไฟไนต์ ได้ ตัวอย่างเช่น คำโปรไฟไนต์ถูกนำมาใช้เพื่ออธิบายลักษณะทางเลือกของแนวคิดเชิงพีชคณิตของวาไรตี้ของเซมิกรุปไฟไนต์

ให้Aเป็นตัวอักษรเซตของคำโปรไฟไนต์บนAประกอบด้วยส่วนเติมเต็มของปริภูมิเมตริกที่มีโดเมนเป็นเซตของคำบนAระยะทางที่ใช้ในการกำหนดเมตริกนั้นกำหนดโดยใช้แนวคิดของการแยกคำ ต่อไปนี้จะเป็นการนิยามแนวคิดเหล่านั้น ${\displaystyle A^{*}}$

ให้MและNเป็นโมโนอิดและให้pและqเป็นสมาชิกของโมโนอิดMให้φเป็นมอร์ฟิซึมของโมโนอิดจากMไปยังNกล่าวได้ว่ามอร์ฟิซึมφแยกpและq ออกจาก กันได้ก็ต่อเมื่อ ตัวอย่างเช่น มอร์ฟิซึมที่ส่งคำไปยังคู่หรือคี่ของความยาวคำนั้น จะแยกคำว่าababaและabaa ออกจากกันได้ ถูก ต้องแล้ว${\displaystyle \phi (p)\neq \phi (q)}$${\displaystyle \phi :A^{*}\to \mathbb {Z} /2\mathbb {Z} ,w\mapsto |w|(\operatorname {mod} 2)}$${\displaystyle \phi (ababa)=1\neq 0=\phi (abaa)}$

กล่าวกันว่าNแยกpและq ออกจากกันได้ ก็ต่อเมื่อมีมอร์ฟิซึมของโมโนอิดφจากMไปยังNที่แยกpและq ออกจากกันได้ โดยใช้ตัวอย่างก่อนหน้านี้ มอร์ฟิซึม φ แยกababaและabaa ออกจากกันได้ โดยทั่วไปแล้วมอร์ฟิซึม φ จะแยกคำใดๆ ที่มีขนาดไม่เท่ากันเมื่อหารด้วยnโดยทั่วไปแล้ว คำสองคำที่แตกต่างกันสามารถแยกออกจากกันได้โดยใช้โมโนอิดที่มีองค์ประกอบเป็นตัวประกอบของpบวกกับองค์ประกอบใหม่ 0 มอร์ฟิซึมนี้จะส่งคำนำหน้าของpไปยังตัวมันเอง และส่งส่วนที่เหลือทั้งหมดไปยัง 0 ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

ระยะห่างระหว่างคำสองคำที่แตกต่างกันpและqถูกกำหนดให้เป็นส่วนกลับของขนาดของโมโนอิดที่เล็กที่สุดNที่คั่นระหว่างpและqดังนั้น ระยะห่างระหว่างababaและabaaคือระยะห่างของpกับตัวมันเองถูกกำหนดให้เป็น 0 ${\displaystyle {\frac {1}{2}}}$

ระยะทาง dนี้เป็นอัลตราเมตริกนั่นคือ. นอกจากนี้ยังสอดคล้องกับ และ. เนื่องจากคำใดๆpสามารถแยกออกจากคำอื่นๆ ได้โดยใช้โมโนอิดที่มีสมาชิก|p|+1ตัว โดยที่|p|คือความยาวของpดังนั้นระยะทางระหว่างpกับคำอื่นๆ จึงมีค่าอย่างน้อย. ด้วยเหตุนี้ โทโพโลยีที่กำหนดโดยเมตริกนี้จึงเป็นแบบไม่ต่อเนื่อง ${\displaystyle d(x,z)\leq \max \left\{d(x,y),d(y,z)\right\}}$${\displaystyle d(uw,vw)\leq d(u,v)}$${\displaystyle d(wu,wv)\leq d(u,v)}$${\displaystyle {\frac {1}{|p|}}}$

การเติมเต็มแบบโปรไฟไนต์ของซึ่งแทนด้วยคือการเติมเต็มเซตของคำจำกัดภายใต้ระยะทางที่กำหนดไว้ข้างต้น การเติมเต็มนี้รักษาโครงสร้างโมโนอิดไว้ ${\displaystyle A^{*}}$${\displaystyle {\widehat {A^{*}}}}$

โครงสร้างเชิงโทโพโลยีบนนั้นเป็นแบบ กะทัดรัด${\displaystyle {\widehat {A^{*}}}}$

มอร์ฟิซึมโมโนอิดใดๆที่มีMเป็นเซตจำกัด สามารถขยายได้อย่างไม่ซ้ำกันเป็นมอร์ฟิซึมโมโนอิดและมอร์ฟิซึมนี้มีความต่อเนื่องสม่ำเสมอ (โดยใช้เมตริกใดๆ บนที่เข้ากันได้กับโทโพโลยีแบบไม่ต่อเนื่อง) ยิ่งไปกว่านั้นยังเป็นปริภูมิโทโพโลยีที่เล็กที่สุดที่มีคุณสมบัตินี้ด้วย ${\displaystyle \phi :A^{*}\to M}$${\displaystyle {\widehat {\phi }}:{\widehat {A^{*}}}\to M}$${\displaystyle M}$${\displaystyle {\widehat {A^{*}}}}$

คำพหูพจน์คือองค์ประกอบของภาษาพหูพจน์ และภาษาพหูพจน์คือเซตของคำพหูพจน์ คำจำกัดทุกคำเป็นคำพหูพจน์ ตัวอย่างของคำพหูพจน์ที่ไม่ใช่คำจำกัดมีดังต่อไปนี้ ${\displaystyle {\widehat {A^{*}}}}$

สำหรับคำใดๆm ให้ แทนซึ่งมีอยู่เพราะเป็นลำดับโคชีตามสัญชาตญาณ เพื่อแยกและโมโนอิดควรนับอย่างน้อยถึงและดังนั้นจึงต้องการอย่างน้อยสมาชิก เนื่องจากเป็นลำดับโคชีดังนั้นจึงเป็นคำโปรไฟไนต์อย่างแท้จริง ${\displaystyle m^{\omega }}$${\displaystyle \lim _{i\to \infty }m^{i!}}$${\displaystyle m^{i!}}$${\displaystyle m^{i!}}$${\displaystyle m^{i'!}}$${\displaystyle \min(i,i')}$${\displaystyle \min(i,i')}$${\displaystyle m^{i!}}$${\displaystyle m^{\omega }}$

นอกจากนี้ คำนี้ ยัง เป็น คำ ที่คงตัว (idempotent ) เนื่องจากสำหรับมอร์ฟิซึมใดๆที่Nเป็นจำนวนจำกัดเนื่องจากNเป็นจำนวนจำกัด ดังนั้นสำหรับiที่มากพอ จึงเป็นคำที่คงตัว และลำดับจึงเป็นค่าคงที่ ${\displaystyle m^{\omega }}$${\displaystyle \phi :A^{*}\to N}$${\displaystyle \phi (m^{i!})=\phi (m)^{i!}}$${\displaystyle \phi (m)^{i!}}$

ในทำนองเดียวกันและถูกกำหนดให้เป็นและตามลำดับ ${\displaystyle m^{\omega +1}}$${\displaystyle m^{\omega -1}}$${\displaystyle \lim _{n\to \infty }m^{n!+1}}$${\displaystyle \lim _{n\to \infty }m^{n!-1}}$

แนวคิดเรื่องภาษาโปรไฟไนต์ช่วยให้เราสามารถเชื่อมโยงแนวคิดของทฤษฎีเซมิกรุปเข้ากับแนวคิดของโทโพโลยีได้ กล่าวคือ เมื่อกำหนดให้ Pเป็นภาษาโปรไฟไนต์ ข้อความต่อไปนี้จะเทียบเท่ากัน:

• Pเป็นคลอโอเพ น
• ตัวอักษร Pสามารถจดจำได้
• ความสอดคล้องทางไวยากรณ์ของPคือ clopen เนื่องจากเป็นเซตย่อยของ${\displaystyle {\widehat {A^{*}}}\times {\widehat {A^{*}}}}$

ข้อความที่คล้ายกันนี้ยังใช้ได้กับภาษาPที่ประกอบด้วยคำจำกัด เงื่อนไขต่อไปนี้ถือว่าเทียบเท่ากัน

• ${\displaystyle P}$สามารถระบุได้ (ในฐานะที่เป็นส่วนย่อยของ)${\displaystyle A^{*}}$
• การปิดของP , , สามารถระบุได้ (ในฐานะเซตย่อยของ)${\displaystyle {\overline {P}}}$${\displaystyle {\widehat {A^{*}}}}$
• ${\displaystyle P=K\cap A^{*}}$สำหรับKบาง ตัว
• ${\displaystyle {\overline {P}}}$คือ clopen

ลักษณะเฉพาะเหล่านั้นเกิดจากข้อเท็จจริงทั่วไปที่ว่า การทำให้ภาษาที่มีคำจำกัดมีความสมบูรณ์แบบ และการจำกัดภาษาที่มีคำจำกัดให้เหลือเพียงคำจำกัดนั้น เป็นการดำเนินการผกผัน เมื่อนำไปใช้กับภาษาที่สามารถจดจำได้