Methodos Primers 1: Sets, Relations, Functions

Methodos Primers 1: Sets, Relations, Functions

1. Sets

2. Relations

3. Functions

1.2 Subsets, Power Sets, Equality of Sets

1.3 Finite and Infinite Sets

1.5 De Morgan Rules, Distributivity, Tables

2.1 Ordered Pairs, Cartesian Products

1. Definition 2.2.2. Let R be a relation on A. Then,

   • dom R = {x ∈ A : There exists some y ∈ A such that hx, yi ∈ R}. dom R is called the domain of R.

   • ran R = {y ∈ A : There exists some x ∈ A such that hx, yi ∈ R} is called the range of R.

   • Finally, fld R = dom R ∪ ran R is called the field of R. Observe that dom R, ran R, and fld R are all subsets of A.

2. Definition 2.2.3. Let R be a relation on A; then R˘ = {<y, x> : <x, y> ∈ R} is called the converse of R.

3. Definition 2.2.4. Let R and S be relations on A; then R ◦ S = {hx, zi : there is a y ∈ A such that xRy and ySz}. The operation ◦ is called the composition or the relative product of R and S.

2.3 Ordering Relations

1. Definition 2.3.1. Let R be a relation on A.

   1. R is reflexive if hx, xi ∈ R for all x ∈ A.

   2. R is antisymmetric if for all x, y ∈ A, hx, yi ∈ R and hy, xi ∈ R implies x = y.

   3. R is transitive if for all x, y, z ∈ A, hx, yi ∈ R and hy, zi ∈ R implies hx, zi ∈ R.

   4. R is a partial order on A, if R is reflexive, antisymmetric, and transitive. Sometimes we will call a partial order on A just an order on A, or an ordering of A.

   5. R is a linear order on A if R is a partial order, and xRy or yRx for all x, y ∈ A, i.e. if any two elements of A are comparable with respect to R.

2.4 Equivalence Relations

1. Definition 2.4.1. A relation R on a set A is called symmetric if ha, biR implies hb, aiR for all a, bA; in other words, R is symmetric if R = R˘. R is called an equivalence relation if R is reflexive, transitive and symmetric.

2. Definition 2.4.2. Let A be a non-empty set. A family P of non-empty subsets of A is called a partition of A, if every element of A is in exactly one element of P. In other words,

3.1 Basic Definitions

1. Definition 3.1.1. A function is an ordered triple hf, A, Bi such that

   1. A and B are sets, and f ⊆ A × B,

   2. For every x ∈ A there is some y ∈ B such that hx, yi ∈ f

   3. If hx, yi ∈ f and hx, zi ∈ f, then y = z; in other words, the assignment is unique in the sense that an x ∈ A is assigned at most one element of B.

   • A is called the domain of f, and B its codomain.

2. we must keep in mind that a function is only properly defined if we also give a domain and a codomain!

3. Definition 3.1.2. Let f : A → B be a function.

   1. If A = B and f(x) = x for all x ∈ A, the f is called the identity function on A, and it is denoted by id A .

   2. If A ⊆ B and f(x) = x for all x ∈ A, then f is called the inclusion function from A to B, or, if no confusion can arise, simply the inclusion. Observe that, if A = B and f is the inclusion, then f is in fact the identity on A.

   3. If f(x) = x for some x ∈ A, then x is called a fixed point of f.

   4. If f(x) = b for all x ∈ A, then f is called a constant function.

   5. If g : C → D is a function such that A ⊆ C, B ⊆ D, and f ⊆ g, then g is called an extension of f over C, and f is called the restriction of g to A.

4. Definition 3.1.3. Let f : A → B and g : C → D be functions such that ran f ⊆ dom g. Then the function g ◦f : A → C defined by (g ◦f)(x) = g(f(x)) is called the (functional) composition of f and g.

   1. Lemma 3.1.1. If f and g are functions such that ran f ⊆ dom g, then dom(g ◦ f) = dom f, and codom(g ◦ f) = codom g.

   2. Lemma 3.1.2. Let f : A → B, g : B → C, h : C → D be functions. Then, h ◦ (g ◦ f) = (h ◦ g) ◦ f, i.e. the composition of functions is associative.

3.2 One–one, Onto, and Bijective Functions

1. Definition 3.2.1. Let f : A → B be a function.

   1. f is called onto or surjective if codom f = ran f.sometimes indicate this by writing f : A ։ B.

   2. f is called one–one or injective if for all x, y ∈ A, f(x) = f(y) implies x = y. If f is injective, we sometimes indicate this by writing f : A ֒→ B.

   3. f is called bijective if f is onto and one-one.

2. Lemma 3.2.1. Let f : A → B be a function; then g : A → ran f defined by g(x) = f(x) for all x ∈ A is onto.

3. Definition 3.3.2. Let A = {1, 2, 3, . . . , n}, and f : A → A be a bijective function; then f is called a permutation on n.

1. Discrete Mathematics II (Spring 2015)

2. Sets, Relations, Functions