Extended: Sets, Relations, and Functions in Discrete Mathematics

See also: https://chatgpt.com/c/670706b7-3788-8005-aa7f-330849b0f49e

Sets, relations, and functions are foundational concepts in discrete mathematics and computer science. They form the building blocks for various advanced topics such as logic, combinatorics, graph theory, and algorithms. Understanding these concepts is essential for modeling and solving problems in computer science.

In this lecture, we will explore these concepts in detail, progressing from basic definitions to more advanced properties and applications:

1. Sets
2. Cartesian Products
3. Relations
4. Functions

We will also address common confusions and include remarks to clarify key points.

A set is a collection of distinct objects, called elements or members of the set. Sets are a fundamental way to represent and organize objects in mathematics and computer science.

• Notation: Sets are usually denoted by uppercase letters, e.g., ( A ), ( B ), ( S ).
• Elements: Elements of sets are denoted by lowercase letters, e.g., ( a ), ( b ), ( x ).

An element ( x ) is a member of a set ( A ) if ( x ) belongs to ( A ), written as ( x \in A ).

Important Points about Sets:

1. Order does not matter: The set ( {1, 2, 3} ) is the same as ( {3, 2, 1} ).
2. No repetition of elements: The set ( {1, 2, 2, 3} ) is the same as ( {1, 2, 3} ).

Remark:

• Sets are unordered collections of distinct elements.

Common Confusions:

• Sets vs. Lists/Sequences: Remember that sets are different from lists or sequences. In sets, the order and repetition of elements are not considered.
• Element vs. Subset: Be careful to distinguish between elements and subsets. For example, ( 3 \in {1, 2, 3} ), but ( {3} \subseteq {1, 2, 3} ).

Sets are typically represented using set-roster notation, where elements are listed within curly braces ( {} ) and separated by commas.

• Example: ( A = {1, 2, 3} ).

We can also use an ellipsis ( \ldots ) to indicate a continuing pattern in a set.

• Example: ( {1, 2, 3, \ldots, 100} ) represents the set of integers from 1 to 100.

Remark:

• When using an ellipsis ( \ldots ), ensure the pattern is clear and unambiguous.

Common Confusions:

• Difference Between ( \in ) and ( \subseteq ):
  • ( a \in A ) means that ( a ) is an element of set ( A ).
  • ( A \subseteq B ) means that ( A ) is a subset of ( B ), i.e., every element of ( A ) is also in ( B ).

Examples of Correct Notation:

• ( 3 \in {1, 2, 3} ).
• ( {1, 2} \subseteq {1, 2, 3} ).

Examples of Incorrect Notation:

• ( x \subseteq 4 ) (Incorrect because 4 is an element, not a set).
• ( {1, 2} \in {1, 2, 3} ) (Incorrect; sets are not elements unless specified).

Remark:

• Be careful with notation to avoid confusion between elements and subsets.

• Natural Numbers Less Than 5: ( {0, 1, 2, 3, 4} ).
• Vowels in the English Alphabet: ( {\text{a}, \text{e}, \text{i}, \text{o}, \text{u}} ).
• Programming Languages: ( {\text{Python}, \text{Java}, \text{C++}} ).
• Set of Countries: ( {\text{Brazil}, \text{India}, \text{Nigeria}, \text{Japan}} ).
• Set of Names: ( {\text{Aaliyah}, \text{Haruki}, \text{Ximena}, \text{Youssef}} ).
• Nested Set: ( S = {1, {2, 3}} ). This set has two elements: the number 1 and the set ( {2, 3} ).

Remark:

• Sets can contain other sets as elements. In such cases, the nested set is considered a single element of the outer set.

Common Confusions:

• When counting the number of elements in a set, nested sets are counted as single elements.
  • Example: ( {{}} ) is a set containing one element—the empty set.

The empty set is the set containing no elements. It is denoted by ( \emptyset ) or ( {} ).

Examples:

• ( \emptyset = {} ).
• ( {\emptyset} ) is a set containing one element—the empty set.

Common Confusions:

• The empty set ( \emptyset ) is not the same as the number zero ( 0 ) or the set ( {0} ).
  • ( \emptyset ) has zero elements.
  • ( {0} ) has one element, the number zero.

Remark:

• Be careful to distinguish between ( \emptyset ), ( 0 ), and ( {0} ).

Certain sets are used so frequently that they have special symbols:

• Natural Numbers (( \mathbb{N} )): The set of non-negative integers.
  • ( \mathbb{N} = {0, 1, 2, 3, \ldots} ).
  • Note: In this class, ( 0 \in \mathbb{N} ).
• Integers (( \mathbb{Z} )): The set of whole numbers, both positive and negative, including zero.
  • ( \mathbb{Z} = {\ldots, -2, -1, 0, 1, 2, \ldots} ).
• Rational Numbers (( \mathbb{Q} )): Numbers that can be expressed as fractions of integers.
  • ( \mathbb{Q} = \left{ \dfrac{p}{q} ,\middle|, p, q \in \mathbb{Z},\ q \neq 0 \right} ).
• Real Numbers (( \mathbb{R} )): All numbers on the number line, including irrational numbers like ( \sqrt{2} ), ( \pi ), ( e ).

Superscripts for Positivity/Negativity:

• ( \mathbb{N}^+ ) or ( \mathbb{N}_{>0} ): Positive natural numbers (excluding zero).
• ( \mathbb{Z}^+ ) or ( \mathbb{Z}_{\geq 0} ): Non-negative integers (including zero).

Common Confusions:

• Is ( 0 ) part of ( \mathbb{N}^+ ) or ( \mathbb{N}^- )?
  • Answer: No, ( 0 ) is neither positive nor negative.
• Is ( 1.0 ) a rational number?
  • Answer: Yes, because ( 1.0 = \dfrac{1}{1} ), and both numerator and denominator are integers.

Remark:

• Be aware that the inclusion of zero in ( \mathbb{N} ) can vary by context. In this class, ( 0 \in \mathbb{N} ).

• Definition: Lists all elements explicitly within curly braces.
• Example: ( A = {1, 2, 3} ).
• Using Ellipsis: To indicate a pattern continues.
  • Example: ( {1, 2, 3, \ldots, 100} ) represents integers from 1 to 100.

Remark:

• When using an ellipsis ( \ldots ), ensure the pattern is clear and unambiguous.

Common Confusions:

• Can ( 4.5 ) be in the set ( {1, 2, 3, \ldots, 5} )?
  • Answer: Typically not, unless specified, as the pattern implies integer increments.
• Is “between” inclusive of endpoints?
  • Answer: It depends on the notation. Inequalities like ( < ) and ( > ) are not inclusive, whereas ( \leq ) and ( \geq ) are inclusive.

• Definition: Specifies a set by stating a property that its members must satisfy.
• General Form: ( S = { x \in D \mid \text{condition involving } x } ), where ( D ) is the domain.
• Examples:
  • ( A = { x \in \mathbb{N} \mid x \text{ is even and } x \leq 10 } = {0, 2, 4, 6, 8, 10} ).
  • ( B = { x \in \mathbb{Z} \mid -2 < x < 5 } = {-1, 0, 1, 2, 3, 4} ).

Common Confusions:

• Is ( {2, 4, \ldots, 10} ) set-builder notation?
  • Answer: No, that’s roster notation using an ellipsis.
• Can set-builder notation represent infinite sets?
  • Answer: Yes, it’s especially useful for defining infinite sets.

Remark:

• Set-builder notation allows for a concise representation of sets, especially when listing all elements is impractical.

A set ( A ) is a subset of a set ( B ) if every element of ( A ) is also an element of ( B ), denoted as ( A \subseteq B ).

• If ( A \subseteq B ) and ( A \neq B ), then ( A ) is a proper subset of ( B ), denoted as ( A \subset B ).

Notation:

• Subset: ( A \subseteq B ).
• Proper Subset: ( A \subset B ).

Examples:

• ( {1, 2} \subseteq {1, 2, 3} ).
• ( {1, 2, 3} \subseteq {1, 2, 3} ) (Every set is a subset of itself).
• ( \mathbb{Q} \subseteq \mathbb{R} ).

Common Confusions:

• Element vs. Subset:
  • ( 1 \in {1, 2, 3} ): ( 1 ) is an element of the set.
  • ( {1} \subseteq {1, 2, 3} ): ( {1} ) is a subset of the set.
• Is ( 7 \subseteq {7} )?
  • Answer: No, ( 7 ) is an element, not a set.
