Part 3: Set Theory

Proving Statements About Sets

Introduction

• We begin with wanting to prove simple yet fundamental statements about sets, for example, the statement that set A is contained in the union of sets A and B (i.e., A ⊆ A ∪ B). Establishing such basic properties of sets is crucial in understanding more complex set relationships and provides a foundation for further mathematical reasoning.

Importance of Proof

• Reason to Prove:

  • In mathematics, what may seem "obvious" does not always imply "true"; this underscores the necessity of rigorous proof in establishing the validity of statements.

  • A proof ensures the truth of a statement by logically demonstrating its correctness through a sequence of logical deductions and definitions.

  • If a statement appears to be obviously true but cannot be quickly proven, it warrants closer scrutiny, as it may contain underlying complexities that need to be addressed.

Definitions and Set Theory Notation

• To prove that A ⊆ A ∪ B, we rely on the formal definition of a subset that states:

  • A set S is a subset of T if for every element x, if x is in S, then x is in T:

    $x ext{ in } S <br>ightarrow x ext{ in } T$

  • To show that A ⊆ A ∪ B, we must demonstrate that every element x belongs to both A and the union A ∪ B, reaffirming the interconnectedness of these sets.

Definition of Union

• The union of sets A and B is formally defined as:

  • $A ∪ B = { x : x ∈ A \text{ or } x ∈ B }$

  • This definition highlights that the union operation combines all distinct elements from both sets, providing a comprehensive set of elements found in at least one of the original sets.

Proof for A ⊆ A ∪ B

1. Assume: Let x be an arbitrary element of set A.

2. By the definition of the union of sets, since x is in A, it must also be that x is included in A ∪ B, which confirms our initial goal that A is indeed a subset of the union, A ⊆ A ∪ B.

Proving Other Statements

• We are interested in demonstrating various other statements regarding set equality and relationships, such as:

  • Proving that the union of intersections holds, specifically, that (A ∩ B) ∪ C ≤ A ∪ C, and how this relates to other established set principles.

Reverse Inclusion

• It is also critical to test if the reverse inclusion A ∪ C ≤ (A ∩ B) ∪ C holds true.

  • If we find it to be true, we should proceed to write a proof; if false, identifying a counterexample can provide insight into the conditions under which set operations behave differently.

The Transitive Law of Set Containment

• Statement: If R ≤ S and S ≤ T, then R ≤ T.

• This is known as the transitive law of set containment, illustrating that if a set is a subset of another, and that set is a subset of a third, the first set must also necessarily be a subset of the third.

Laws of Sets

• A comprehensive list of important laws of sets includes:

  • Commutative Laws:

    • $A ∩ B = B ∩ A$ (Intersection)

    • $A ∪ B = B ∪ A$ (Union)

  • Associative Laws:

    • $A ∩ (B ∩ C) = (A ∩ B) ∩ C$ (Intersection)

    • $A ∪ (B ∪ C) = (A ∪ B) ∪ C$ (Union)

Importance of Proofs

• Many statements in set theory may seem intuitively true, but each demands verification through painstaking proofs to uphold the integrity of mathematical discourse and to ensure that established ideas are valid.

• The discipline of mathematics inherently requires proof for claims of truth; historical precedents highlight the critical role of proofs in advancing mathematical knowledge.

Method of Proving Set Equality

• Method of Containment: To prove two sets are equal, one must consecutively prove containment in both directions.

  • For example, to demonstrate that A ∩ B equals B ∩ A, one can approach it by showing:

  • 1. $A ∩ B ⊆ B ∩ A$

  • 2. $B ∩ A ⊆ A ∩ B$

Proof Structure

1. Proof of A ∩ B ⊆ B ∩ A:

   • Assume $x ∈ A ∩ B$.

   • By the definition of intersection, x must simultaneously belong to both A and B. Therefore,

   • The implication $x ∈ A ext{ and } x ∈ B$ leads to the conclusion that $x ∈ B ext{ and } x ∈ A$, thus $x ∈ B ∩ A$.

2. Proof of B ∩ A ⊆ A ∩ B:

   • Assume $x ∈ B ∩ A$.

   • By similar deduction, showing that $x ∈ B ext{ and } x ∈ A$ implies $x ∈ A ∩ B$.

Definition Chasing

• This method, known as definition chasing, involves meticulously verifying definitions, emphasizing a thorough understanding of the fundamental principles of set theory without necessitating advanced insights.

Importance of Notation in Proofs

• Proper usage of notation in generating proofs is crucial.

  • It’s essential to differentiate between propositions (which can be proved) and sets (which cannot be directly proved), ensuring clarity and precision in mathematical discussions.

Exercises

• Write out proofs for the following propositions:

  • Commutative law for intersection: prove $A ∩ B = B ∩ A$.

  • Commutative law for union: prove $A ∪ B = B ∪ A$.

• Understand the implications of commutativity in set operations and how it interacts with other laws of set theory regarding manipulation of sets.

Advanced Laws

• Further laws worth investigating:

  • The associative law for both union and intersection possesses profound implications in set operations that facilitate understanding complex relationships.

  • Explore the distributive law, characterized by:

    • $A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)$

    • $A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)$.

Final Remarks

• A repeated and careful reading of these notes is indispensable for mastery of the content and principles.

• Utilizing Venn Diagrams can serve as effective illustration tools for visualizing and comprehending set relations and properties, enhancing the overall understanding of the subject matter.

• Engaging actively with the content by posing questions and seeking clarifications can significantly deepen comprehension.

• DeMorgan's laws should be properly illustrated through set notation and Venn Diagrams for enhanced understanding, as these laws are pivotal in the analysis of set complements and intersections.

• It is important to note that while Venn Diagrams serve illustrative purposes, they do not serve as substitutes for rigorous proofs, which are foundational in mathematics.