關係傳遞性

Question

我有關於證明關係性質的問題。 問題是這樣的： 我該如何去證明，如果R和S（R和S都是不同的關係）是傳遞的，那麼R union S是傳遞的？

答案實際上是FALSE，然後在本書中給出了一個反例的解決方案。

我明白反例如何在書中解釋，但我不明白的是，他們究竟是如何得出結論的，即該陳述實際上是錯誤的。 （x，y）在R中，（y，z）在R中，（R，S）中的所有值（x，y，z）因爲R是傳遞性的，所以x，z）在R中。如果（x，y）在S中且（y，z）在S中，則由於S是傳遞性的，（x，z）在S中。由於（x，z）在R和S中，交集是真實的。但爲什麼R和S的聯合也不是真的？

是否因爲證明不能以「既（R，S）同時在R和S中，（X，Z）可以在R或S中」結束？基本上，證明不能以OR語句結束？

Answer 1

我明白反例是如何在書中解釋的，但我不明白的是，他們究竟是如何得出結論，說明其實是錯誤的。

假設有一個（可能是有效的）反，聲明有是假的。試圖將您的證明應用於反例可以幫助揭示錯誤。

這並不是說它是從來沒有兩個傳遞關係的聯合本身是傳遞的情況。事實上，有一些明顯的例子，如與其自身的傳遞關係或less-than和less-than-or-equal-to（對於任何合理的定義等於less-than-or-equal-to）的聯合。但原來的聲明斷言這種情況是任何兩個傳遞關係。一個反例證明了這一點。如果你能提供一份（有效的）聲明證明，你就會發現一個矛盾。這通常會導致數學家重新評估系統的公理以消除悖論。在這種情況下，沒有悖論。

讓T成爲R和S的聯合（爲了簡單起見，我們假設域等於範圍，並且它們都是相同的集合）。你試圖證明的是，如果xTy和yTz，那麼它必然是xTz的情況。當你的證據大綱的一部分，聲明如下：

如果（X，Y）是R和（Y，Z）是R，（X，Z）是因爲R R是傳遞

這顯然是對的，因爲它只是傳遞性的定義。正如你指出的那樣，它可以用來證明兩個傳遞關係交集的傳遞性。然而，由於T是工會，沒有理由認爲xRy;它可能只是xSy。既然你不能證明先行詞（那xRy和yRz），結果（那xRz）是不相關的。同樣，你不能顯示xSz。如果你不能顯示xRz或xSz，沒有理由相信xTz。

這意味着這種情況給出了一個反例的陳述：當傳遞對的一半隻來自R而另一隻來自S。作爲一個簡單的，做作，例如，定義的關係通過所述一組{1,2,3}：

R={(1,2)}
S={(2,3)}

顯然，兩個R和S是可傳遞（因爲不存在x, y, z使得xRy and yRz或xSy and ySz）。在另一方面，

T={(1,2),(2,3)}

是不可傳遞的。雖然1T2（因爲1R2）和2T3（因爲2S3），它並不是1T3。你的教科書可能會給出一個更自然的反例，但我認爲這可以很好地理解可能導致斷言失敗的原因。