Discrete Structures 1: Set Theory

Set Theory

• Set theory is a branch of mathematical logic that studies sets, founded by Georg Cantor.

Sets

• A set is an unordered collection of objects, called elements or members of the set.
• A set can be denoted using roster method or set builder notation.

Subsets

• A set A is a subset of B (A ⊆ B) if every element of A is also an element of B.
• A and B are equal if and only if they have the same elements.

Power Sets

• The power set of S, denoted by P(S), is the set of all subsets of S.
• Example: P({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.

Cartesian Products

• The Cartesian product of A and B, denoted by B x A, is the set of all ordered pairs (b, a) where b ∈ B and a ∈ A.
• Example: B x A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.

Cardinality

• The cardinality of a set is a measure of a set's size, meaning the number of different elements in the set.
• Example: The set {1, 2, 4} has a cardinality of 3.

Set Operations

• Union: A ∪ B = {x | x ∈ A ∨ x ∈ B}.
• Difference: A − B = {x | x ∈ A ∧ x ∉ B}.
• Intersection: A ∩ B = {x | x ∈ A ∧ x ∈ B}.
• Complement: U − A = {x | x ∈ U ∧ x ∉ A}.
• Example: The difference between {1, 3, 5} and {1, 2, 3} is the set {5}.
• Example: The union of the sets {1, 3, 5} and {1, 2, 3} is {1, 2, 3, 5}.