Linear Algebra: Functions

Relations, functions, inverse relations/functions, set cardinality.

70 flashcards · Mathematics · by lakesare

1. What is the definition of a relation from A to B?

   Basically relation R from A to B is any subset of A × B. Let A = {0, 1, 2} and B = {1, 2, 3} and let us say that an element x in A is related to an element y in B if, and only if, x is less than y. Let us use the notation xRy as a shorthand for the sentence “x is related to y.” 0 R 1 since 0 < 1, 1 !R 1 since 1 !< 1

2. Rewrite x R y.

   (x, y) ∈ R

3. Define a function from the point of view of sets/relations.

   A relation F from A to B is a function if, and only if: Every element of A must be mapped to some element of B And ONLY ONE element of B So, if x ∈ A and y ∈ B, relation F = {(each x is present, y), ...} and {(x, only y is mapped to x and nothing else)}. This definitions presents function as a set of ordered pairs.

4. Let A = {2, 4, 6} and B = {1, 3, 5}. Which of the relations R, S, and T defined below are functions from A to B? R = {(2, 5), (4, 1), (4, 3), (6, 5)} For all (x, y) ∈ A × B, (x, y) ∈ S means that y = x + 1. T is defined by the arrow diagram

   relation R is not a function (doesn't satisfy property 2: {(4, 1), (4, 3)} - not only one element from B maps to each element of A) relation S is not a function (doesn't satisfy property 1: 6+1=7, but 7 is not present in B) relation T is a function A relation F from A to B is a function if, and only if: Every element of A must be mapped to some element of B And ONLY ONE element of B

5. Functions VS relations?

   Relation from A to B is just any subset of a cartesian product A × B. Any function IS a relation, but function must also have these 2 properties: Every element of A must be mapped to some element of B And ONLY ONE element of B

6. Which of these relations are functions?

7. Domain vs codomain vs image vs range?

   F: A -> B Domain: what can go into a function Codomain: what may possibly come out Image: ==range Range: what actually comes out of a function Example: we can define a function f(x)=2x with a domain and codomain of integers (because we say so).But by thinking about it we can see that the range (actual output values) is just the even integers.So the codomain is integers (we defined it that way), but the range is even integers. Links: mathopolis quiz!

8. f: A → B (read as f is a function from A to B) What does this notation mean?

   f: A → B: if x is an element of set A, then f(x) is an element of set B.

9. g(x, y) = 2x + y. Where x and y are integers. Express this function in notation.

   g: (Z×Z) → Z Input (domain) can be represented as a cartesian product of two Zs, which would result in a set of 2-tuples: {(0, 0), (0, 1)...}.

10. Consider relation C: For all (x, y) ∈ R × R, (x, y) ∈ C means that x2 + y2 = 1. Is relation C a function?

    No. We know that x2 + y2 = 1 is a circle on a cartesian graph. Therefore for a single x value there will be 2 y values! Which goes against the 2nd property of a function: Every element of A must be mapped to some element of B And ONLY ONE element of B

11. Given sets A and B, a relation from A to B is ______.

    Any subset of the Cartesian product A × B

12. A function F from A to B is a relation from A to B that satisfies the following two properties: for every element x of A, there is _______. for all elements x (in A), and y and z (in B), if ____ then ______.

    an element y of B such that (x, y) ∈ F (x, y) ∈ F and (x,z) ∈ F; y = z

13. When are functions f and g considered equal?

    If f and g are functions from a set A to a set B, f = g iff f(x) = g(x) for all x in A. If two functions are equal is just a question of comparing two sets. It holds if both contain exactly the same elements (x,f(x)). Thus, they must have the same domain.However it's not required that they have the same CO-DOMAIN, different texts have different definitions for function equality in this sense: https://math.stackexchange.com/a/91962/163615

14. How is this read?

    f sends x to y, or f maps x to y

15. What's meant by: the image of x under f?

    Just f(x). The unique element to which f sends x.

16. Write a set definition: range of f = image of X under f = ...

    range of f = image of X under f = { y ∈ Y | y = f(x), where x ∈ X } (Y is a co-domain of f, X is a domain of f)

17. What's a preimage?

    preimage of y = {x ∈ X | f(x) = y} Same with inverse image.

