{"id":125,"date":"2021-10-21T11:41:30","date_gmt":"2021-10-21T11:41:30","guid":{"rendered":"https:\/\/wqrld.net\/blog\/?p=125"},"modified":"2021-12-10T13:53:32","modified_gmt":"2021-12-10T13:53:32","slug":"set-math-notations","status":"publish","type":"post","link":"https:\/\/wqrld.net\/blog\/set-math-notations\/","title":{"rendered":"Set math (notations and P iff Q)"},"content":{"rendered":"\n

Some math basics for trying to understand https:\/\/ocw.tudelft.nl\/wp-content\/uploads\/Algoritmiek_proofs.pdf<\/a> and\/or MIT’s OCW on math for computer science.<\/p>\n\n\n\n

Sets<\/h2>\n\n\n\n

for set A and B<\/p>\n\n\n\n

\u222a = union, Everything in A AND everything in B (including overlap)
\u2229 = intersection, Everything in A AND B (just the overlap)
A \\ B = {x | x \u2208 A and x \u2208 B} = Everything in A but not in B

A \u2208 B = A is part of B (smaller side of \u2208 towards the smaller set)
Q.E.D. = Proof done (normally a block symbol, but wordpres….)
P iff Q = P if and only if Q = P \u2194 Q) = P implies Q and vice-versa<\/p>\n\n\n\n

\"\"
\u2229 intersection (wikipedia)<\/figcaption><\/figure>\n\n\n\n

Set proof (both statements imply eachother)<\/h2>\n\n\n\n

With set A,B,C:

A \u2229 (B \u222a C) = (A \u2229 B) \u222a (A \u2229 C)
the intersection of A with (B andor C)
=
(The intersection between A and B) andor (the intersection between A and C)

This looks correct, but let’s prove it.<\/p>\n\n\n\n

Proof<\/strong>.
We show that z \u2208 A \u2229 (B \u222a C)<\/strong> implies that
z \u2208 (A \u2229 B) \u222a (A \u2229 C) <\/strong>and vice-versa.

First<\/strong>, we show that z \u2208 A \u2229 (B \u222a C) implies that
z \u2208 (A \u2229 B) \u222a (A \u2229 C):

Assume that z \u2208 A \u2229 (B \u222a C).
Then z is in A and z is also in B or C. Thus, z is in
either A\u2229B or A\u2229C, which implies z \u2208 (A\u2229B)\u222a(A\u2229C)

——-

Now<\/strong>, we show that z \u2208 (A\u2229B)\u222a(A\u2229C) implies that
z \u2208 A \u2229 (B \u222a C).

Assume that z \u2208 (A \u2229 B) \u222a (A \u2229 C).
Then z is in both A and B or else z is in both A and
C. Thus, z is in A and z is also in B or C. This implies
that z \u2208 A \u2229 (B \u222a C).

Q.E.D.
<\/p>\n\n\n\n


<\/p>\n\n\n\n

Proof by contradiction<\/h2>\n\n\n\n

Proof by contra-positive ((P \u2192 Q) \u2194 (\u00acQ \u2192 \u00acP) is a tautology. )

<\/p>\n\n\n\n

In order to prove a proposition P by contradiction:<\/p>\n\n\n\n

  1. Write, \u201cWe use proof by contradiction.\u201d<\/li>
  2. Write, \u201cSuppose P is false.\u201d<\/li>
  3. Deduce a logical contradiction.<\/li>
  4. Write, \u201cThis is a contradiction. Therefore, P must
    be true.\u201d<\/li><\/ol>\n\n\n\n

    Theorem: sqrt(2) is irrational<\/strong><\/p>\n\n\n\n

    proving something irrational is hard, so instead assume it to be rational:<\/p>\n\n\n\n

    sqrt(2) = a\/b (in the lowest terms a and b possible)
    2 = (a^2)\/(b^2)
    a^2 = 2(b^2)
    which means a^2 is even
    thus a is even
    thus a^2 is a multiple of 4
    thus b^2 is a multiple of 4
    thus b is also even

    a and b are even which is a contradiction with the lowest term rule
    thus a\/b is not rational<\/p>\n","protected":false},"excerpt":{"rendered":"

    Some math basics for trying to understand https:\/\/ocw.tudelft.nl\/wp-content\/uploads\/Algoritmiek_proofs.pdf and\/or MIT’s OCW on math for computer science. Sets for set A and B \u222a = union, Everything in A AND everything in B (including overlap) \u2229 = intersection, Everything in A AND B (just the overlap)A \\ B = {x | x \u2208 A and x … Continue reading “Set math (notations and P iff Q)”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-125","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/posts\/125","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/comments?post=125"}],"version-history":[{"count":11,"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/posts\/125\/revisions"}],"predecessor-version":[{"id":181,"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/posts\/125\/revisions\/181"}],"wp:attachment":[{"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/media?parent=125"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/categories?post=125"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wqrld.net\/blog\/wp-json\/wp\/v2\/tags?post=125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}