• Basic Definitions
  • Set, Element, Subset
  • Example:
  • Empty Set
  • Universal Set
• Set Notation
  • Roster Notation
  • Set-Builder Notation
• Membership and Inclusion
  • Membership
  • Subset and Inclusion
  • Example:
• Venn Diagrams
  • Common Venn Diagram Operations:
  • Example:
• Union ( ∪ )
• Intersection ( ∩ )
• Difference ( A \ B )
• Complement ( A' )
• Symmetric Difference
• Cartesian Product
• Pairs and Tuples
  • Example of Pairs and Tuples:
• Commutative, Associative, and Distributive Laws
  • Commutative Laws:
  • Associative Laws:
  • Distributive Laws:
• De Morgan’s Laws
  • Example:
• Absorption and Idempotent Laws
  • Absorption Laws:
  • Idempotent Laws:
• Double Complement Law
  • Example:
• Proofs Using Venn Diagrams and Algebraic Techniques
  • Proof with Venn Diagrams:
    • Example: Prove De Morgan’s Law $(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$ using a Venn diagram:
  • Proof with Algebraic Techniques:
    • Example: Prove the absorption law $A\cup (A\cap B)=A$:
  • Example of De Morgan’s Law Using Algebraic Techniques:
• Definitions
  • Ordered Pairs and Cartesian Products
  • Binary Relations
• Properties of Relations
  • Reflexive Relations
  • Symmetric Relations
  • Antisymmetric Relations
  • Transitive Relations
• Equivalence Relations
  • Equivalence Classes
• Partition of a Set
• Partial and Total Orders
  • Partial Orders
  • Total Orders
• Hasse Diagrams
  • Example:

Introduction to Set Theory

Basic Definitions

Set, Element, Subset

• Set: A set is a well-defined collection of distinct objects, considered as an object in its own right. The objects in a set are called elements or members of the set.
• Element: If $a$ is an object, we say $a$ is an element of a set $A$ if $a$ belongs to the set. This is denoted as $a\in A$.
• Subset: A set $A$ is called a subset of another set $B$ if every element of $A$ is also an element of $B$. This is denoted as $A\subseteq B$.

Example:
Let $A=\{1,2,3\}$ and $B=\{1,2,3,4,5\}$. Since every element of $A$ is also in $B$, we say $A$ is a subset of $B$: $A\subseteq B$.

Empty Set

• Empty Set: The empty set, denoted by $\mathrm{\varnothing }$, is the set that contains no elements. Formally:

Universal Set

• Universal Set: The universal set is the set that contains all possible elements for a particular discussion. It is typically denoted as $U$. All other sets are considered subsets of the universal set.

Set Notation

Roster Notation

• Roster Notation: A set is defined by explicitly listing all of its elements inside curly braces.
  • Example: $A=\{1,2,3,4\}$ means that $A$ is the set containing the elements 1, 2, 3, and 4.

Set-Builder Notation

• Set-Builder Notation: A set is defined by specifying a property that its members must satisfy.
  • Example: $A=\{x\mid x\text{ is an even number}\}$ defines the set $A$ as all even numbers.

Membership and Inclusion

Membership

• Membership is the relationship between an element and a set. If $a$ is an element of a set $A$, we say $a$ belongs to $A$ and write:

If $a$ does not belong to $A$, we write:

Subset and Inclusion

• Subset: A set $A$ is a subset of another set $B$ if every element of $A$ is also an element of $B$. This is denoted as:

• Proper Subset: $A$ is a proper subset of $B$, written $A\subset B$, if $A$ is a subset of $B$ but $A\ne B$.

Example:
If $A=\{1,2\}$ and $B=\{1,2,3\}$, then $A\subseteq B$ because all elements of $A$ are in $B$. However, $A\ne B$, so $A\subset B$ (proper subset).

Venn Diagrams

• Venn Diagrams: A Venn diagram visually represents sets and their relationships. Each set is shown as a circle, and the relationships between the sets (such as intersections or unions) are depicted by the overlapping or non-overlapping areas of the circles.

Common Venn Diagram Operations:

• Intersection ($A\cap B$): The set of elements common to both $A$ and $B$. Represented by the overlapping region of two circles.
• Union ($A\cup B$): The set of elements that belong to either $A$ or $B$. Represented by the entire area covered by both circles.
• Complement ($A^c$): The set of elements not in $A$, but in the universal set $U$.
• Difference ($A-B$): The set of elements in $A$ but not in $B$.

Example:
If $A=\{1,2,3\}$ and $B=\{3,4,5\}$:

• $A\cup B=\{1,2,3,4,5\}$ (union)
• $A\cap B=\{3\}$ (intersection)
• $A-B=\{1,2\}$ (difference)

Venn diagrams provide an intuitive way to visualize these set operations.

Operations on Sets

Union ( ∪ )

• Union of two sets $A$ and $B$ is the set of elements that are in either $A$ or $B$, or in both. The union operation is denoted by $A\cup B$.

• Example: If $A=\{1,2,3\}$ and $B=\{3,4,5\}$, then:

Intersection ( ∩ )

• Intersection of two sets $A$ and $B$ is the set of elements that are in both $A$ and $B$. The intersection operation is denoted by $A\cap B$.

• Example: If $A=\{1,2,3\}$ and $B=\{3,4,5\}$, then:

Difference ( A \ B )

• The difference of two sets $A$ and $B$ is the set of elements that are in $A$ but not in $B$. The difference is denoted by $A\setminus B$ or $A-B$.

• Example: If $A=\{1,2,3\}$ and $B=\{3,4,5\}$, then:

Complement ( A' )

• The complement of a set $A$ refers to all the elements that are not in $A$, but are in the universal set $U$. The complement of $A$ is denoted by $A^{\prime }$ or $A^c$.

• Example: If the universal set $U=\{1,2,3,4,5\}$ and $A=\{1,2\}$, then:

Symmetric Difference

• The symmetric difference of two sets $A$ and $B$ is the set of elements that are in either of the sets, but not in their intersection. It is denoted by $A\mathrm{△}B$.

• Example: If $A=\{1,2,3\}$ and $B=\{3,4,5\}$, then:

Cartesian Product

• The Cartesian product of two sets $A$ and $B$ is the set of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$. It is denoted by $A\times B$.

• Example: If $A=\{1,2\}$ and $B=\{x,y\}$, then:

Pairs and Tuples

• Pairs: A pair is an ordered collection of two elements. For example, $(a,b)$ is a pair where the order matters—$(a,b)\ne (b,a)$ unless $a=b$.
• Tuples: A tuple is an ordered collection of elements. A 2-tuple is just a pair, a 3-tuple is called a triple, and so on. For example, $(a,b,c)$ is a 3-tuple.

Example of Pairs and Tuples:

• Pair: $(2,3)$ where the order matters.
• Triple: $(1,2,3)$ where each element in the tuple is in a specific position.

Basic Set Identities

Commutative, Associative, and Distributive Laws

Commutative Laws:

• The commutative law for union and intersection states that the order of sets does not affect the result of the operation.

Associative Laws:

• The associative law for union and intersection states that the grouping of sets does not affect the result.

Distributive Laws:

• The distributive law links union and intersection. It states that intersection distributes over union and vice versa.

De Morgan’s Laws

• De Morgan’s Laws describe the complement of unions and intersections. These laws are very important for simplifying expressions involving complements.

Example:
If $A=\{1,2,3\}$ and $B=\{3,4,5\}$ with universal set $U=\{1,2,3,4,5,6\}$, then:

• $A^{\prime }=\{4,5,6\}$
• $B^{\prime }=\{1,2,6\}$
• $(A\cup B{)}^{\prime }=\{6\}$ and $A^{\prime }\cap B^{\prime }=\{6\}$, showing that De Morgan's law holds.

Absorption and Idempotent Laws

Absorption Laws:

• The absorption law simplifies expressions involving both union and intersection.

Idempotent Laws:

• The idempotent law states that combining a set with itself does not change the set.

Double Complement Law

• The double complement law states that the complement of the complement of a set is the set itself.

Example:
If $A=\{1,2,3\}$ and the universal set $U=\{1,2,3,4,5\}$, then:

• $A^{\prime }=\{4,5\}$
• $(A^{\prime }{)}^{\prime }=A=\{1,2,3\}$

Proofs Using Venn Diagrams and Algebraic Techniques

Proof with Venn Diagrams:

• Venn Diagrams provide a visual representation of set operations and are useful for proving identities.

Example: Prove De Morgan’s Law $(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$ using a Venn diagram:

1. Draw two overlapping circles representing sets $A$ and $B$.
2. Shade the area outside the union of $A$ and $B$ to represent $(A\cup B{)}^{\prime }$.
3. Then, separately shade the intersection of $A^{\prime }$ and $B^{\prime }$ (the regions outside $A$ and $B$).
4. You will see that the shaded regions for both expressions are identical, proving the identity.

Proof with Algebraic Techniques:

• Algebraic proofs involve manipulating set expressions step by step, using known identities.

Example: Prove the absorption law $A\cup (A\cap B)=A$:

1. Start with $A\cup (A\cap B)$.
2. By the distributive law, we have:

3. By the idempotent law, $A\cup A=A$, so:

4. By the absorption law again, $A\cap (A\cup B)=A$. Therefore:

Example of De Morgan’s Law Using Algebraic Techniques:

• Start with $(A\cup B{)}^{\prime }$. By De Morgan’s Law, this is equal to $A^{\prime }\cap B^{\prime }$. To prove:

1. $(A\cup B{)}^{\prime }$ means all elements that are not in either $A$ or $B$.
2. $A^{\prime }\cap B^{\prime }$ means all elements that are not in $A$ and not in $B$.
3. Since both describe the same set (elements not in $A$ or $B$), they are equal, and thus:

Relations

Definitions

Ordered Pairs and Cartesian Products

• An ordered pair is a pair of elements $(a,b)$ where the order matters; $(a,b)\ne (b,a)$ unless $a=b$.
• The Cartesian product of two sets $A$ and $B$, denoted $A\times B$, is the set of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$:

• Example: If $A=\{1,2\}$ and $B=\{x,y\}$, then:

Binary Relations

• A binary relation from a set $A$ to a set $B$ is a subset of the Cartesian product $A\times B$. If $R$ is a binary relation, we write $aRb$ to mean that $(a,b)\in R$.
• If $R\subseteq A\times A$, it is called a binary relation on $A$.

Properties of Relations

Reflexive Relations

• A relation $R$ on a set $A$ is called reflexive if every element of $A$ is related to itself:

• Example: If $A=\{1,2\}$, the relation $R=\{(1,1),(2,2)\}$ is reflexive.

Symmetric Relations

• A relation $R$ on a set $A$ is called symmetric if whenever $aRb$, then $bRa$:

• Example: If $A=\{1,2\}$, the relation $R=\{(1,2),(2,1)\}$ is symmetric.

Antisymmetric Relations

• A relation $R$ on a set $A$ is called antisymmetric if whenever $aRb$ and $bRa$, then $a=b$:

• Example: If $A=\{1,2\}$, the relation $R=\{(1,1),(2,2)\}$ is antisymmetric, because no two distinct elements are mutually related.

Transitive Relations

• A relation $R$ on a set $A$ is called transitive if whenever $aRb$ and $bRc$, then $aRc$:

• Example: If $A=\{1,2,3\}$ and $R=\{(1,2),(2,3),(1,3)\}$, the relation $R$ is transitive.

Equivalence Relations

• A relation $R$ on a set $A$ is called an equivalence relation if it is reflexive, symmetric, and transitive.
• Example: The relation "is equal to" on a set of numbers is an equivalence relation because:
  • It is reflexive: $a=a$.
  • It is symmetric: If $a=b$, then $b=a$.
  • It is transitive: If $a=b$ and $b=c$, then $a=c$.

Equivalence Classes

• If $R$ is an equivalence relation on a set $A$, then the equivalence class of an element $a\in A$ is the set of all elements in $A$ that are related to $a$:

• Example: For the equivalence relation "has the same remainder when divided by 3" on the set of integers, the equivalence class of 1 includes numbers like $\{1,4,7,10,\dots \}$.

Partition of a Set

• A partition of a set $A$ is a collection of non-empty, disjoint subsets of $A$ whose union is $A$.
• Each equivalence class induced by an equivalence relation forms a partition of the set.
• Example: If $A=\{1,2,3,4\}$, a partition of $A$ might be $\{\{1,2\},\{3,4\}\}$.

Partial and Total Orders

Partial Orders

• A relation $R$ on a set $A$ is called a partial order if it is reflexive, antisymmetric, and transitive.
• A set with a partial order is called a partially ordered set or poset.
• Example: The "less than or equal to" relation $\le$ on the set of integers is a partial order.

Total Orders

• A partial order $R$ on a set $A$ is called a total order if every pair of elements in $A$ is comparable, i.e., for any $a,b\in A$, either $aRb$ or $bRa$.
• Example: The relation $\le$ on the set of natural numbers $\mathbb{N}$ is a total order because any two numbers can be compared.

Hasse Diagrams

• A Hasse diagram is a graphical representation of a finite partially ordered set.
• In a Hasse diagram:
  • Elements are represented by points.
  • There is a line from $a$ to $b$ if $aRb$ and there is no element $c$ such that $aRc$ and $cRb$.
  • The diagram omits arrows, assuming that lines go upward (i.e., $aRb$ means $b$ is above $a$).

Example:
For the set $A=\{1,2,3,4\}$ with the partial order $R=\le$, the Hasse diagram would look like this: