Advertisement
Guest User

Untitled

a guest
Nov 11th, 2019
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. Theorem “Intersection of 𝕀 and ×”: 𝕀 B ∩ (C × D) = 𝕀 (B ∩ C ∩ D)
  2. Proof:
  3. Using “Relation extensionality”:
  4. Subproof for `∀ x • ∀ y • x ⦗ 𝕀 B ∩ (C × D) ⦘ y ≡ x ⦗ 𝕀 (B ∩ C ∩ D) ⦘ y`:
  5. For any `x`, `y`:
  6. x ⦗ 𝕀 B ∩ (C × D) ⦘ y
  7. ≡⟨ “Relation intersection” ⟩
  8. x ⦗ 𝕀 B ⦘ y ∧ x ⦗ (C × D) ⦘ y
  9. ≡⟨ “Relationship via 𝕀” ⟩
  10. x = y ∈ B ∧ x ⦗ (C × D) ⦘ y
  11. ≡⟨ “Definition of `_⦗_⦘_`”, “Membership in ×” ⟩
  12. x = y ∈ B ∧ x ∈ C ∧ y ∈ D
  13. ≡⟨ Substitution, “Replacement” ⟩
  14. x = y ∧ y ∈ B ∧ (z ∈ C)[z ≔ y] ∧ y ∈ D
  15. ≡⟨ Substitution ⟩
  16. x = y ∧ y ∈ B ∧ y ∈ C ∧ y ∈ D
  17. ≡⟨ “Intersection” ⟩
  18. x = y ∧ y ∈ B ∩ C ∩ D
  19. ≡⟨ “Relationship via 𝕀” ⟩
  20. x ⦗ 𝕀 (B ∩ C ∩ D) ⦘ y
  21.  
  22.  
  23. Theorem “Difference of 𝕀 and ×”: 𝕀 B - (C × D) = 𝕀 (B - (C ∩ D))
  24. Proof:
  25. Using “Relation extensionality”:
  26. Subproof for `∀ x • ∀ y • x ⦗ 𝕀 B - (C × D) ⦘ y ≡ x ⦗ 𝕀 (B - (C ∩ D)) ⦘ y`:
  27. For any `x`, `y`:
  28. x ⦗ 𝕀 B - (C × D) ⦘ y
  29. ≡⟨ “Relation difference” ⟩
  30. x ⦗ 𝕀 B ⦘ y ∧ ¬ (x ⦗ (C × D) ⦘ y)
  31. ≡⟨ “Relationship via 𝕀”, “Definition of `_⦗_⦘_`”, “Membership in ×” ⟩
  32. x = y ∧ y ∈ B ∧ ¬ (x ∈ C ∧ y ∈ D)
  33. ≡⟨ “De Morgan”, “Complement” ⟩
  34. (x = y ∧ y ∈ B) ∧ (x ∈ ~ C ∨ y ∈ ~ D)
  35. ≡⟨ “Distributivity of ∧ over ∨” ⟩
  36. (x = y ∧ y ∈ B ∧ x ∈ ~ C) ∨ (x = y ∧ y ∈ B ∧ y ∈ ~ D)
  37. ≡⟨ Substitution, “Replacement” ⟩
  38. (x = y ∧ y ∈ B ∧ (z ∈ ~ C)[z ≔ y]) ∨ (x = y ∧ y ∈ B ∧ y ∈ ~ D)
  39. ≡⟨ Substitution ⟩
  40. (x = y ∧ y ∈ B ∧ (y ∈ ~ C)) ∨ (x = y ∧ y ∈ B ∧ y ∈ ~ D)
  41. ≡⟨ “Distributivity of ∧ over ∨” ⟩
  42. (x = y ∧ y ∈ B) ∧ (y ∈ ~ C ∨ y ∈ ~ D)
  43. ≡⟨ “Complement”, “De Morgan” ⟩
  44. (x = y ∧ y ∈ B) ∧ ¬ (y ∈ C ∧ y ∈ D)
  45. ≡⟨ “Intersection” ⟩
  46. x = y ∧ y ∈ B ∧ ¬ (y ∈ C ∩ D)
  47. ≡⟨ “Set difference” ⟩
  48. x = y ∧ y ∈ B - (C ∩ D)
  49. ≡⟨ “Relationship via 𝕀” ⟩
  50. x ⦗ 𝕀 (B - (C ∩ D)) ⦘ y
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement