Mathematics/Discrete Math/Sets

Sets, aka groups of elements and logic regarding such.

Terminology

• Set - A grouping of various elements.
• Subset - A grouping of such that all elements of the set are also contained within an equal-sized or larger set. May include two equivalent sets.
• Proper Subset - A subset in which the two sets are not equivalent.
• Empty Set/Zero Set (∅) - A set containing exactly 0 elements. Aka a null set.
• Closed Set - A set in which it's own boundary is contained within the set.
• Open Set - A set where the boundary is excluded from the set, but all values between the boundary are included.
• Cardinality - The number of distinct elements within a set.
  • Ex: The set {-1, 0, 1} has a Cardinality of 3.

Common Set Types:

• Universal Set (U) - An arbitrary set, which changes based on context. However, it is assumed to always contain every possible element currently being considered for the given context.
• Integers (Z) - The set of all integers.
  • Ex: {..., -3, -2, -1, 0, 1, 2, 3, ...}.
• Positive Integers (Z⁺) - The set of all positive integers.
  • Ex: {1, 2, 3, ...}.
• Natural Numbers (N) - The set of Z⁺, but including zero.
  • Ex: {0, 1, 2, 3, ...}.
• Positive Real Numbers (R+) - The set of non-imaginary numbers, greater than zero. Includes fractions, decimals, etc.
• Real Numbers (R) - The set of R+, but including zero and negative numbers.
• Complex Numbers (C) - The set of all numbers, including imaginary ones.

Basic Set Operations

The following are basic operations are explained with sets A={2, 3, 4, 5} and B={0, 2, 4, 6} onto set S. But the operations could be applied to any arbitrary two sets.

• Union of A and B (A ∪ B) - The set of all distinct elements contained in either A or B.
  • Ex: S={0, 2, 3, 4 ,5, 6}.
• Intersection of A and B (A ∩ B) - The set of all distinct elements that are contained in both A and B.
  • Ex: S={2, 4}
• Difference (A/B) - The given set, minus all elements in the second set.
  • Ex: A/B={3, 5}
  • Ex: B/A={0, 6}
• Symmetric Difference of A and B (A △ B or A ⊖ B) - The set of all elements that are a member of exactly one set A or B.
  • Ex: S={0, 3, 5, 6}.
• Cartesian Product of A and B ( A x B) - The set containing all ordered pairs (a, b) for each a in set A and each b in set B.
  • Ex: S={(2, 0), (2, 2), (2, 4), (2, 6), (3, 0), (3, 2), (3, 4), (3, 6), (4, 0), (4, 2), (4, 4), (4, 6), (5, 0), (5, 2), (5, 4), (5, 6)}
• Power Set of A (A) - The set containing all possible subsets using elements from the original set A. Includes the empty set.
  • Note that the number of elements is always equal to 2^x, where x is equal to the cardinality of the given set. This is why it's called the power set; The number of elements corresponds to powers of 2. Thus, counting the elements is a good way to check that it's correct.
    • For example, a set of Cardinality 3 will have 2³ elements.
  • Ex: S={∅, {2}, {3}, {4}, {5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}, {2, 3, 4, 5}}

Set-Builder Notation

Sometimes referred to as "Set Notation". Set-Builder Notation is a standardized way to describe a given set.
The following are explained using the arbitrary sets A and B plus the arbitrary elements x and x.

• x ∈ A - Means that element x is in set A.
• x ∉ A - Means that element x is not in set A.
• A ⊆ B - Means that A is a Subset of B. In other words, all elements in set A are contained within set B. Set B may or may not have additional elements past what what A contains, potentially resulting in A = B.
• A ⊆ B - Means that A is a Proper Subset of B. In other words, all elements in set A are contained within set B. Set B must also have additional elements past what what A contains, resulting in A ≠ B.
• | or : - "Such that...".
  • Ex: { q | q > 0 } - Translates to "The set of all possible values for q, such that q is greater than zero."
  • Ex: { x ∈ R | x ≥ 5 } - Translates to "The set of all Real Numbers x, such that x is greater than or equal to 5."
• ∀ - "For all...".
  • Ex: ∀x ∈ Z+, x+1 < x+2 - Translates to "x+1 is less than x+2 for all x, as long as x is a positive integer.".
• ∃ - "There exists at least one...".
  • Ex: ∃x | P(x) - Translates to "There exists at least one x, such that the function P(x) is true.
• * ∃! - "There exists exactly one...".
• ∴ - "Therefore...".