• Is ( {7} \subseteq X ) if ( X = {7} )?
  • Answer: Yes, ( {7} \subseteq {7} ).

Remark:

• The empty set ( \emptyset ) is a subset of every set: ( \emptyset \subseteq A ).
• Be careful not to confuse elements with singleton subsets.

Venn diagrams are visual representations of sets and their relationships.

• Universal Set (( U )): The set containing all possible elements under consideration.
• Subsets: Represented as circles or ovals within the universal set.

Examples:

• Illustrating Subsets:
  • Drawing circle ( A ) inside circle ( B ) represents ( A \subseteq B ).
• Set Operations:
  • Union (( A \cup B )): The area covered by both circles ( A ) and ( B ).
  • Intersection (( A \cap B )): The overlapping area of circles ( A ) and ( B ).
  • Difference (( A - B )): The part of circle ( A ) that does not overlap with ( B ).

Common Confusions:

• Is the empty set ( \emptyset ) an element of every set?
  • Answer: No, ( \emptyset ) is a subset of every set but is not necessarily an element unless specified.

Remark:

• Venn diagrams help visualize relationships between sets, especially for understanding set operations and subsets.

• Definition: The set of all elements that are in ( A ), or in ( B ), or in both.
• Notation: ( A \cup B = { x \mid x \in A \text{ or } x \in B } ).

• Definition: The set of all elements that are in both ( A ) and ( B ).
• Notation: ( A \cap B = { x \mid x \in A \text{ and } x \in B } ).

• Definition: The set of all elements that are in ( A ) but not in ( B ).
• Notation: ( A - B = { x \mid x \in A \text{ and } x \notin B } ).

• Definition: The set of all elements in the universal set ( U ) that are not in ( A ).
• Notation: ( \overline{A} = { x \in U \mid x \notin A } ).

• Union: ( {1, 2, 3} \cup {2, 4, 6} = {1, 2, 3, 4, 6} ).
• Intersection: ( {\text{red}, \text{blue}} \cap {\text{blue}, \text{yellow}} = {\text{blue}} ).
• Difference: ( {\text{dog}, \text{cat}, \text{bird}} - {\text{bird}} = {\text{dog}, \text{cat}} ).
• Complement: If ( U = {\text{apple}, \text{banana}, \text{orange}, \text{grape}} ) and ( A = {\text{apple}, \text{banana}} ), then ( \overline{A} = {\text{orange}, \text{grape}} ).

Mathematical Definitions (Using set-builder notation):

• Union: ( A \cup B = { x \in U \mid x \in A \text{ or } x \in B } ).
• Intersection: ( A \cap B = { x \in U \mid x \in A \text{ and } x \in B } ).
• Difference: ( A - B = { x \in U \mid x \in A \text{ and } x \notin B } ).
• Complement: ( \overline{A} = { x \in U \mid x \notin A } ).

Common Confusions:

• Is ( B - A ) the same as ( \overline{A} )?
  • Answer: Not necessarily, unless ( B = U ).
• When ( U ) is not specified, how do we find the complement?
  • Answer: The complement is relative to a universal set ( U ) that should be clear from context.
• Can we write the complement as ( A’ )?
  • Answer: Yes, ( A’ ) is another notation for the complement of ( A ).

Remark:

• Be precise with notation to avoid ambiguity.

Let ( A = {1, 2, 3} ), ( B = {3, 4, 5} ), and ( U = {1, 2, 3, 4, 5, 6} ).

• Union: ( A \cup B = {1, 2, 3, 4, 5} ).
• Intersection: ( A \cap B = {3} ).
• Difference:
  • ( A - B = {1, 2} ).
  • ( B - A = {4, 5} ).
• Complement:
  • ( \overline{A} = U - A = {4, 5, 6} ).
  • ( \overline{B} = U - B = {1, 2, 6} ).

Remark:

• Set difference is not commutative: ( A - B \neq B - A ).

• Union: ( A \cup B = B \cup A ).
• Intersection: ( A \cap B = B \cap A ).

• Union: ( A \cup (B \cup C) = (A \cup B) \cup C ).
• Intersection: ( A \cap (B \cap C) = (A \cap B) \cap C ).

• Union over Intersection: ( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) ).
• Intersection over Union: ( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) ).

• Union with Empty Set: ( A \cup \emptyset = A ).
• Intersection with Universal Set: ( A \cap U = A ).

• Union with Universal Set: ( A \cup U = U ).
• Intersection with Empty Set: ( A \cap \emptyset = \emptyset ).

• Complement of Union: ( \overline{A \cup B} = \overline{A} \cap \overline{B} ).
• Complement of Intersection: ( \overline{A \cap B} = \overline{A} \cup \overline{B} ).

Common Confusions:

• Associative vs. Commutative Laws:
  • Commutative Law: Changing the order of the operands.
    • ( A \cup B = B \cup A ).
  • Associative Law: Changing the grouping of operands.
    • ( (A \cup B) \cup C = A \cup (B \cup C) ).

Remark:

• These properties are fundamental and help simplify set expressions.

Given ( A = {1, 2, 3} ), ( B = {3, 4} ), and ( U = {1, 2, 3, 4, 5} ).

• Find ( \overline{A \cup B} ).
  • ( A \cup B = {1, 2, 3, 4} ).
  • ( \overline{A \cup B} = U - (A \cup B) = {5} ).
• Find ( \overline{A} \cap \overline{B} ).
  • ( \overline{A} = U - A = {4, 5} ).
  • ( \overline{B} = U - B = {1, 2, 5} ).
  • ( \overline{A} \cap \overline{B} = {5} ).
• Conclusion: ( \overline{A \cup B} = \overline{A} \cap \overline{B} ).

Remark:

• De Morgan’s Laws are useful for simplifying expressions involving complements.

• Definition: The number of elements in a set ( A ), denoted ( |A| ).
• Examples:
  • ( |A| = 3 ) if ( A = {1, 2, 3} ).
  • ( |\emptyset| = 0 ).

Common Confusions:

• Does cardinality account for duplicate elements?
  • Answer: No, since sets do not have duplicate elements.
• Does nesting affect cardinality?
  • Answer: Each nested set is counted as one element.

• Definition: The set of all subsets of ( A ), including ( A ) and ( \emptyset ), denoted ( \mathcal{P}(A) ).
• Formula: If ( |A| = n ), then ( |\mathcal{P}(A)| = 2^n ).

Examples:

• Let ( A = {a, b} ).
  • Subsets: ( \emptyset ), ( {a} ), ( {b} ), ( {a, b} ).
  • Power Set: ( \mathcal{P}(A) = {\emptyset, {a}, {b}, {a, b}} ).
  • Cardinality: ( |\mathcal{P}(A)| = 4 ).

Remark:

• The power set includes all possible combinations of elements from ( A ).
• Question: Is the cardinality of the power set always ( 2^n )?
  • Answer: Yes, where ( n ) is the number of elements in the original set.

[The lecture notes would continue with sections on Cartesian Products, Relations, and Functions, integrating relevant examples, remarks, and clarifications based on the students’ questions.]

1. Set Operations:
   • Given ( A = {2, 4, 6, 8} ) and ( B = {4, 8, 12} ), find:
     • ( A \cup B )
     • ( A \cap B )
     • ( A - B )
     • ( \overline{A} ), assuming universal set ( U = {2, 4, 6, 8, 10, 12} )
2. Power Set and Cardinality:
   • Find the power set ( \mathcal{P}(C) ) for ( C = {x, y} ).
   • What is ( |\mathcal{P}(C)| )?
3. Relation Properties:
   • For relation ( R ) on ( \mathbb{Z} ) defined by ( a, R, b ) if ( a - b ) is divisible by ( 5 ):
     • Is ( R ) reflexive?
     • Is ( R ) symmetric?
     • Is ( R ) transitive?
     • Is ( R ) antisymmetric?
4. Function Classification:
   • Determine if the function ( f: \mathbb{N} \rightarrow \mathbb{N} ) defined by ( f(n) = 2n ) is:
     • Injective
     • Surjective
5. Inverse Function:
   • Given ( f: \mathbb{R} \rightarrow \mathbb{R} ), ( f(x) = 3x - 7 ), find the inverse function ( f^{-1}(x) ).

End of Lecture Notes

By incorporating these additions and clarifications, the lecture notes aim to provide clearer explanations, address common student questions, and ensure a logical progression of topics.