ความสัมพันธ์ทวิภาคแบบถ่ายทอด วี ที อี
สมมาตร แอนติสมมาตร เชื่อมต่อแล้ว มีเหตุผลที่ดี ได้เข้าร่วมแล้ว ได้พบปะแล้ว สะท้อนกลับ ไร้ปฏิกิริยาตอบสนอง ไม่สมมาตร โททอลเซมิคอนเน็กซ์ ต่อต้านปฏิกิริยาสะท้อน ความสัมพันธ์สมมูล วาย ✗ ✗ ✗ ✗ ✗ วาย ✗ ✗ สั่งซื้อล่วงหน้า(กึ่งสั่งซื้อ) ✗ ✗ ✗ ✗ ✗ ✗ วาย ✗ ✗ คำสั่งซื้อบางส่วน ✗ วาย ✗ ✗ ✗ ✗ วาย ✗ ✗ ยอดสั่งซื้อล่วงหน้าทั้งหมด ✗ ✗ วาย ✗ ✗ ✗ วาย ✗ ✗ คำสั่งซื้อทั้งหมด ✗ วาย วาย ✗ ✗ ✗ วาย ✗ ✗ การสั่งซื้อล่วงหน้า ✗ ✗ วาย วาย ✗ ✗ วาย ✗ ✗ การจัดลำดับแบบกึ่งดี ✗ ✗ ✗ วาย ✗ ✗ วาย ✗ ✗ การจัดระเบียบที่ดี ✗ วาย วาย วาย ✗ ✗ วาย ✗ ✗ โครงตาข่าย ✗ วาย ✗ ✗ วาย วาย วาย ✗ ✗ ข้อต่อเซมิแลตติซ ✗ วาย ✗ ✗ วาย ✗ วาย ✗ ✗ มีท-เซมิแลตติซ ✗ วาย ✗ ✗ ✗ วาย วาย ✗ ✗ ลำดับบางส่วนที่เข้มงวด ✗ วาย ✗ ✗ ✗ ✗ ✗ วาย วาย คำสั่งอ่อนที่เข้มงวด ✗ วาย ✗ ✗ ✗ ✗ ✗ วาย วาย ลำดับที่เข้มงวดทั้งหมด ✗ วาย วาย ✗ ✗ ✗ ✗ วาย วาย สมมาตร แอนติสมมาตร เชื่อมต่อแล้ว มีเหตุผลที่ดี ได้เข้าร่วมแล้ว ได้พบปะแล้ว สะท้อนกลับ ไร้ปฏิกิริยาตอบสนอง ไม่สมมาตร คำจำกัดความสำหรับทุกคนและ${\displaystyle a,b}$${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ และ }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ หรือ }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
วายเครื่องหมาย * แสดงว่าคุณสมบัติของคอลัมน์นั้นเป็นจริงเสมอสำหรับพจน์ของแถวนั้น (ทางซ้ายสุด) ในขณะที่ เครื่องหมาย ✗แสดงว่าคุณสมบัตินั้นไม่ได้รับการรับประกันโดยทั่วไป (อาจเป็นจริงหรือไม่ก็ได้) ตัวอย่างเช่น ความสัมพันธ์สมมูลทุกความสัมพันธ์เป็นสมมาตร แต่ไม่จำเป็นต้องเป็นปฏิสมมาตรจะแสดงด้วย * ในคอลัมน์ "สมมาตร" และ เครื่องหมาย ✗ในคอลัมน์ "ปฏิสมมาตร" ตามลำดับ วาย โดยปริยายแล้ว นิยามทั้งหมดกำหนดให้ความสัมพันธ์เอกพันธุ์ ต้องเป็นแบบถ่ายทอดได้ กล่าวคือ สำหรับทุกถ้าและแล้ว นิยามของคำศัพท์อาจต้องการคุณสมบัติเพิ่มเติมที่ไม่ได้ระบุไว้ในตารางนี้ ${\displaystyle R}$${\displaystyle a,b,c,}$${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle aRc.}$

