อ่าน 4 นาที
ความเท่าเทียมกันขั้นพื้นฐาน
ในทฤษฎีแบบจำลองซึ่งเป็นสาขาหนึ่งของตรรกศาสตร์ทางคณิตศาสตร์โครงสร้าง สองแบบMและN ที่มี ลายเซ็นσเดียวกันจะเรียกว่าสมมูลกันโดยพื้นฐาน หาก โครงสร้าง ทั้งสองนั้นสอดคล้องกับ...
ความเท่าเทียมกันขั้นพื้นฐาน
ในทฤษฎีแบบจำลองซึ่งเป็นสาขาหนึ่งของตรรกศาสตร์ทางคณิตศาสตร์โครงสร้าง สองแบบMและN ที่มี ลายเซ็นσเดียวกันจะเรียกว่าสมมูลกันโดยพื้นฐาน หาก โครงสร้าง ทั้งสองนั้นสอดคล้องกับ ประโยคσอันดับแรก เดียวกัน
ถ้าNเป็นโครงสร้างย่อยของMมักจะต้องมีเงื่อนไขที่เข้มงวดกว่า ในกรณีนี้Nเรียกว่าโครงสร้างย่อยพื้นฐาน (elementary substructure ) ของM ถ้า สูตรσอันดับแรกφ ( a 1 , …, a n ) ทุกสูตรที่มีพารามิเตอร์a 1 , …, a nจากNเป็นจริงในNก็ต่อเมื่อเป็นจริงใน M เท่านั้น ถ้าNเป็นโครงสร้างย่อยพื้นฐานของMแล้วMเรียกว่าส่วนขยายพื้นฐานของ Nการฝังh : N → Mเรียกว่าการฝังพื้นฐานของNลงในMถ้าh ( N ) เป็นโครงสร้างย่อยพื้นฐาน ของ M
โครงสร้างย่อยNของMจะเป็นโครงสร้างพื้นฐานก็ต่อเมื่อผ่านการทดสอบ Tarski–Vaught เท่านั้น กล่าวคือ สูตรอันดับแรกφ ( x , b 1 , …, b n ) ทุก สูตร ที่มีพารามิเตอร์ในNซึ่งมีคำตอบในMก็จะมีคำตอบใน Nเมื่อประเมินใน M ด้วยเช่นกัน เราสามารถพิสูจน์ได้ว่าโครงสร้างสองโครงสร้างนั้นเทียบเท่ากันในเชิงพื้นฐานด้วยเกม Ehrenfeucht–Fraïssé
การฝังข้อมูลขั้นพื้นฐานถูกนำมาใช้ในการศึกษาจำนวนเชิงคาร์ดินัลขนาดใหญ่รวมถึงการฝังข้อมูลแบบลำดับชั้นต่อลำดับชั้น
โครงสร้างที่เทียบเท่ากันในระดับพื้นฐาน
โครงสร้าง MและNสองโครงสร้าง ที่มีลายเซ็น σเดียวกันนั้น จะสมมูลกันโดยพื้นฐานก็ต่อเมื่อประโยคอันดับหนึ่ง (สูตรที่ไม่มีตัวแปรอิสระ) ทุกประโยคบน σเป็นจริงในMก็ต่อเมื่อเป็นจริงในN เท่านั้น กล่าว คือ ถ้าMและNมีทฤษฎีอันดับหนึ่งที่สมบูรณ์ เหมือนกัน ถ้า MและNสมมูลกันโดยพื้นฐาน เราจะเขียนว่า M ≡ N
ทฤษฎีอันดับแรกจะสมบูรณ์ก็ต่อเมื่อแบบจำลองสองแบบใดๆ ของทฤษฎีนั้นสมมูลกันในเชิงพื้นฐาน
ตัวอย่างเช่น พิจารณาภาษาที่มีสัญลักษณ์ความสัมพันธ์ทวิภาคหนึ่งตัวคือ '<' แบบจำลองRของจำนวนจริงที่มีลำดับปกติ และแบบจำลองQของจำนวนตรรกยะที่มีลำดับปกติ มีความสมมูลกันในเชิงพื้นฐาน เนื่องจากทั้งสองแบบจำลองตีความ '<' ว่าเป็นการเรียงลำดับเชิงเส้น หนาแน่นที่ไม่จำกัดขอบเขต ซึ่งเพียงพอที่จะรับประกันความสมมูลกันในเชิงพื้นฐาน เพราะทฤษฎีของการเรียงลำดับเชิงเส้นหนาแน่นที่ไม่จำกัดขอบเขตนั้นสมบูรณ์แล้ว ดังที่สามารถแสดงได้ด้วย การทดสอบ Łoś – Vaught
โดยทั่วไปแล้ว ทฤษฎีอันดับหนึ่งใดๆ ที่มีแบบจำลองอนันต์จะมีแบบจำลองที่ไม่สมมาตรแต่เทียบเท่ากันในเชิงพื้นฐาน ซึ่งสามารถหาได้จากทฤษฎีบทโลเวนไฮม์-สโกเลมตัวอย่างเช่น มีแบบจำลองที่ไม่เป็นมาตรฐานของเลขคณิตพีอาโนซึ่งประกอบด้วยวัตถุอื่นๆ นอกเหนือจากตัวเลข 0, 1, 2 เป็นต้น แต่ก็ยังเทียบเท่ากับแบบจำลองมาตรฐานในเชิงพื้นฐาน
โครงสร้างย่อยพื้นฐานและส่วนขยายพื้นฐาน
Nเป็นโครงสร้างย่อยพื้นฐานหรือแบบจำลองย่อยพื้นฐานของMถ้าNและM เป็นโครงสร้างที่มี ลายเซ็น σเดียวกัน โดยที่สำหรับ สูตรσอันดับแรกทั้งหมดφ ( x 1 , …, x n ) ที่มีตัวแปรอิสระx 1 , …, x nและองค์ประกอบทั้งหมดa 1 , …, a nของ Nนั้นφ ( a 1 , …, a n ) เป็นจริงในNก็ต่อเมื่อมันเป็นจริงในM :
คำจำกัดความนี้ปรากฏครั้งแรกใน Tarski, Vaught (1957) [ 1 ] ดังนั้นจึงสรุป ได้ ว่าNเป็นโครงสร้างย่อยของM
ถ้าNเป็นโครงสร้างย่อยของMแล้ว ทั้งNและMสามารถตีความได้ว่าเป็นโครงสร้างในรูปแบบลายเซ็นσ Nซึ่งประกอบด้วยσพร้อมกับสัญลักษณ์ค่าคงที่ใหม่สำหรับแต่ละองค์ประกอบของ Nดังนั้นNจะเป็นโครงสร้างย่อยพื้นฐานของMก็ต่อเมื่อNเป็นโครงสร้างย่อยของMและNกับMมีความสมมูลกันในระดับพื้นฐานในฐานะโครงสร้าง σ N
ถ้าNเป็นโครงสร้างย่อยพื้นฐานของMเราจะเขียนN ∈ Mและกล่าวว่าMเป็นส่วนขยายพื้นฐานของN : M ∈ N
ทฤษฎีบท Löwenheim–Skolemแบบลงล่างให้โครงสร้างย่อยพื้นฐานที่นับได้สำหรับโครงสร้างลำดับที่หนึ่งอนันต์ใดๆ ที่มีลายเซ็นที่นับได้มากที่สุด ในขณะที่ทฤษฎีบท Löwenheim–Skolem แบบขึ้นบนให้ส่วนขยายพื้นฐานของโครงสร้างลำดับที่หนึ่งอนันต์ใดๆ ที่มีขนาดใหญ่ตามอำเภอใจ
การทดสอบ Tarski–Vaught
การทดสอบ Tarski–Vaught (หรือเกณฑ์ Tarski–Vaught ) เป็นเงื่อนไขที่จำเป็นและเพียงพอสำหรับโครงสร้างย่อยNของโครงสร้างMที่จะเป็นโครงสร้างย่อยพื้นฐาน การทดสอบนี้มีประโยชน์สำหรับการสร้างโครงสร้างย่อยพื้นฐานของโครงสร้างขนาดใหญ่
ให้Mเป็นโครงสร้างลายเซ็นσและNเป็นโครงสร้างย่อยของMแล้วNเป็นโครงสร้างย่อยพื้นฐานของMก็ต่อเมื่อสำหรับสูตรลำดับที่หนึ่งφ ( x , y 1 , …, y n ) เหนือσและองค์ประกอบb 1 , …, b n ทั้งหมด จากNถ้าM x φ ( x , b 1 , …, b n ) แล้วจะมีองค์ประกอบaในNที่M φ ( a , b 1 , …, b n ) [ 2 ]
การฝังข้อมูลขั้นพื้นฐาน
การ ฝัง โครงสร้างNลงในโครงสร้างM ที่มีลายเซ็น σเดียวกันอย่างง่ายคือ แผนที่h : N → M โดยที่สำหรับทุก สูตรσอันดับแรกφ ( x 1 , …, x n ) และทุกองค์ประกอบa 1 , …, a nของ N
- N φ ( a 1 , …, a n ) ก็ต่อเมื่อM φ ( h ( a 1 ), …, h ( a n ))
การฝังตัวพื้นฐานทุกแบบเป็น โฮโม มอ ร์ฟิซึมที่แข็งแกร่งและเหนี่ยวนำให้เกิดไอโซมอร์ฟิซึมระหว่างNกับโครงสร้างย่อยพื้นฐานของM
การฝังตัวแบบพื้นฐาน (Elementary embeddings) เป็นแผนที่ที่สำคัญที่สุดในทฤษฎีแบบจำลอง ในทฤษฎีเซตการฝังตัวแบบพื้นฐานที่มีโดเมนเป็นV (เอกภพของทฤษฎีเซต) มีบทบาทสำคัญในทฤษฎีของจำนวน เชิง คาร์ดินัลขนาดใหญ่ (ดูเพิ่มเติมที่จุดวิกฤต )
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ ความเท่าเทียมกันขั้นพื้นฐาน
ในทฤษฎีแบบจำลองซึ่งเป็นสาขาหนึ่งของตรรกศาสตร์ทางคณิตศาสตร์โครงสร้าง สองแบบMและN ที่มี ลายเซ็นσเดียวกันจะเรียกว่าสมมูลกันโดยพื้นฐาน หาก โครงสร้าง ทั้งสองนั้นสอดคล้องกับ...
โครงสร้างที่เทียบเท่ากันในระดับพื้นฐาน
โครงสร้าง M และ N สองโครงสร้าง ที่มีลายเซ็น σ เดียวกันนั้น จะ สมมูลกันโดยพื้นฐานก็ ต่อเมื่อประโยคอันดับหนึ่ง (สูตรที่ไม่มีตัวแปรอิสระ) ทุกประโยคบน σ เป็นจริงใน M ก็ต่อเมื่อเป็นจริงใน N เท่านั้น กล่าว คือ ถ้า M และ N มีทฤษฎีอันดับหนึ่ง ที่สมบูรณ์ เหมือนกัน ถ้า...
โครงสร้างย่อยพื้นฐานและส่วนขยายพื้นฐาน
N เป็น โครงสร้างย่อยพื้นฐาน หรือ แบบจำลองย่อยพื้นฐาน ของ M ถ้า N และ M เป็นโครงสร้างที่มี ลายเซ็น σ เดียวกัน โดยที่สำหรับ สูตร σ อันดับแรกทั้งหมด φ ( x 1 , …, x n ) ที่มีตัวแปรอิสระ x 1 , …, x n และองค์ประกอบทั้งหมด a 1 , …, a n ของ N นั้น φ ( a 1 , …, a n )...
การทดสอบ Tarski–Vaught
การ ทดสอบ Tarski–Vaught (หรือ เกณฑ์ Tarski–Vaught ) เป็นเงื่อนไขที่จำเป็นและเพียงพอสำหรับโครงสร้างย่อย N ของโครงสร้าง M ที่จะเป็นโครงสร้างย่อยพื้นฐาน การทดสอบนี้มีประโยชน์สำหรับการสร้างโครงสร้างย่อยพื้นฐานของโครงสร้างขนาดใหญ่