관계에 대한 흥정

Question

관계의 증명 속성에 관한 질문이 있습니다. 질문 : R과 S (R과 S가 서로 다른 관계 임)가 전이성이 있으면 R 유니온 S가 전 이적이라는 것을 어떻게 증명할 수 있습니까?

답은 실제로 거짓이며 카운터 예제가 책의 해답으로 주어집니다.

나는 반례가이 책에서 설명한대로 어떻게 작용하는지 이해하지만, 내가 이해할 수없는 것은 진술이 실제로 거짓이라는 결론에 얼마나 정확하게 도달했는지이다.

기본적으로 R과 S의 모든 값 (x, y, z)에 대해 (x, y)가 R이고 (y, z)가 R 인 경우 x, z)는 R에 속합니다. 왜냐하면 R은 전이 적이기 때문입니다. 그리고 (x, y)가 S에 있고 (y, z)가 S에 있으면, S가 전이 적이기 때문에 (x, z)는 S에 있습니다. (x, z)는 R과 S에 있기 때문에, 교집합은 참입니다. 그러나 왜 R과 S의 결합도 사실이 아니겠습니까?

"(x, z)가 R과 S 모두에 있기 때문에 (x, z)가 R 또는 S 일 수 있기 때문에 증명이 끝날 수 없기 때문입니까?" 근본적으로, 증명은 결국 OR 성명서로 끝날 수 없다는 것인가?

Answer 1

나는 반례가이 책에서 설명한대로 어떻게 작용하는지 이해하지만, 나는 그들이 진술이 실제로 거짓이라는 결론에 얼마나 정확하게 도달했는지 이해하지 못한다.

은 (아마도 유효) 반례가있다 감안할 때, 문 은 거짓으로 있습니다. 반증에 증거를 적용하려고하면 오류를 알 수 있습니다.

그것은 이 아님을 의미하지 않습니다. 두 전이 관계의 결합 자체가 전 이적 인 경우입니다. 실제로, 자신과의 전 이적 관계의 조합 또는 less-than과 less-than-or-equal-to의 합집합 (이는 합리적인 정의에 대해 less-than-or-equal-to과 같습니다)과 같은 명백한 예가 있습니다. 그러나 원래의 진술은 에 대한 모든 경우 두 전이 관계에 해당한다고 주장합니다. 하나의 반례가 그것을 반증합니다. 귀하가 진술서의 (유효한) 증거를 제공 할 수 있다면, 당신은 역설을 발견했을 것입니다. 이것은 일반적으로 수학자가 역설을 제거하기 위해 시스템의 공리를 재평가하게 만듭니다. 이 경우에는 역설이 없습니다.

과 S의 합집합이라고합시다 (간단히하기 위해 도메인은 범위와 같고 두 세트 모두 동일한 것으로 가정합니다). 당신이 증명하려고하는 것은 만약 xTy과 yTz이라면 xTz 일 것입니다. (x는, z는) R 이후 R에

(X, Y)가 R과 (Y, Z)에 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이 아닙니다. 당신의 교과서는 아마도 더 자연스런 반례를 줄지 모르지만, 이것이 어설 션이 실패 할 수있는 원인을 잘 이해하고 있다고 생각합니다.