18. What's an inverse image?

    the inverse image of y = {x ∈ X | f(x) = y} Same with preimage.

19. What's an identity function?

    Identity function on X: I(x) = x for all x ∈ X Thus the identity function can be pictured as a machine that sends each piece of input directly to the output chute without changing it in any way.

20. What's Hamming distance function?

    It's a function giving a measure of the 'difference' between two strings of 0's and 1's (that have the same length). H(s, t) = the number of positions in which s and t have different values H: Sn × Sn → Z nonnegwhere Sn: set of all strings of 0s and 1s of length n

21. Find Hamming distance: H(11000, 00000) = ?

    H(11000, 00000) = 2

22. What's a Boolean function?

    An (n-place) Boolean function f is a function whose: DOMAIN: set of all n-tuples of 0’s and 1’s, CO-DOMAIN: set {0, 1}.

23. Denote an n-place Boolean function in a f: Domain -> Co-domain notation.

    f: {0, 1}n → {0, 1} {0, 1}n = {0, 1} × {0, 1} × n copies! => {(0, 0, 0), (0, 0, 1), ..., (111)} More formally, the domain of a Boolean function can be described as the Cartesian product of n copies of the set {0, 1}, which is denoted {0, 1}n.

24. When we write f(a, b) we mean f((a, b)).

25. What does {0, 1}n signify?

    {0, 1}n = {0, 1} × {0, 1} × n copies! => {(0, 0, 0), (0, 0, 1), ..., (111)}

26. 3-place Boolean function is defined as: f(x1, x2, x3) = (x1 + x2 + x3) mod 2 Find f(1, 1, 1).

    f(1, 1, 1) = (1 + 1 + 1) mod 2 = 3 mod 2 = 1

27. We can input a set of inputs into function and get a set of results back. Find: F({1, 4}) F({1, 2, 3, 4})

    F({1, 4}) = {b} F({1, 2, 3, 4}) = {a, b, d}

28. f : X → Y A ⊆ X and C ⊆ Y Express in set notation: image of A: f(A) inverse image of C: f−1(C)

    f(A) = { y ∈ Y | y = f(x) where x ∈ A } f−1(C) = { x ∈ X | f (x) ∈ C }

29. Let X = {1, 2, 3, 4} and Y = {a, b, c, d, e}. Let A = {1, 4}, C = {a, b}, and D = {c, e}. Find: F(A) F(X) F−1(C) F−1(D)

    F(A) = { b } F(X) = { a, b, d } F−1(C) = { 1, 2, 4 } F−1(D) = ∅

30. Find all functions from X = {a, b} to Y = {u, v}.

    {(a, u), (b, u)} {(a, v), (b, v)} {(a, u), (b, v)} {(a, v), (b, u)}

31. Evaluate:

    This is an identity function defined on the set of all integers. Result is bijk.

32. Complete a definition of a one-to-one function: F: X → Y is one-to-one ⇔ ______________________.

    F: X → Y is one-to-one ⇔ ∀ x1, x2 ∈ X if F(x1) = F(x2) then x1 = x2. One-to-one functions are also called injective.

33. f: R → R f(x) = 4x − 1 for all x ∈ R Is f one-to-one? Prove or give a counterexample.

    We must prove that if f(a) = f(b) => a = b. f(a) = 4a - 1 f(b) = 4b - 1 f(a) = f(b) => 4a - 1 = 4b - 1 => 4a = 4b => a = b

34. What's injective function?

    One-to-one function.

35. Complete a definition of an onto function: F: X → Y is onto ⇔ ______________________.

    F: X → Y is onto ⇔ ∀ y∈Y, there exists x∈X such that F(x) = y. Onto functions are also called surjective.

36. Are these two functions onto and/or one-to-one?

    one-to-one function, but not onto onto function, but not one-to-one

37. page 431: TODO Example 7.2.5 Proving or Disproving That Functions Are Onto

    page 431: TODO Example 7.2.5 Proving or Disproving That Functions Are Onto

38. For any positive real numbers b, c and x with b != 1 and c != 1:

39. What's a one-to-one correspondence (or bijection)?

    Function F: X → Y that is both one-to-one, and onto.

40. Plot the graphs of the power functions p0, p1/2, p1, and p2 on the same coordinate axes.

