Part 4: Set Theory
Proof of Set Equality A ∪ B = B ∪ A
Let x ∈ (A ∪ B)**.
By the definition of union, x ∈ (A ∪ B) means x ∈ A or x ∈ B.
Consider the two cases:**
Case 1: x ∈ A
Then x ∈ (B ∪ A), via the logical argument P → Q ∨ P, where P = "x ∈ A" and Q = "x ∈ B".
Case 2: x ∈ B
Then x ∈ (B ∪ A), via the tautology P → P ∨ Q, where P = "x ∈ B" and Q = "x ∈ A".
In either case, x ∈ (B ∪ A).
Therefore, if x ∈ (A ∪ B) then x must also be in (B ∪ A).
Structure of the Argument:
This argument follows a dilemma structure where x ∈ A or x ∈ B.
If x ∈ A then x ∈ (B ∪ A).
If x ∈ B then x ∈ (B ∪ A).
Conclusively, x ∈ (B ∪ A) or x ∈ (B ∪ A) implies x ∈ (B ∪ A).
Conclusion:
Based on arguments, x ∈ (B ∪ A).
Set Containment Proof for A ∩ B = A ∪ B
To prove A ∩ B = A ∪ B, we first need to show set containment in both directions:
Show: A ∩ B ⊆ A ∪ B
Let x ∈ (A ∩ B). We need to show that x ∈ (A ∪ B).
By the definition of intersection, x ∈ (A ∩ B) means x ∈ A and x ∈ B.
Therefore, we can conclude, based on the logic of material implication and the definition of union, that x must consequently be part of either A or B.
Conclusion: A ∩ B ⊆ A ∪ B.
Next, Show: A ∪ B ⊆ A ∩ B.
This proof utilizes a similar approach and Demorgan's laws of logic.
Upon proving both directions: A ∩ B ⊆ A ∪ B and A ∪ B ⊆ A ∩ B, we have shown equality.
Prove A ∪ Ø = A
To prove A ∪ Ø ≤ A and A ≤ A ∪ Ø, we follow the definitions:
Let x ∈ (A ∪ Ø).
By the definition of union, x ∈ A or x ∈ Ø.
Since Ø (the empty set) contains no elements, our disjunctive syllogism follows: x ∈ A.
Thus, A ∪ Ø ≤ A is validated.
Now, prove the other direction: A ≤ (A ∪ Ø).
Let x ∈ A.
By the definition of union, this implies that x ∈ (A ∪ Ø).
This gives us A ≤ (A ∪ Ø).
Conclusion: By having shown both A ∪ Ø ≤ A and A ≤ (A ∪ Ø), we conclude A ∪ Ø = A.
Prove A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Need to show set containment in both directions.
Show A ∩ (B ∪ C) ≤ (A ∩ B) ∪ (A ∩ C).
Let x ∈ (A ∩ (B ∪ C)).
By the definition of intersection, this implies x ∈ A and x ∈ (B ∪ C).
By the definition of union, x can be either in B or C; thus we derive two consequent conditions.
This affirms that x must be in (A ∩ B) or (A ∩ C) under logical distribution laws.
Show (A ∩ B) ∪ (A ∩ C) ≤ A ∩ (B ∪ C).
Let x ∈ ((A ∩ B) ∪ (A ∩ C)).
By the definition of union, either x ∈ (A ∩ B) or x ∈ (A ∩ C).
Thus, we achieve a similar conclusion that reinforces x ∈ A which is essential for proving the initial containment.
Conclusion: Complete proof of set equality with both containment directions validated.
Cardinality Definition and Properties
Definition 2.17: The cardinality of a set is defined as the number of elements within that set. Denoted as |A|.
Example: If A = {a, b, c, d, f}, then |A| = 5.
Example: If S = {2, x, 7}, then |S| = 3.
Example: |Ø| = 0, indicating the empty set has no elements.
Distinction: Cardinality denotes the quantification of set elements, which should not be confused with claiming a set's equivalence to its cardinal size.
Cardinality Relation: For sets X and Y, the cardinality relation is expressed as:
This equation signifies that to find the cardinality of the union of two sets, one must add the individual cardinalities and subtract the cardinality of their intersection to avoid double counting.
Show A ∩ A = Ø
To prove: Show A ∩ A ≤ Ø and Ø ≤ A.
Show: A ∩ A ≤ Ø.
Let x ∈ (A ∩ A).
Define intersection implies that x ∈ A and x ∈ A (which is identical).
A logical contradiction arises if A were non-empty, hence concluding x must lead to Ø directly.
Show: Ø ≤ A.
The empty set Ø is a subset of every set by definition, hence holds true.
Conclusion: Since we've substantiated both directions of containment, we conclude A ∩ A = Ø.
Assertions and Validations
Assertions are unproven statements that require validation. For example:
"Then x must also be in A…"
"This will always result in an odd number…"
These require rigorous proof to be accepted valid in mathematical arguments.
Always justify assertions to avoid assumptions in proofs.
Valid Argument Methods
Transitivity: For proving set containment, the valid argument states:
If R ⊆ S and S ⊆ T, then R ⊆ T.
This method maintains the logical proof integrity across set relationships and containment assertions.
Always create counterexamples to demonstrate falsehood in statements when required, specifying the universe considered (e.g., u = {1, 2, 3, 4}).