Set Theory, Set Relations, Cartesian Products, and Proof Methods
Fundamental Set Definitions and Set Operations
Set Operations and Formal Definitions:
Intersection: The intersection of two sets and in a universal set contains all elements belonging to both and :
Union: The union of two sets and contains all elements belonging to , to , or to both:
Set Difference (Relative Complement): The difference of set from set consists of all elements that belong to but do not belong to :
Absolute Complement: The complement of a set consists of all elements in the universal set that are not in :
Foundational Theorems on Subsets:
Theorem 5.1: For any set , the empty set is a subset of , and is a subset of itself:
Theorem 5.2 (Set Equality Criterion): Let and be subsets of a universal set . The sets and are equal () if and only if both mutual subset inclusions hold:
Power Sets and Cardinality:
Power Set Definition: If is a subset of the universal set , the power set of , denoted , is the set whose members are all the subsets of :
Cardinality Definition: The cardinality of a finite set represents the total number of elements contained in , denoted by:
Proving Set Relationships and Inclusions
Element-Chasing Proof Methodology:
To establish that , an arbitrary element satisfying the defining property of () must be selected.
Specific elements cannot be chosen; the selection must be entirely arbitrary to ensure general validity.
Worked Example: Subset Inclusion with Multiples (PC 5.8):
Given Sets:
Claim: Prove that .
Proof:
Let .
By definition of , there exists an integer such that:
Rewrite by factoring:
Since , define , where .
Substituting gives:
Because is expressed as times an integer, it satisfies the membership condition of :
Therefore, .
Proposition 5.10 (Contrapositive Membership):
Let .
If an arbitrary element satisfies , then by definition .
Since every element of must be in , having implies that:
Consequently, , establishing that .
Proposition 5.B: Equivalence of Set Difference and Complement Intersection:
Theorem Statement: Let and be sets. Then:
Proof of Direction 1 ():
Let .
By definition of set difference, and .
Because , it follows from the definition of complement that .
Since and , by definition of intersection:
Hence, .
Proof of Direction 2 ():
Let .
By definition of intersection, and .
Because , it follows that .
Since and , by definition of set difference:
Hence, .
Conclusion: Both subset inclusions hold, proving .
Counterexample Analysis: Investigating :
Question: Is the equation true for all sets and ?
Counterexample Construction:
Let .
Let .
Computations:
Compute the union:
Remove the elements of :
Comparison:
Result: The statement is false in general because , which equals only when .
Worked Example: Modular Congruence Subsets (Exercise #3, 5.2):
Given Sets:
Set Elements:
Claim: Prove that .
Proof:
Let . Then .
By definition of congruence, there exists such that:
Decompose into multiples of :
Let . Since , .
Thus, , which means:
Therefore, , confirming .
Disjoint Sets and Proof by Contradiction:
Definition: Two sets and are disjoint if and only if their intersection is empty:
Problem: Let and . Prove that and are disjoint.
Proof by Contradiction:
Assume there exists an integer such that .
Since , , so there exists such that:
Since , , so there exists such that:
Equate the two expressions for :
Group terms to analyze algebraic parity:
The left-hand side is of the form , which is an odd integer.
The right-hand side is of the form , which is an even integer.
Because an odd integer cannot equal an even integer (odd even), a contradiction is reached.
Therefore, the assumption is false, and .
Investigating Inclusions and Set Hypotheses (Exercise 5.2 #13):
Condition (a): Testing if
If and , then .
However, if and , the condition provides no information about whether .
Counterexample: Let , , and . Here and , so the premise fails.
Alternative counterexample satisfying the premise: Let , , and . Then and , so holds, but because and .
Condition (c): Testing if
Counterexample:
Let .
Let .
Let .
Evaluate unions:
Although , because but , and but ().
Hence, the implication is false.
Properties of Set Operations and Algebraic Proofs
De Morgan's Laws for Sets:
Complement of a Union:
Proof of De Morgan's Law for Union:
Part 1 ():
Let .
By definition of complement, .
By the logical negation of union, and .
Thus, and .
By definition of intersection, .
Part 2 ():
Let .
By definition of intersection, and .
Thus, and .
Consequently, .
By definition of complement, .
Generalized De Morgan's Laws across Sets:
The complement of an arbitrary finite union is the intersection of the complements:
The complement of an arbitrary finite intersection is the union of the complements:
Both generalized forms can be proven formally using mathematical induction.
Distributive Laws (Theorem 5.18):
Theorem Statement: For any subsets of a universal set :
Element-Chasing Proof of :
Direction 1 ():
Let .
Then and .
Since , either or .
Case 1: If , then since , . Therefore, .
Case 2: If , then since , . Therefore, .
In either case, .
Direction 2 ():
Let .
Case 1: If , then and . Since , . Combining with yields .
Case 2: If , then and . Since , . Combining with yields .
In either case, .
Algebraic Proof of Set Identity (Theorem 5.20):
Target Identity: Prove algebraically that:
Step-by-Step Derivation:
Apply the definition of set difference ():
Rewrite the internal difference as an intersection with complement:
Apply De Morgan's Law and the double complement law ():
Apply the distributive law of intersection over union:
Convert the terms back to difference notation:
Cartesian Products
Definition of Ordered Pairs and Equality:
For elements and , two ordered pairs are equal if and only if their corresponding coordinates are equal:
Cartesian Product of Sets:
The Cartesian product is the set of all ordered pairs where the first coordinate is from and the second coordinate is from :
Cartesian Square: The Cartesian product of a set with itself is denoted :
Discrete Examples of Cartesian Products:
Let and .
Compute :
Compute :
Set Operations with Cartesian Products (Exercise 1h & 1i):
Let , , and .
Compute :
Determine :
Compute the product:
Compute :
Expand each product:
Remove common elements from :
The evaluation confirms the distribution of Cartesian product over difference:
Geometric Interpretation of Cartesian Products:
Let continuous intervals be defined as and .
The product in the coordinate plane represents the set of points:
Geometrically, this forms a solid rectangle in the Cartesian plane with horizontal span from to and vertical span from to .
Theorem 5.25: Outlines standard distributive and algebraic relationships for Cartesian products across unions, intersections, and set differences.
Mathematical Induction and Number Theory Review
Summation Proof by Mathematical Induction:
Proposition: Prove that for all : (Note: The numerator corresponds to the product of 3 consecutive integers).
Basis Step ():
Left-hand side:
Right-hand side:
Since , the basis step holds.
Inductive Step:
Inductive Hypothesis: Assume the statement holds for some :
Goal: Prove the statement holds for :
Proof Derivation:
Substitute the inductive hypothesis into the sum of terms:
Find a common denominator:
Factor out the common term from the numerator:
The formula is valid for . By mathematical induction, the identity is true for all .
Divisibility via Modular Arithmetic:
Problem: Determine whether is divisible by for all .
Empirical Validation:
For :
For :
General Proof using Modular Arithmetic:
Note the base congruence modulo :
By Theorem 2.28 (modular power compatibility: if , then ):
Subtracting from both sides:
Hence, is divisible by for all .
Congruence of Sum of Squares Modulo 2:
Claim: Prove that for all :
Algebraic Derivation:
Expanding the left side gives:
Since is a multiple of , for any integers and .
Therefore, .
Proof by Exhaustive Case Analysis Modulo 2:
Case 1:
Case 2:
Case 3:
Case 4:
Generalization (Freshman's Dream):
When is any prime number, the binomial coefficients are divisible by for all , yielding:
Inequality Proof by Contradiction:
Proposition: For all with :
Proof by Contradiction:
Assume the negation: suppose there exist with such that:
Multiply both sides by (valid without changing inequality direction because and ):
Rearrange the inequality:
For all real numbers , the square of a real number is non-negative: .
The only way and can both hold is if:
This contradicts the premise that .
Thus, the assumption is false, concluding that .