ในทางคณิตศาสตร์ความสัมพันธ์ทวิภาค R เรียกว่ามีรากฐานที่ดี (หรือมีรากฐานที่ดีหรือมีรากฐาน ) ^{[ 1 ]}บนเซตหรือโดยทั่วไปบนคลาสX ถ้า เซตย่อยที่ไม่ว่าง ทุก เซต (หรือคลาสย่อย) S ⊆ Xมีองค์ประกอบขั้นต่ำเมื่อเทียบกับRกล่าวคือ มีm ∈ S อยู่ เช่นนั้นสำหรับทุกs ∈ Sจะไม่มีs R mในทางที่เป็นทางการมากขึ้น ความสัมพันธ์จะมีรากฐานที่ดีถ้า: ผู้เขียนบางคนรวมเงื่อนไขเพิ่มเติมว่าRมีลักษณะคล้ายเซต กล่าวคือ องค์ประกอบที่น้อยกว่าองค์ประกอบที่กำหนดใดๆ จะประกอบเป็นเซต $${\displaystyle (\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}$$

ในทำนองเดียวกัน สมมติว่าสัจพจน์ของการเลือกที่ขึ้นอยู่กันความสัมพันธ์จะถือว่ามีรากฐานที่ดีเมื่อไม่มีสายโซ่ที่ลดลงอย่างไม่มีที่สิ้นสุดหมายความว่าไม่มีลำดับอนันต์x ₀ , x ₁ , x ₂ , ...ขององค์ประกอบของXที่x _{n +1} R x _nสำหรับทุกจำนวน^{ธรรมชาติ} n [ ^{2 ] [ 3 ]}

ในทฤษฎีลำดับ ลำดับ บางส่วนจะเรียกว่ามีรากฐานที่ดี (well-founded order) ถ้าลำดับเข้มงวด ที่สอดคล้องกัน เป็นความสัมพันธ์ที่มีรากฐานที่ดี (well-founded relation) และถ้าลำดับนั้นเป็นลำดับสมบูรณ์ (total order ) ก็จะเรียกว่ามีรากฐานที่ดี (well-order )

ในทฤษฎีเซตเซตxเรียกว่าเซตที่มีรากฐานดี (well-founded set)ถ้า ความสัมพันธ์ ของการเป็นสมาชิกของเซตนั้นมีรากฐานดีบนการปิดแบบถ่ายทอด (transitive closure)ของx สัจพจน์ของความสม่ำเสมอ (agxiom of regularity ) ซึ่งเป็นหนึ่งในสัจพจน์ของทฤษฎีเซตของ Zermelo–Fraenkelกล่าวว่า เซตทั้งหมดมีรากฐานดี

ความสัมพันธ์R เรียก ว่าเป็นความสัมพันธ์ที่มีรากฐานดีแบบผกผันความสัมพันธ์ที่มีรากฐานดีแบบขึ้นหรือความสัมพันธ์แบบโนเธอร์เรียนบนXถ้าความสัมพันธ์ผกผันR ⁻¹เป็นความสัมพันธ์ที่มีรากฐานดีบนXในกรณีนี้Rยังกล่าวได้ว่าตรงตามเงื่อนไขลูกโซ่ขึ้น ด้วย ในบริบทของ ระบบ การเขียนใหม่ความสัมพันธ์แบบโนเธอร์เรียนยังเรียกว่าความสัมพันธ์ที่ สิ้นสุด ด้วย

เหตุผลสำคัญที่ทำให้ความสัมพันธ์ที่มีรากฐานดีน่าสนใจก็คือสามารถใช้การเหนี่ยวนำแบบอนันต์ กับความสัมพันธ์เหล่านี้ได้ กล่าวคือ ถ้า ( X , R ) เป็นความสัมพันธ์ที่มีรากฐานดี และP ( x )เป็นคุณสมบัติบางอย่างของสมาชิกในXและเราต้องการแสดงว่า

P ( x ) เป็นจริงสำหรับ องค์ประกอบ xทั้งหมดของ X

เพียงพอที่จะแสดงให้เห็นว่า:

ถ้าxเป็นสมาชิกของXและP ( y )เป็นจริงสำหรับทุกyที่y R xแล้วP ( x )ก็ต้องเป็นจริงด้วย

นั่นคือ $${\displaystyle (\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).}$$

บางครั้งการเหนี่ยวนำที่มีพื้นฐานที่ดีเรียกว่าการเหนี่ยวนำแบบ Noetherian ^{[ 4 ]}ตามชื่อของEmmy Noether

เช่นเดียวกับการอุปนัย ความสัมพันธ์ที่มีรากฐานที่ดีก็สนับสนุนการสร้างวัตถุโดยการเรียกซ้ำแบบอนันต์ เช่นกัน ให้( X , R )เป็นความสัมพันธ์ที่มีรากฐานที่ดีแบบเซต และ Fเป็นฟังก์ชันที่กำหนดวัตถุF ( x , g )ให้กับแต่ละคู่ขององค์ประกอบx ∈ Xและฟังก์ชันgบนเซต{ y : y ∈ R x }ของตัวก่อนหน้าของxแล้วจะมีฟังก์ชันG ที่ไม่ซ้ำกันเพียงฟังก์ชันเดียว ซึ่งสำหรับทุกx ∈ X$${\displaystyle G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right).}$$