41. What's a floor function?

    The floor of a number is the integer immediately to its left on the number line.

42. Graph the floor function.

43. Find inverse function f-1(y) for f(x) = 4x − 1.

    f−1(y) = (y + 1) / 4

44. Define Floor: R→Z by the formula Floor(x) = ⌊x⌋, for all real numbers x . a. Is Floor one-to-one? b. Is Floor onto?

    a. Floor is NOT one-to-one. Floor(5.5) = 5; Floor(5.9) = 5; But 5.5 !== 5.9.b. Floor IS onto.

45. Name 2 ways to denote: composition of f and g.

    (g ◦ f)(x) g(f(x)) where g ◦ f is read “g circle f”and g(f(x)) is read “g of f of x.”

46. f(n) = n + 1 g(n) = n2 Find the compositions: 1. g ◦ f 2. f ◦ g.

    1. g ◦ f = g(f(x)) = g(x + 1) = (x + 1)2 2. f ◦ g = f(g(x)) = f(x2) = x2 + 1

47. What does IX denote?

    Identity function on set X.

48. Definition of same cardinality: Let A and B be any sets. A has the same cardinality as B if, and only if, there exists some bijective function from A to B. Let 2Z be the set of all even integers. Prove that 2Z and Z have the same cardinality.

    Consider function H(n) = 2n from Z to 2Z. Let's prove that H is bijective: one-to-one - suppose H(n1) = H(n2) for some integers n1 and n2. Then 2n1 = 2n2 by definition of H, and dividing both sides by 2 gives n1 = n2. Hence h is one-to-one. onto - suppose m is any element of 2Z. Then m is an even integer, and so m = 2k for some integer k. It follows that H(k) = 2k = m. Thus there exists k in Z with H(k) = m, and hence H is onto. Therefore, by definition of cardinality, Z and 2Z have the same ca…

49. Suppose f : X → Y and g: Y → Z are both one-to-one functions. Prove that g ◦ f is one-to-one.

50. e. Draw the graph of L as a subset of the Cartesian plane R × R

    a. no b. yes c. no d. yes e.

51. Define a relation E from Z to Z as follows: For all (m, n) ∈ Z × Z, m E n ⇔ m − n is even List two integers that are related by E to 1. Prove that if n is any odd integer, then n E 1.

    1. 3 is related by E to 1 (because 3 - 1 is even) 5 is related by E to 1 (because 5 - 1 is even) 2. We must prove that n - 1 is even. If n is any odd integer, then n = 2 * int_1 + 1. 2 * int_1 + 1 - 1 = 2 * int_1 is even by definition.

52. Define the inverse of a relation via set notation.

    R−1 = { (y, x) ∈ B × A | (x, y) ∈ R }

53. Let A = { 2, 3, 4 } and B = { 2, 6, 8 } and let R be: For all (x, y) ∈ A × B, x R y ⇔ x | y. State explicitly which ordered pairs are in: R R−1

    R = { (2,2), (2,6), (2,8), (3,6), (4,8) } R−1 = { (2,2), (6,2), (8,2), (6,3), (8,4) }

54. What's meant by a 'relation on a set A'?

    Relation from A to A.

55. Suppose a function F: X → Y is one-to-one but not onto. Is F−1 (the inverse relation for F) a function?

56. We define a relation R on A = { 0, 1, 2, 3 } by R = { (0,0), (1, 2), (2, 2) }. Draw the directed graph of R.

57. Here is a directed graph for a relation R: Let A = { 2,3,4,6,7,9 } and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 3 | (x−y). Explain why is it: reflexive symmetric transitive

    reflexive: Each point of the graph has an arrow looping around from it back to itself. symmetric: In each case where there is an arrow going from one point to a second, there is an arrow going from the second point back to the first. transitive: In each case where there is an arrow going from 1st point to 2nd, and from 2nd to 3rd, there is arrow from 1st point to 3rd. That is, there are no “incomplete directed triangles” in the graph. 1. R is reflexive ⇔ for all x in A, (x, x)∈R. 2. R is symmet…

