Chapter 2

2.1 Set theory

2.1.1. Sets.

A set is a collection of objects, called elements of the set.

A set can be represented by listing its elements between braces: A = {1, 2, 3, 4, 5}.

The symbol is used to express that an element is (or belongs to) a set.

Its negation is represented by .

If the set is finite, its number of elements is represented |A|,

e.g. if A = {1, 2, 3, 4, 5} then |A| = 5.

- Set-builder notation: An alternative way to define a set, called setbuilder

notation, is by stating a property (predicate) P(x) verified by exactly its elements.

- Principle of Extension. Two sets are equal if and only if they have

the same elements

- Subset

- Proper subset: if A B but A B

- Empty Set.

- Power Set. The collection of all subsets of a set A is called the

power set of A

2.1.2. Venn Diagrams

Venn diagrams are graphic representations of sets as enclosed areas in the plane

2.1.3. Set Operations

1. Intersection: giao

2. Union: hợp

3. Complement: phần bù, The set of elements (in the universal set) that do

not belong to a given set:

4. Difference or Relative Complement: hiệu

5. Symmetric Difference: Given two sets, their symmetric difference

is the set of elements that belong to either one or the other

set but not both.

A B = {x | (x A) (x B)} .

A B = A B - A B = (A-B) (B-A)

2.1.4. Counting with Venn Diagrams

2.1.5. Properties of Sets

1. Associative Laws: kết hợp

2. Commutative Laws: giao hoán

3. Distributive Laws: phân phối

4. Identity Laws:

5. Complement Laws:

6. Idempotent Laws:

7. Bound Laws:

8. Absorption Laws:

9. Involution Law:

10. 0/1 Laws:

11. DeMorgan's Laws:

2.1.6. Generalized Union and Intersection.

2.1.7. Partitions.

2.1.8. Ordered Pairs, Cartesian Product.

2.2. Functions

2.2.1. Correspondences.

2.2.2. Functions.

A function or mapping f from a set A to a set B, denoted f : A ! B, is a correspondence in which to each element x of A corresponds exactly one element y = f(x) of B

1. The floor function:

= greatest integer less than or equal to x .

2. The ceiling function:

= least integer greater than or equal to x .

Graph: The graph of a function f : A ! B is the subset of A × B

defined by G(f) = {(x, f(x)) | x A}

2.2.3. Types of Functions.

1. One-to-One or Injective: A function f : A B is called one - to-one or injective if each element of B is the image of at most one element of A

2. Onto or Surjective: A function f : A B is called onto or surjective if every element of B is the image of some element of A

3. One-To-One Correspondence or Bijective: function f : A B is said to be a one-to-one correspondence, or bijective, or a bijection, if it is one-to-one and onto

2.2.4. Identity Function. Given a set A, the function 1A : A !

A defined by 1A(x) = x for every x in A is called the identity function for A.

2.2.5. Function Composition

2.2.6. Inverse Function

2.2.7. Operators.

2.3. Relations

A relation R from a set A to a set B will be understood as a subset of the Cartesian

product A × B