กล่าวคือ หากเราต้องการสร้างฟังก์ชันGบนXเราสามารถกำหนดG ( x )โดยใช้ค่าของG ( y )สำหรับy ∈ R xได้

ยกตัวอย่างเช่น พิจารณาความสัมพันธ์ที่มีรากฐานดี( N , S )โดยที่Nคือเซตของจำนวนธรรมชาติ ทั้งหมด และSคือกราฟของฟังก์ชันตัวสืบทอดx ↦ x + 1การอุปมานบนSคือการอุปมานทางคณิตศาสตร์ แบบปกติ และการเวียนเกิดบนSจะให้การเวียนเกิดแบบดั้งเดิมถ้าเราพิจารณาความสัมพันธ์ลำดับ( N , <)เราจะได้การอุปมานที่สมบูรณ์และการเวียนเกิดแบบลำดับค่าข้อความที่ว่า( N , <)มีรากฐานดีนั้นเรียกอีกอย่างว่าหลักการจัดลำดับที่ดี

นอกจากนี้ยังมีกรณีพิเศษที่น่าสนใจอื่นๆ ของการเหนี่ยวนำแบบมีรากฐานที่ดี เมื่อความสัมพันธ์แบบมีรากฐานที่ดีคือการเรียงลำดับตามปกติบนกลุ่มของจำนวนเชิงอันดับ ทั้งหมด เทคนิคนี้เรียกว่าการเหนี่ยวนำแบบอนันต์เมื่อเซตแบบมีรากฐานที่ดีคือเซตของโครงสร้างข้อมูลที่กำหนดแบบเวียนซ้ำ เทคนิคนี้เรียกว่าการเหนี่ยวนำเชิงโครงสร้างเมื่อความสัมพันธ์แบบมีรากฐานที่ดีคือการเป็นสมาชิกของเซตบนกลุ่มสากล เทคนิคนี้เรียกว่าการเหนี่ยวนำแบบ ∈โปรดดูบทความเหล่านั้นสำหรับรายละเอียดเพิ่มเติม

ความสัมพันธ์ที่มีพื้นฐานมั่นคงแต่ไม่ได้เป็นระเบียบเรียบร้อยโดยสมบูรณ์ ได้แก่:

• จำนวนเต็ม บวก{1, 2, 3, ...}โดยมีลำดับที่กำหนดโดยa < bก็ต่อเมื่อa หาร b ลงตัว และa ≠ b
• เซตของสตริง จำกัดทั้งหมดที่ สร้างขึ้นจากตัวอักษรคงที่ โดยมีลำดับที่กำหนดโดยs < tก็ต่อเมื่อsเป็นสตริงย่อยแท้ของt
• เซตN × Nของคู่จำนวนธรรมชาติเรียงลำดับตาม( n ₁ , n ₂ ) < ( m ₁ , m ₂ )ก็ต่อเมื่อn ₁ < m ₁และn ₂ < m ₂
• ทุกคลาสที่มีสมาชิกเป็นเซต จะมีความสัมพันธ์ ∈ ("เป็นสมาชิกของ") นี่คือสัจพจน์ของความสม่ำเสมอ
• โหนดของกราฟทิศทางแบบ ไม่มีวงจรจำกัดใดๆ โดยที่ความสัมพันธ์Rถูกกำหนดไว้เช่นนั้นa ∈ R bก็ต่อเมื่อมีเส้นเชื่อมจากaไปยังb

ตัวอย่างของความสัมพันธ์ที่ไม่ถูกต้องตามหลักการ ได้แก่:

