Advertisement
Guest User

Untitled

a guest
Nov 11th, 2019
425
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.09 KB | None | 0 0
  1. Theorem “Union of 𝕀 relations”: 𝕀 B ∪ 𝕀 C = 𝕀 (B ∪ C)
  2. Proof:
  3. Using “Relation extensionality”:
  4. Subproof for `∀ x • ∀ y • x ⦗ 𝕀 B ∪ 𝕀 C ⦘ y ≡ x ⦗ 𝕀 (B ∪ C) ⦘ y`:
  5. For any `x`, `y`:
  6. x ⦗ 𝕀 B ∪ 𝕀 C ⦘ y
  7. ≡⟨ “Relation union” ⟩
  8. x ⦗ 𝕀 B ⦘ y ∨ x ⦗ 𝕀 C ⦘ y
  9. ≡⟨ “Relationship via 𝕀” ⟩
  10. x = y ∈ B ∨ x = y ∈ C
  11. ≡⟨ “Reflexivity of ≡”, “Idempotency of ∧” ⟩
  12. (x = y ∧ y ∈ B) ∨ (x = y ∧ y ∈ C)
  13. ≡⟨ “Distributivity of ∧ over ∨” ⟩
  14. (x = y) ∧ ( y ∈ B ∨ y ∈ C )
  15. ≡⟨ “Union” ⟩
  16. x = y ∧ y ∈ B ∪ C
  17. ≡⟨ “Reflexivity of ≡” ⟩
  18. x = y ∈ (B ∪ C)
  19. ≡⟨ “Relationship via 𝕀” ⟩
  20. x ⦗ 𝕀 (B ∪ C) ⦘ y
  21.  
  22.  
  23. Theorem “Difference of 𝕀 relations”: 𝕀 B - 𝕀 C = 𝕀 (B - C)
  24. Proof:
  25. Using “Relation extensionality”:
  26. Subproof for `∀ x • ∀ y • x ⦗ 𝕀 B - 𝕀 C ⦘ y ≡ x ⦗ 𝕀 (B - C) ⦘ y`:
  27. For any `x`, `y`:
  28. x ⦗ 𝕀 B - 𝕀 C ⦘ y
  29. ≡⟨ “Relation difference” ⟩
  30. x ⦗ 𝕀 B ⦘ y ∧ ¬ (x ⦗ 𝕀 C ⦘ y)
  31. ≡⟨ “Relationship via 𝕀” ⟩
  32. x = y ∈ B ∧ ¬ (x = y ∈ C)
  33. ≡⟨ “Reflexivity of ≡” ⟩
  34. x = y ∧ y ∈ B ∧ ¬ (x = y ∧ y ∈ C)
  35. ≡⟨ “De Morgan”, “Complement” ⟩
  36. (x = y ∧ y ∈ B) ∧ (¬ (x = y) ∨ (y ∈ ~ C))
  37. ≡⟨ “Distributivity of ∧ over ∨” ⟩
  38. (x = y ∧ y ∈ B ∧ ¬ (x = y)) ∨ (x = y ∧ y ∈ B ∧ y ∈ ~ C)
  39. ≡⟨ “Contradiction”, “Zero of ∧”, “Identity of ∨” ⟩
  40. (x = y ∧ y ∈ B ∧ y ∈ ~ C)
  41. ≡⟨ “Complement” ⟩
  42. (x = y ∧ y ∈ B ∧ ¬ (y ∈ C))
  43. ≡⟨ “Set difference” ⟩
  44. (x = y ∧ y ∈ B - C)
  45. ≡⟨ “Relationship via 𝕀” ⟩
  46. x ⦗ 𝕀 (B - C) ⦘ y
  47.  
  48.  
  49.  
  50. Theorem “Set complement as difference”: ~ B = 𝐔 - B
  51. Proof:
  52. Using “Set extensionality”:
  53. Subproof for `∀ x • x ∈ ~ B ≡ x ∈ (𝐔 - B)`:
  54. For any `x`:
  55. x ∈ ~ B
  56. ≡⟨ “Complement” ⟩
  57. ¬ (x ∈ B)
  58. ≡⟨ “Identity of ∧” ⟩
  59. ¬ (x ∈ B) ∧ true
  60. ≡⟨ “Universal set” ⟩
  61. ¬ (x ∈ B) ∧ x ∈ 𝐔
  62. ≡⟨ “Set difference” ⟩
  63. x ∈ 𝐔 - B
  64.  
  65.  
  66.  
  67. Theorem “Difference of 𝕀 relations”: 𝕀 (~ B) = 𝕀 𝐔 - 𝕀 B
  68. Proof:
  69. Using “Relation extensionality”:
  70. Subproof for `∀ x • ∀ y • x ⦗ 𝕀 (~ B) ⦘ y ≡ x ⦗ 𝕀 𝐔 - 𝕀 B ⦘ y`:
  71. For any `x`, `y`:
  72. x ⦗ 𝕀 (~ B) ⦘ y
  73. ≡⟨ “Set complement as difference” ⟩
  74. x ⦗ 𝕀 (𝐔 - B) ⦘ y
  75. ≡⟨ “Difference of 𝕀 relations” ⟩
  76. x ⦗ 𝕀 𝐔 - 𝕀 B ⦘ y
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement