Introduction to Set Theory

Basics of Set Theory

• A set represents a collection of objects applicable across disciplines.
• Objects within sets are known as elements.
• Sets are typically labeled using capital letters, often italicized for distinction.
• Elements belonging to a set, such as set A, can be visually represented within a labeled ring.

Defining Sets

• Sets can be defined through descriptive statements.
• Roster notation involves listing elements explicitly within curly braces, separated by commas, like A = {1, 2, 3, 4}.
• Sets can be easily referenced by their assigned name or label once defined.
• Set elements are versatile, including numbers, people, objects, and even other sets.
• Each element in a set is unique, with no repetitions.

Uniqueness and Order

• Each element is considered only once; repetitions are disregarded.
• Redundant listings hold no additional value; {1, 1, 1, 2, 3, 3} is equivalent to {1, 2, 3}.
• Order is irrelevant; {a, b, c} = {c, a, b} = {b, c, a}.
• Sets are unordered collections of objects.
• When sets contain numbers, elements are usually listed in ascending order for clarity.

Notation

• Ellipsis (...) serves as a shorthand for large sets exhibiting a clear pattern.
• T = {1, 2, 3, ..., 1000} defines T to include integers from 1 to 1000.
• An ellipsis at the end indicates the pattern continues indefinitely.
• Ellipses can appear at the beginning and end to denote infinite sets.

Set Types

• Infinite sets contain an unlimited number of elements.
• Finite sets contain a specific, countable number of elements.
• Sets can be defined by describing their elements within curly braces.
• M = {calendar months}, O = {people who have walked on the moon}, S = {integers from one to a thousand} are examples of definition by description.
• Descriptions must be precise; vague definitions like "set of good songs" are not acceptable.

Special Predefined Sets

• The empty set (or null set) contains no elements, symbolized by ∅ or {}.
• The universal set encompasses all elements of interest in a given context, symbolized by U.

Predefined Sets of Numbers

• Sets are represented using blackboard bold font, characterized by double vertical lines.
• R represents the set of real numbers.
• Q represents the set of rational numbers (quotients of two integers).
• Z represents the set of all positive and negative integers, including zero.
• N represents the set of natural numbers or counting numbers, with or without zero, depending on convention.
• C represents the set of complex numbers.

Cardinality

• Cardinality is the number of elements in a set.
• It is expressed with absolute value bars around the set label, such as |B|.
• |B| is read as "the cardinality of set B."
• Since set elements are unique, duplicates do not affect cardinality. |{1,1,1,2,3,3}| = 3.
• Empty set cardinality is zero, expressed as an identity.
• Cardinality acts as a function, taking a set as input and returning a number.
• Other notations for the cardinality of set S include n(S) and #S.
• The set containing an empty set is not an empty set; |{ ∅ }| = 1.

Set Membership

• An element belongs to a set, expressed as 3 ∈ C.
• An element does not belong to a set, expressed as 3 ∉ C.
• Statements can be rephrased, although it's less common.
• "Set C contains element 3" and "Set C does not contain element 3" are examples of rephrased statements.
• The set membership symbol "∈" resembles "E" for element.

Set Builder Notation

• This notation defines a set by specifying the conditions that its elements must satisfy.
• For example, A = {x | x ∈ N and x < 6}.
• This translates to "Set A is the set of all x such that x is an element of the set of natural numbers and x is less than 6."
• The variable is usually x but can be any lowercase letter.
• The colon (:) or vertical bar (|) means "such that."
• The algebraic expression after the colon must be true for x to be included in the set.
• Multiple conditions separated by commas are interpreted as "and."

Considerations in Set Builder Notation

• If the type of number is not evident for x, specify the type:
  • B = {x ∈ N | x ≤ 5} denotes that Set B comprises natural numbers x less than or equal to 5.
• For conciseness, specify the type before the "such that" condition.

Combining Definitions

• Compatible with natural language; P = {x | x is the square of an integer}.
• Conditions can be combined using commas, implying "and".
• Multiple conditions can be combined with a comma (and).
• Conditions like squares up to a hundred can be applied.
• "Or" conditions allow inclusion if at least one condition is met.
• Q = {x ∈ Z | x is the square of a positive integer, x ≤ 10} is one set

Complement of a Set

• The complement of a set consists of all elements in the universal set that are not in the set.
• If U = {1, 2, 3, 4, 5} and A = {1, 2, 5}, then Ac = {3, 4}.
• Symbols for complement include Ac, A', or Ā.
• The complement of a set is itself another set.
• Cardinality is such that |U| = 5, |A| = 3, |Ac| = 2.

Cardinality and Complements

• A set's cardinality plus its complement's cardinality equals the universal set's cardinality.
• The complement of set A contains all x, where x is in the universal set but not in A.
• The complement of the empty set is the universal set.
• The complement of the universal set is the empty set.

Venn Diagrams

• Sets are visually represented using Venn diagrams, with the universal set as a large rectangle.
• Sets are usually represented as ovals or circles within this rectangle.
• Elements of a set are placed inside its corresponding oval.
• Shading the interior of a set highlights the set in general.
• Shading the region outside a set's oval indicates the set's complement.
• In Venn diagrams, the empty set has nothing shaded.
• In Venn diagrams, the universal set has everything inside the rectangle shaded.

Subsets and Supersets