58. Let R be a relation on a set A. 1. R is reflexive ⇔ ? 2. R is symmetric ⇔ ? 3. R is transitive ⇔ ?

    1. R is reflexive ⇔ for all x in A, (x, x)∈R. 2. R is symmetric ⇔ for all x and y in A, if (x, y)∈R then (y,x)∈R. 3. R is transitive ⇔ for all x, y, z in A, if (x, y)∈R and (y, z)∈R then (x, z)∈R.

59. Define relations S and T on A={0, 1, 2, 3} as: S = {(0, 0), (0, 2), (0, 3), (2, 3)} T = {(0,1),(2,3)} Is S reflexive? symmetric? transitive? Is T reflexive? symmetric? transitive?

    S is NOT reflexive: There is no loop at 1, for example. Thus (1, 1) ∈/ S, and so S is not reflexive. S is NOT symmetric: There is an arrow from 0 to 2 but not from 2 to 0. Hence(0,2) ∈ S but (2, 0) ∈/ S, and so S is not symmetric. S is transitive: There are three cases for which there is an arrow going from one point of the graph to a second and from the second point to a third: Namely, from 0 to 2 and from 2 to 3; from 0 to 0 and from 0 to 2; from 0 to 0 and from 0 to 3. In each case there is…

60. What is the difference between definitions of [reflexive] and [symmetric, transitive] relations?

    Reflexive relation is the only one that defines an actual relation (for all x∈R, MUST x R x). Symmetric and transitive relations use IF x R y. Caution! The definition of symmetric does not say that x is related to y by R; only that if it happens that x is related to y, then y must be related to x.

61. What is transitive closure of the relation?

    Transitive closure of the relation R is a relation RT obtained by adding the least number of ordered pairs to ensure transitivity. Generally speaking, a relation fails to be transitive because it fails to contain certain ordered pairs. For example, if (1, 3) and (3, 4) are in a relation R, then the pair (1, 4) must be in R if R is to be transitive. To obtain a transitive relation from one that is not transitive, it is necessary to add ordered pairs. Roughly speaking, the relation obtained by ad…

62. Let A = {0, 1, 2, 3} and consider the relation R defined on A as follows: R = {(0, 1), (1, 2), (2, 3)}. Find the transitive closure of R.

    We add {(0, 2), (1, 3), (0,3)}, resulting in: {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}

63. What is equivalence relation?

    Relation that is reflexive, symmetric, and transitive. Let A be a set and R a relation on A. R is an equivalence relation if, and only if, R is reflexive, symmetric, and transitive.

64. Equivalence relations

    https://math.stackexchange.com/a/2526763/163615 8.3, 8.4, 8.5

65. When is relation R antisymmetric?

    if R(a, b) and R(b, a), then a = b R is symmetric ⇔ for all x and y in A, if (x, y)∈R then (y, x)∈R. R is antisymmetric ⇔ for all x and y in A, if (x, y)∈R and (y, x)∈R, then x = y.

66. Write down Binomial Theorem.

67. What's a partial function?

    Partial function from X to Y is a function f: X′ → Y, for some subset X′ of X. It generalizes the concept of a function f : X → Y by not forcing f to map every element of X to an element of Y (only some subset X′ of X). Here is a definition of a usual function. Relation F from A to B is a function if, and only if:1. Every element of A must be mapped to some element of B2. And ONLY ONE element of BPartial function removes the requirement 1.

68. What does it mean to linearize a function?

    It means to change y-ordinate to, e.g., y2-ordinate - to anything that allows our graph to be the straight line. One of the properties of power functions is that taking the logarithm of the terms on the left and right sides of the equation changes the function into a straight line.

69. When is a polynomial an odd VS even function?

    even - if a polynomial contains only even powers of x Even polynomials have the property f(x) = f(−x).E.g.: f(x) = 1 + x2 − x4odd - if a polynomial contains only odd powers of x, for example , we call this polynomial odd. Odd polynomials have the property g(x) = −g(−x). E.g.: g(x) = x + x3 − x9neither even or nod - if a polynomial has both even and odd terms. The terminology of odd and even applies to functions in general and not just to polynomials. All functions that satisfy f(x) = f(−x) are…

70. Are sine and cosine trigonometric functions odd/even?

    The sin function is odd: sin(x) = −sin(−x). The cos function is even: cos(x) = cos(−x).