T.7 · Set images, equivalence relations and logical negation

학부 GRE 준비. 검토된 ETS 범위 내의 로컬 목표; 이는 공식 시험이나 점수 예측기가 아닌 독자적 교육 과정입니다.

필요 선행 지식: 집합 연산, 양자사, 함수 및 기초 증명법.

• 이미지 등식을 증명하고 포함 관계와 동등함을 구분하십시오
• 명시된 사례를 통해 반사성, 대칭성 및 추이성을 확인하십시오
• 범위를 변경하지 않고 함의 및 양자사 명제를 부정하십시오

원상(preimage): 출력이 특정 타겟 집합에 속하는 모든 입력의 집합입니다.

동치관계(equivalence relation): 반사적, 대칭적이며 추이적인 관계입니다.

f:X→Y이고 A⊆X일 때, 이미지 f(A)는 a가 A에 있을 때 모든 출력 f(a)의 집합입니다. 점은 f(A∪B)에 정확히 포함될 때 A 또는 B에서 유래하므로 f(A∪B)=f(A)∪f(B)입니다. A⊆B이면 f(A)⊆f(B)입니다. 교집합에 대해서는 f(A∩B)⊆f(A)∩f(B)만 자동으로 성립합니다. 같은 출력이 서로 다른 입력에서 올 수 있기 때문입니다. f(x)=x², A={−1}, B={1}을 사용하십시오; 왼쪽 이미지는 비어 있지만 오른쪽 교집합은 {1}입니다.

원상은 다르게 행동합니다. C⊆Y에 대해, 여기서 f⁻¹(C)는 f에 역함수가 없더라도 C로 보내지는 모든 입력의 집합을 나타냅니다. 두 원상에 대한 membership는 매우 동일한 입력이 두 타겟 집합 모두로 매핑됨을 의미합니다. 따라서 원상은 명시된 정의역/공정의역에 대해 합집합, 교집합 및 보집합을 보존합니다. 원상에 대한 정리를 이미지로 이전하지 마십시오. f가 단사(injective)이면, 같은 출력이 공통된 입력을 강제하므로 이미지 교집합도 동등해집니다.

A relation R on X is reflexive when xRx for every x, symmetric when xRy implies yRx, and transitive when xRy and yRz imply xRz. All three make an equivalence relation; its classes partition X. On integers, xRy when x and y have the same remainder modulo four gives four classes. The relation |x−y|≤1 is reflexive and symmetric but not transitive: 0R1 and 1R2 while 0 is not related to 2. Checking only a diagram or two properties is insufficient.

함의 P⇒Q는 P가 참이고 Q가 거짓일 때에만 거짓입니다. 따라서 P⇒(Q∧R)의 부정은 ¬P⇒(¬Q∧¬R)이 아닌 P∧(¬Q∨¬R)입니다. “모든 x는 성질 A를 가진다”의 부정은 “A를 가지 않는 x가 존재한다”이며, “x가 존재한다”의 부정은 “모든 x는 그렇지 않다”입니다. 반례는 보편적 주장을 반박할 수 있지만, 예시는 이를 증명할 수 없습니다. 개별적으로 부정할 때 양자사의 순서는 유지됩니다: ¬(∀x∃y S(x,y))는 ∃x∀y ¬S(x,y)입니다.

f가 a와 b를 모두 라벨 L에 매핑한다고 하자. A={a}, B={b}이라 하면, f(A∩B)=∅이지만 f(A)∩f(B)={L}이다. R에서 x=y 또는 x=−y로 정의된 xRy는 반사성과 대칭성이 직접 따르며, 두 번의 부호 변경을 해도 z=±x이 되어 추이성을 증명한 다. classes는 {x,−x}이며, {0}는aban singleton이다. “저장된 모든 파일에는 해시가 있다”라는 명제가 거짓이라는 것은 적어도 하나의 저장된 파일에는 해시가 없다는 것을 의미하며, 모든 파일에 해시가 없다는 것을 의미하지는 않는다.

f⁻¹(C)는 역함수가 없는 원상 집합을 의미할 수 있습니다. 반사성과 대칭성을 가진 관계도 가연성이 실패할 수 있습니다. 부분식을 단순화하기 전에 전체 명제를 먼저 부정하십시오.

$f(A\cap B)\subseteq f(A)\cap f(B)$를 증명하십시오. 엄격한 포함 관계를 보여주는 예시를 제시하십시오. f에 대해 어떤 추가 가정이 imposition될 때 모든 A와 B에 대해 동등함이 따릅니까?

풀이 과정

$y=f(x)$가 $x\in A\cap B$에 대해 성립하면, x는 각 집합에 속하므로 y는 각 이미지에도 속합니다. 엄격함을 위해 서로 다른 a, b를 같은 c로 매핑하고 $A=\{a\}$, $B=\{b\}$을 취하십시오. 왼쪽 이미지는 비어 있고 오른쪽 교집합은 $\{c\}$입니다. If f is injective and $y=f(a)=f(b)$ with $a\in A,b\in B$, injectivity gives a=b in the intersection, proving reverse inclusion. Conversely the singleton example shows that equality for all pairs forces injectivity.

정수집합 위에서 $a-b$이 4로 나누어 떨어질 때 $aRb$을 정의하십시오. 이것이 동치관계임을 증명하고 각 동치류를 서술하십시오. 부정문: “모든 정수 n에 대해 n보다 큰 정수 m이 존재하여 성질 P를 만족한다.”

시도 후 확인

Reflexivity uses $a-a=0$; symmetry uses the negative of a multiple of four; transitivity uses the sum of two such multiples. Classes are the four residues modulo four; the class of a is $a+4\mathbb Z$. 부정은 다음과 같습니다: 어떤 정수 n이 존재하여, 모든 n보다 큰 정수 m은 P를 만족하지 않는다는 것입니다. 이는 $\exists n\,\forall m\,(m>n\Rightarrow\neg P(m))$과 동치입니다. P가 모든 정수에 대해 성립하지 않는다고 주장하지 않으며, 모든 m에 대해 m이 n 이하라고 주장하지도 않습니다.