• Set A is a subset of set B if every element of A is also an element of B.
• Equal sets are subsets of each other.
• Every set is a subset of itself.
• The empty set is a subset of every set.
• Every set is a subset of the universal set.
• B is a superset of A if A is a subset of B.
• Equal sets are supersets of each other.
• Every set is a superset of itself.
• Every set is a superset of the empty set.
• The universal set is a superset of every set.

Proper Subsets and Supersets

• A is a proper subset of B if A is a subset of B but not equal to B.
• If A is a proper subset of B, then |A| < |B|.
• Equal sets aren't proper subsets, and a set isn't a proper subset of itself.
• The proper superset is the inverse of the proper subset.

Interval Notation

• Shorthand for set builder notation describing continuous real number ranges.
• Square brackets, [ ], denote closed intervals including endpoints.
• Parentheses, ( ), denote open intervals excluding endpoints.
• Half-open intervals mix parentheses and square brackets, including one endpoint but excluding the other.
• Interval notation concisely defines sets of continuous real numbers.

Set Operations

• Ways to create new sets from existing ones.
• Binary set operations involve two sets.
• Unary set operations involve one set.

Complement

• The complement of set A is the set of elements not in set A (a unary operation).

Cardinality

• Cardinality is not a set operation but rather the number of elements in a set.

Intersection

• The intersection of A and B (A ∩ B) contains elements common to both A and B.
• In set builder notation: A ∩ B = {x | x ∈ A and x ∈ B}.
• The intersection of a set with itself results in the set itself.
• A ∩ ∅ = ∅.
• A ∩ universal set = A.
• The intersection operation is commutative: A ∩ B = B ∩ A.
• Disjoint sets have no common elements; their intersection is the empty set.
• Intersection corresponds to the logical operator "and."

Union

• The union of A and B (A ∪ B) is the set of all elements in A or B or both.
• In set builder notation: A ∪ B = {x | x ∈ A or x ∈ B}.
• The union operation is commutative: A ∪ B = B ∪ A.
• The union of a set with itself is the set itself: A ∪ A = A.
• A ∪ ∅ = A.
• A ∪ universal set = universal set.
• The union operator is associated with the logical operator "or."

Set Operations and Their Results

• Set operations like intersection and union produce sets, not individual elements.
• The intersection of sets A and B, both containing 2, yields {2}, not just the number 2.

Relative Complement

• Relative complement operation yields elements exclusively in one set and not in another.
• "A not in B" is the relative complement of B with respect to A, denoted as A \ B.
• Set builder notation: {x | x ∈ A and x ∉ B}.
• Relative complement of R with respect to S is written S \ R.
• Terms like "complement," "slash," and "not in" signify exclusion.
• U \ A is the complement of set A.
• Relative complement is "relative" against another set but "absolute" against the universal set.
• Relative complement isn't commutative (A \ B ≠ B \ A).
• A not in B is equivalent to A ∩ B complement.

Symmetric Difference

• Contains elements unique to either set A or set B, but not in both.
• Operation symbols include a triangle or a plus sign inside a circle.
• Can be read as "A delta B" or "A xor B”.
• Set builder notation uses the exclusive or (xor) operator.
• A xor B = (A ∪ B) \ (A ∩ B).
• A xor B = (A \ B) ∪ (B \ A).
• Symmetric difference follows the commutative law.

Summary of Binary Set Operations

• Four common binary set operations exist: intersection, union, relative complement, and symmetric difference.
• Each has a set builder notation, logical word (and, or, xor), and Venn diagram representation.
• Intersection, union, and symmetric difference are commutative, while relative complement is not.

Multiple Sets in a Problem

• Problems can involve more than two sets.
• The logical operator "or" corresponds to set operator the union (∪).
• Male stem students as may be represented as F' ∩ S, where F' is the complement of female students.
• F' ∩ S can also be written as S \ F.
• The intersection set operator obeys the associative law, enabling operations in any order.
• The union operator also obeys the associative law.
• The exclusive or operation also obeys the associative law.

Order of Operations and the Distributive Law

• Order is important for union and intersection, often indicated using parentheses.
• Intersection and union obey the distributive law.
• G ∩ (S ∪ F) = (F ∩ G) ∪ (F ∩ S).
• G ∪ (S ∩ F) = (F ∪ G) ∩ (F ∪ S).

De Morgan's Laws

• Identities involving complements of sets.
• (A ∪ B)' = A' ∩ B'; The complement of the union equals the intersection of the complements.
• (A ∩ B)' = A' ∪ B'; The complement of the intersection equals the union of the complements.
• To apply these, switch the set operation and distribute the complement symbol to both sets.

Cartesian Product (Cross Product)

• Combines elements of two sets to form ordered pairs.
• The symbol used is x, usually pronounced "cross."
• For sets A = {a, b} and B = {1, 2, 3}, A x B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}.
• Set builder notation: A x B = {(x, y) | x ∈ A and y ∈ B}.
• |A x B| = |A| * |B|.
• Cartesian product is not commutative (A x B ≠ B x A), but their cardinalities are equal.
• Ordered pairs can represent coordinates on a Cartesian coordinate system.
• R x R represents a two-dimensional plane, often denoted as R^2 , and R-cubed denotes a three-dimensional space.

Power Set

• The power set of S is the set of all possible subsets of S, including the empty set and S itself.
• If S = {a, b}, then the power set of S = { {}, {a}, {b}, {a, b} }.
• A set with n elements has 2^n subsets.
• Binary numbers can generate each subset.
• |Power set of S| = 2|S|.