• จำนวนเต็มลบ{−1, −2, −3, ...}เรียงลำดับตามปกติ เนื่องจากเซตย่อยที่ไม่จำกัดขอบเขตใดๆ ก็ไม่มีสมาชิกที่เล็กที่สุด
• เซตของสตริงที่สร้างขึ้นจากตัวอักษรจำกัดที่มีมากกว่าหนึ่งองค์ประกอบ ภายใต้ลำดับปกติ (ตาม ลำดับ พจนานุกรม ) เนื่องจากลำดับ"B" > "AB" > "AAB" > "AAAB" > ...เป็นสายโซ่ที่ลดลงอย่างไม่มีที่สิ้นสุด ความสัมพันธ์นี้จึงไม่สามารถพิสูจน์ได้ว่ามีรากฐานที่ดี แม้ว่าเซตทั้งหมดจะมีองค์ประกอบต่ำสุด คือ สตริงว่าง
• เซตของจำนวนตรรกยะ (หรือจำนวนจริง ) ที่ไม่เป็นลบภายใต้การเรียงลำดับมาตรฐาน เนื่องจากตัวอย่างเช่น เซตย่อยของจำนวนตรรกยะ (หรือจำนวนจริง) ที่เป็นบวกไม่มีค่าต่ำสุด

ถ้า( X , <)เป็นความสัมพันธ์ที่มีรากฐานที่ดี และxเป็นสมาชิกของXแล้ว ลำดับการเรียงจากมากไปน้อยที่เริ่มต้นจากxจะมีค่าจำกัด แต่ไม่ได้หมายความว่าความยาวของลำดับเหล่านั้นจะมีขอบเขตเสมอไป พิจารณาตัวอย่างต่อไปนี้: ให้Xเป็นการรวมกันของจำนวนเต็มบวกที่มีสมาชิกใหม่ ω ซึ่งมีค่ามากกว่าจำนวนเต็มใดๆ แล้วXเป็นเซตที่มีรากฐานที่ดี แต่จะมีลำดับการเรียงจากมากไปน้อยที่เริ่มต้นจาก ω ซึ่งมีความยาวมาก (จำกัด) ตามอำเภอใจ ลำดับω, n − 1, n − 2, ..., 2, 1มีความยาวnสำหรับn ใด ๆ

บทตั้งการยุบตัวของ Mostowskiบ่งชี้ว่าการเป็นสมาชิกของเซตเป็นสากลใน ความสัมพันธ์ที่มีรากฐานดีแบบ ขยาย : สำหรับความสัมพันธ์ที่มีรากฐานดีแบบเซตใดๆRบนคลาสXที่เป็นแบบขยาย จะมีคลาสC อยู่ เช่นนั้น( X , R )เป็นไอโซมอร์ฟิกกับ( C , ∈ )

ความสัมพันธ์Rเรียกว่าเป็นความสัมพันธ์สะท้อนกลับ (reflexive relation) ถ้าa R aเป็นจริงสำหรับทุกค่า aในโดเมนของความสัมพันธ์นั้น ความสัมพันธ์สะท้อนกลับทุกความสัมพันธ์บนโดเมนที่ไม่ว่างเปล่าจะมีลำดับการลดลงที่ไม่มีที่สิ้นสุด เพราะลำดับคงที่ใดๆ ก็เป็นลำดับการลดลงเช่นกัน ตัวอย่างเช่น ในจำนวนธรรมชาติที่มีลำดับปกติ ≤ เราจะได้1 ≥ 1 ≥ 1 ≥ ...เพื่อหลีกเลี่ยงลำดับการลดลงที่ไม่สำคัญเหล่านี้ เมื่อทำงานกับลำดับบางส่วน ≤ มักจะใช้คำจำกัดความของความถูกต้องตามหลักการ (well-foundedness) (อาจโดยปริยาย) กับความสัมพันธ์ทางเลือก < ซึ่งกำหนดไว้ว่าa < bก็ต่อเมื่อa ≤ bและa ≠ bโดยทั่วไปแล้ว เมื่อทำงานกับลำดับก่อนหน้า ≤ มักจะใช้ความสัมพันธ์ < ซึ่งกำหนดไว้ว่าa < bก็ต่อเมื่อa ≤ bและb ≰ aในบริบทของจำนวนธรรมชาติ หมายความว่าความสัมพันธ์ < ซึ่งถูกต้องตามหลักการ จะถูกใช้แทนความสัมพันธ์ ≤ ซึ่งไม่ถูกต้องตามหลักการ ในบางตำรา นิยามของความสัมพันธ์ที่มีพื้นฐานมั่นคงจะถูกเปลี่ยนแปลงจากนิยามข้างต้นเพื่อรวมเอาธรรมเนียมเหล่านี้เข้าไปด้วย

• https://ncatlab.org/nlab/show/well-founded+coalgebra