Set operation

A set operation applies some rule to define new sets given previously-defined sets. Every set operation has a corresponding logical analogue.

Contents

Complement

The complement of a set is the set of all elements not in that set. A universal set must be defined in order to use this operation. The complement of a set $A$ is denoted $\overline{A}$ and can be read as "$A$ complement" or "not $A.$"

Given a universal set $U$, the complement of a set $A$ can be written in set-builder notation: $$\overline{A} = \set{x \in U:x \notin A}$$ It can also be written as a difference: $$\overline{A} = U - A$$

The set complement's logical analogue is negation.

Intersection

The intersection of two sets is the set of all elements they have in common. The intersection of two sets $A$ and $B$ is denoted $A \cap B$ and is read as "$A$ intersect $B.$"

The intersection of two sets $A$ and $B$ can be written in set-builder notation: $$A \cap B = \set{x:x \in A \land x \in B}$$

If $A \cap B = \emptyset$, then $A$ and $B$ are disjoint from each other, or in other words, they have no elements in common.

The set intersection's logical analogue is conjunction.

Similar to $\sum$ notation, there is a way to compactly represent the intersection of a sequence of sets.

For a finite intersection of sets $S_1, S_2, S_3, ..., S_n$, instead of writing $S_1 \cap S_2 \cap S_3 \cap ... \cap S_n$, one can write: $$\bigcap\limits_{i=1}^{n} S_i$$

Union

The union of two sets is the set of all elements they have, common or not. The union of two sets $A$ and $B$ is denoted $A \cup B$ and is read as "$A$ union $B.$"

The union of two sets $A$ and $B$ can be written in set-builder notation: $$A \cup B = \set{x:x \in A \lor x \in B}$$

The set union's logical analogue is disjunction.

Similar to $\sum$ notation, there is a way to compactly represent the union of a sequence of sets.

For a finite union of sets $S_1, S_2, S_3, ..., S_n$, instead of writing $S_1 \cup S_2 \cup S_3 \cup ... \cup S_n$, one can write: $$\bigcup\limits_{i=1}^{n} S_i$$

Difference

The difference of two sets is the set of all elements in the first set that the second set doesn't have. The difference of two sets $A$ and $B$ is denoted $A - B$ and is read as "$A$ minus $B.$"

The difference of two sets $A$ and $B$ can be written in set-builder notation: $$A - B = \set{x:x \in A \land x \notin B}$$ It can also be written in set-builder notation using the conditional: $$A - B = \set{x:\lnot(x \in A \rightarrow x \in B)}$$

This is a directed set operation, so the choice of which set is first and which is second matters. In other words, $A - B \ne B - A$ unless $A = B.$

Interestingly, the set difference's logical analogue is the negation of the conditional.

Set differences aren't involved in any of the set identities, so trying to rewrite them may be difficult at first. I recommend drawing a Venn diagram to convince yourself that the following equation is true: $A - B = A \cap \overline B.$ Notice this equation is incredibly similar to the first conditional identity from the logic laws.

Symmetric difference

The symmetric difference of two sets is the set of all elements they don't have in common. The symmetric difference of two sets $A$ and $B$ is denoted $A \oplus B$ and is read "$A$ symmetric difference $B.$" However, feel free to instead say "$A$ xor $B.$"

The symmetric difference of two sets $A$ and $B$ can be written in set-builder notation: $$A \oplus B = \set{x:x \in A \oplus x \in B}$$ It can also be written as the union of set differences: $$A \oplus B = (A - B) \cup (B - A)$$

The set symmetric difference's logical analogue is exclusive disjunction.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort