[Discrete Mathematics] Sets and Funtions

21/09/2017 by Leave a Comment

1. Sets

  • A set is an unordered collection of objects, called elements or members of the set.
  • A set is said to contain its elements
  • $ a \in A $ if a is element of A
  • $ a \notin A $ if a is not element of A
  • Ways to describe set
    • List all the members of a set (Roster method). E.g $ A = \{a, b, c, d\} $ (Roster method)
    • Use set builder notation: $ X = \{ x \mid P(x) \} $$$ E.g \ \ O=\{x \mid x \ is \ odd\} $$
  • A is a subset of B if and only if every element of A is also an element of B.$$ A \subseteq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B) $$
  • Two sets are equal if and only if they have the same elements.$$ A = B \Leftrightarrow \forall x (x \in A \leftrightarrow x \in B) $$$$ A = B \Leftrightarrow A \subseteq B \land B \subseteq A $$
  • The empty set: $\emptyset$$$ For \ every \ set \ \emptyset \subseteq S, S \subseteq S $$
  • Given a set $S$, the power set of $S$ is the set of all subsets of the set S. The power set of S is denoted by $\mathcal{P}(S)$

2. Set operations

  • The union of the sets A and B is the set that contains those elements that are either in A or in B, or in both.$$ A \cup B = \{x \mid x \in A \lor x \in B \} $$
  • The intersection of the sets A and B is the set containing those elements in both A and B.$$ A \cap B = \{x \mid x \in A \land x \in B \} $$
  • The difference of A and B is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A.$$ A \setminus B = \{ x \mid x \in A \land x \notin B \} $$

Table set identies

To be done

3. Cartesian product

  • The ordered n-tuple (a1, a2, . . . , an) is the ordered collection that has a1 as its first element, a2 as its second element, . . . , and an an as its nth element.
  • The Cartesian product of the sets A1, A2, . . . , An, denoted by A1 x A2 x · · · x An, is the set of ordered n-tuples (a1, a2, . . . , an), where ai belongs to Ai for i = 1, 2, . . . , n.$$A_1 × A_2 × · · · × A_n = \{ \ (a_1, a_2, . . . , a_n) \mid a_i ∈ A_i, i = 1, 2, . . . , n \ \} $$

4. Function

  • Let X and Y be nonempty sets. A function f from X to Y is an assignment of exactly one element of X to each element of Y$$ f : X \to Y $$
  • A function f is said to be one-to-one, or an injunction, if and only if f(a) = f (b) implies that a = b for all a and b in the domain of f (Injunctive)$$ \forall a \forall b (a \neq b \rightarrow f(a) \neq f(b)) $$
  • A function f from X to Y is called onto, or a surjection, if and only if for every element y ∈ Y there is an element x ∈ X with f(x) = y (Surjective)$$ \forall y \in Y, \exists x \in X : f(x) = y $$
  • A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. (Bijective)$$ \forall y \in Y, \exists ! x \in X : f(x) = y $$
  • Let f be a function from the set X to the set Y and let g be a function from the set y to the set C. The composition of the functions g and f, is defined by is defined by (f ◦ g)(a) = f (g(a)).

5. Cardinality of Sets

Definition

The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.

To be done

References

  • Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen
  • Đại số tuyến tính, Nguyễn Hữu Việt Hưng
Chủ đề: Toán rời rạc Mức độ:
Khuyên dùng

 

Speak Your Mind

*