Advertisement
Guest User

Untitled

a guest
Nov 12th, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.40 KB | None | 0 0
  1. Theorem “Relationship via 𝕀”: x ⦗ 𝕀 B ⦘ y ≡ x = y ∈ B
  2. Proof:
  3. x ⦗ 𝕀 B ⦘ y
  4. ≡⟨ “Definition of 𝕀” ⟩
  5. x ⦗ { x ❙ x ∈ B • ⟨ x , x ⟩ } ⦘ y
  6. ≡⟨ “Infix relationship” ⟩
  7. ⟨ x , y ⟩ ∈ { z ❙ z ∈ B • ⟨ z , z ⟩ }
  8. ≡⟨ “Set membership” ⟩
  9. ∃ z ❙ z ∈ B • ⟨ x , y ⟩ = ⟨ z , z ⟩
  10. ≡⟨ “Pair equality” ⟩
  11. ∃ z ❙ z ∈ B • x = z ∧ y = z
  12. ≡⟨ “Trading for ∃” ⟩
  13. ∃ z ❙ y = z • x = z ∧ z ∈ B
  14. ≡⟨ “One-point rule for ∃”, Substitution ⟩
  15. x = y ∈ B
  16.  
  17. Theorem “Intersection of 𝕀 relations”: 𝕀 B ∩ 𝕀 C = 𝕀 (B ∩ C)
  18. Proof:
  19. 𝕀 B ∩ 𝕀 C = 𝕀 (B ∩ C)
  20. ≡ ⟨ “Relation extensionality” ⟩
  21. ∀ x • ∀ y • x ⦗ 𝕀 B ∩ 𝕀 C ⦘ y ≡ x ⦗ 𝕀 (B ∩ C) ⦘ y
  22. ≡ ⟨ “Relationship via 𝕀” ⟩
  23. ∀ x • ∀ y • x ⦗ 𝕀 B ∩ 𝕀 C ⦘ y ≡ x = y ∧ y ∈ (B ∩ C)
  24. ≡ ⟨ “Relation intersection” ⟩
  25. ∀ x • ∀ y • x ⦗ 𝕀 B ⦘ y ∧ x ⦗ 𝕀 C ⦘ y ≡ x = y ∈ (B ∩ C)
  26. ≡ ⟨ “Intersection” ⟩
  27. ∀ x • ∀ y • x ⦗ 𝕀 B ⦘ y ∧ x ⦗ 𝕀 C ⦘ y ≡ x = y ∧ (y ∈ B ∧ y ∈ C)
  28. ≡ ⟨ Subproof:
  29. For any `x`, `y`:
  30. x ⦗ 𝕀 B ⦘ y ∧ x ⦗ 𝕀 C ⦘ y
  31. ≡ ⟨“Relationship via 𝕀”⟩
  32. x = y ∧ y ∈ B ∧ x = y ∧ y ∈ C
  33. ≡ ⟨ “Idempotency of ∧” ⟩
  34. x = y ∧ (y ∈ B ∧ y ∈ C)
  35. true
  36.  
  37.  
  38. Theorem “Union of 𝕀 relations”: 𝕀 B ∪ 𝕀 C = 𝕀 (B ∪ C)
  39. Proof:
  40. 𝕀 B ∪ 𝕀 C = 𝕀 (B ∪ C)
  41. ≡ ⟨ “Relation extensionality” ⟩
  42. ∀ x • ∀ y • x ⦗ 𝕀 B ∪ 𝕀 C ⦘ y ≡ x ⦗ 𝕀 (B ∪ C) ⦘ y
  43. ≡ ⟨ “Relationship via 𝕀” ⟩
  44. ∀ x • ∀ y • x ⦗ 𝕀 B ∪ 𝕀 C ⦘ y ≡ x = y ∧ y ∈ (B ∪ C)
  45. ≡ ⟨ “Relation union” ⟩
  46. ∀ x • ∀ y • x ⦗ 𝕀 B ⦘ y ∨ x ⦗ 𝕀 C ⦘ y ≡ x = y ∈ (B ∪ C)
  47. ≡ ⟨ “Union” ⟩
  48. ∀ x • ∀ y • x ⦗ 𝕀 B ⦘ y ∨ x ⦗ 𝕀 C ⦘ y ≡ x = y ∧ (y ∈ B ∨ y ∈ C)
  49. ≡ ⟨ Subproof:
  50. For any `x`, `y`:
  51. x ⦗ 𝕀 B ⦘ y ∨ x ⦗ 𝕀 C ⦘ y
  52. ≡ ⟨“Relationship via 𝕀”⟩
  53. (x = y ∧ y ∈ B) ∨ (x = y ∧ y ∈ C)
  54. ≡ ⟨ “Distributivity of ∧ over ∨” ⟩
  55. x = y ∧ (y ∈ B ∨ y ∈ C)
  56. true
  57.  
  58. Theorem “Difference of 𝕀 relations”: 𝕀 B - 𝕀 C = 𝕀 (B - C)
  59. Proof:
  60. 𝕀 B - 𝕀 C = 𝕀 (B - C)
  61. ≡ ⟨ “Relation extensionality” ⟩
  62. ∀ x • ∀ y • x ⦗ 𝕀 B - 𝕀 C ⦘ y ≡ x ⦗ 𝕀 (B - C) ⦘ y
  63. ≡ ⟨ “Relationship via 𝕀” ⟩
  64. ∀ x • ∀ y • x ⦗ 𝕀 B - 𝕀 C ⦘ y ≡ x = y ∧ y ∈ (B - C)
  65. ≡ ⟨ “Relation difference” ⟩
  66. ∀ x • ∀ y • x ⦗ 𝕀 B ⦘ y ∧ ¬ ( x ⦗ 𝕀 C ⦘ y ) ≡ x = y ∈ (B - C)
  67. ≡ ⟨ “Set difference” ⟩
  68. ∀ x • ∀ y • x ⦗ 𝕀 B ⦘ y ∧ ¬ ( x ⦗ 𝕀 C ⦘ y ) ≡ x = y ∧ (y ∈ B ∧ ¬ (y ∈ C))
  69. ≡ ⟨ Subproof:
  70. For any `x`, `y`:
  71. x ⦗ 𝕀 B ⦘ y ∧ ¬ ( x ⦗ 𝕀 C ⦘ y )
  72. ≡ ⟨“Relationship via 𝕀”⟩
  73. (x = y ∧ y ∈ B) ∧ ¬ (x = y ∧ y ∈ C)
  74. ≡ ⟨“De Morgan”, “Distributivity of ∧ over ∨”, “Contradiction”, “Identity of ∨” ⟩
  75. x = y ∧ (y ∈ B ∧ ¬ (y ∈ C))
  76. true
  77.  
  78. Theorem “Set complement as difference”: ~ B = 𝐔 - B
  79. Proof:
  80. ~ B = 𝐔 - B
  81. ≡ ⟨“Set extensionality”⟩
  82. ∀ e • e ∈ ~ B ≡ e ∈ 𝐔 - B
  83. ≡ ⟨“Set difference”, “Universal set”, “Identity of ∧”⟩
  84. ∀ e • e ∈ ~ B ≡ ¬ (e ∈ B)
  85. ≡ ⟨“Complement”⟩
  86. ∀ e • true — This is “True ∀ body”
  87.  
  88.  
  89. Theorem “Intersection of 𝕀 and ×”: 𝕀 B ∩ (C × D) = 𝕀 (B ∩ C ∩ D)
  90. Proof:
  91. Using “Relation extensionality”:
  92. For any `x`, `y`:
  93. x ⦗ 𝕀 B ∩ (C × D) ⦘ y
  94. ≡ ⟨ “Relation intersection” ⟩
  95. x ⦗ 𝕀 B ⦘ y ∧ x ⦗ (C × D) ⦘ y
  96. ≡ ⟨ “Relationship via 𝕀”, “Infix relationship” ⟩
  97. x = y ∧ y ∈ B ∧ ⟨ x , y ⟩ ∈ (C × D)
  98. ≡ ⟨ “Membership in ×” ⟩
  99. x = y ∧ y ∈ B ∧ x ∈ C ∧ y ∈ D
  100. ≡ ⟨ Substitution ⟩
  101. x = y ∧ (y ∈ B ∧ z ∈ C ∧ y ∈ D)[z ≔ x]
  102. ≡ ⟨ “Replacement”, Substitution ⟩
  103. x = y ∧ (y ∈ B ∧ y ∈ C ∧ y ∈ D)
  104. ≡ ⟨ “Intersection” ⟩
  105. x = y ∧ (y ∈ B ∩ C ∩ D)
  106. ≡ ⟨ “Relationship via 𝕀” ⟩
  107. x ⦗ 𝕀 (B ∩ C ∩ D) ⦘ y
  108.  
  109.  
  110. Theorem “Difference of 𝕀 and ×”: 𝕀 B - (C × D) = 𝕀 (B - (C ∩ D))
  111. Proof:
  112. Using “Relation extensionality”:
  113. For any `x`, `y`:
  114. x ⦗ 𝕀 B - (C × D) ⦘ y
  115. ≡ ⟨“Relation difference”⟩
  116. (( x ⦗ 𝕀 B ⦘ y ) ∧ ¬ ( x ⦗ (C × D) ⦘ y ))
  117. ≡ ⟨“Infix relationship”, “Relationship via 𝕀”, “Membership in ×”⟩
  118. x = y ∧ y ∈ B ∧ ¬ (x ∈ C ∧ y ∈ D)
  119. ≡ ⟨Substitution⟩
  120. x = y ∧ (y ∈ B ∧ ¬ (z ∈ C ∧ y ∈ D))[z ≔ x]
  121. ≡ ⟨“Replacement”, Substitution⟩
  122. x = y ∧ y ∈ B ∧ ¬ (y ∈ C ∧ y ∈ D)
  123. ≡ ⟨“Intersection”⟩
  124. x = y ∧ y ∈ B ∧ ¬ (y ∈ C ∩ D)
  125. ≡ ⟨“Relationship via 𝕀”, “Set difference”⟩
  126. x ⦗ 𝕀 (B - (C ∩ D)) ⦘ y
  127.  
  128.  
  129. Theorem “Isotonicity of 𝕀”: B ⊆ C ≡ 𝕀 B ⊆ 𝕀 C
  130. Proof:
  131. 𝕀 B ⊆ 𝕀 C
  132. ≡ ⟨ “Set inclusion” ⟩
  133. ∀ e ❙ e ∈ 𝕀 B • e ∈ 𝕀 C
  134. ≡ ⟨ “Definition of 𝕀”, “Trading for ∀” ⟩
  135. ∀ e • e ∈ { x ❙ x ∈ B • ⟨ x , x ⟩ } ⇒ e ∈ { x ❙ x ∈ C • ⟨ x , x ⟩ }
  136. ≡ ⟨ Subproof for `e ∈ { x ❙ x ∈ B • ⟨ x , x ⟩ } ⇒ e ∈ { x ❙ x ∈ C • ⟨ x , x ⟩ } ≡ ∀ e • e ∈ B ⇒ e ∈ C`:
  137. e ∈ { x ❙ x ∈ B • ⟨ x , x ⟩ } ⇒ e ∈ { x ❙ x ∈ C • ⟨ x , x ⟩ }
  138. ≡ ⟨ ? ⟩
  139. e ∈ B ⇒ e ∈ C
  140. ∀ e • e ∈ B ⇒ e ∈ C
  141. ≡ ⟨“Trading for ∀”, “Set inclusion”⟩
  142. B ⊆ C
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement