Meaning of function or mapping or transformation in brief words

DEFINITION:

Given two sets X and Y, a transformation (also called a function or mapping) f: X \rightarrow Y of X into Y is a triple (X,Y,G) where G itself is a collection of ordered pairs (x,y), the first element of each pair being an element of X, and the second an element of Y, with the condition that each element of X appears as the first element of exactly one pair of G.

If each element of Y appears as the second element of some pair in G, then the transformation is said to be onto.

If each element of Y which appears at all, appears as the second element of exactly one pair in G, then f is said to be one-to-one. Note that a transformation can be onto without being one-to-one and conversely.

As an aid in understanding the above definition, consider the equation y=x^{2} where x is a real number. We may take X to be the set of all real numbers and then the collection G is the set of pairs of (x,x^{2}). Taking Y to be just the set of nonnegative reals will cause f to be onto. But if Y is all real numbers, or all reals greater than -7, or any other set containing the nonnegative reals as a proper subset, the transformation is not onto. With each new choice of Y, we change the triple and hence the transformation.

Continuing with the same example, we could assume that X is the set of nonnegative reals also. Then the transformation is one-to-one, as is easily seen. Depending upon the the choice of Y, the transformation may or may not be onto, of course. Thus, we see that we have stated explicitly the conditions usually left implicit in defining a function in analysis. The reader will find that the seemingly pedantic distinctions made here are really quite necessary.

If f: X \rightarrow Y is a transformation of X into Y, and x is an element of the set X, then we let f(x) denote the second element of the pair in G whose first element is x. That is, f(x) is the “functional value” in Y of the point x. Similarly, if Z is a subset of X, then f(Z) denotes that subset of Y composed of all points f(z), where z is a point in Z. If y is a point of Y, then by f^{-1}(y) is meant the set of all points in X for which f(x)=y; and if W is a subset of Y, then f^{-1}(W) is the set theoretic union of the sets $f^{-1}(w)$, where w is in W. Note that f^{-1} can be used as a symbol to denote the triple (X,Y,G^{'}) wjere G^{'} consists of all pairs (y,x) that are reversals of pairs in G. But f^{-1} is a transformation only if f is both one-to-one and onto. If A is a subset of X and if f: X \rightarrow Y, then f may be restricted to A to yield a transformation denoted by f|A: A \rightarrow Y, and called the restriction of f to A.

Cheers,

Nalin Pithwa

Notes I: Sets and Functions: Solutions

Problem 1:

If \{ A_{i}\} and \{ B_{j}\} are two classes of sets such that \{ A_{i}\} \subseteq \{ B_{j}\}, prove that \bigcup_{i}A_{i} \subseteq \bigcup_{i}B_{i} and \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}.

Answer 1:

The first part is clear as the hypothesis says the set of sets \{ A_{i}\} is a subset of the set of sets \{ B_{j}\}. So, quite clearly \bigcup_{i}A_{i} \subseteq \bigcup_{j}A_{j}. For the second part, we can use the generalized De Morgan’s laws. (Note: if you try to derive it straight, you will prove exactly what is opposite of the required result :-)). For the second part note that X \subseteq Y \Longleftrightarrow Y^{'} \bigcap X^{'}. Using the result in the first part, that is, consider \bigcup_{i}A_{i} \subseteq \bigcup_{j}A_{j} and now take the complement of both sides so we get: \bigcup_{i}A_{i} \subseteq \bigcup_{j}B_{j} \Longleftrightarrow (\bigcup_{j}B_{j})^{'} \subseteq (\bigcup_{i}A_{i})^{'}, that is, \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}. QED.

Problem 2:

The difference between two sets A and B, denoted by A-B, is the set of all elements in A and not in B, thus A-B = A \bigcap B^{'}. Show the following:

(a)A-B = A - (A \bigcap B) = (A \bigcup B) -B.

Answer (a): A-B is the set of elements x \in A, but not in B. Hence, A-B = A-(A \bigcap B), simply by definition. Again, if we consider elements in A or B or both, and then take away elements of B, we are just left with elements of A only, but not of B. That is, A-B = A-(A \bigcap B) = (A \bigcup B) - B. QED. ps: A venn diagram may help visualize v well.

(b) TPT: (A-B) - C = A - (B \bigcup C) (PS: a Venn diagram can help visualize and perhaps, guide the writing of the proof also).

Let x \in A-B, but x \notin C. Then, x \in A, but x \notin B, or x \notin C, or not in both B and C. That is, x \in A-(B \bigcup C). By reversing the argument, we get the other subset relationship. Hence, (A-B)-C = A- (B \bigcap C). QED.

(c) TPT: A - (B-C) = (A-B) \bigcup (A \bigcap C).

Answer (c): Let x \in A-(B-C). That is, x \in A and x \notin (B-C). That is, x \in A, x \notin B, x \in C. That is, x \in A, x \notin B, or x could be both in A and C. That is, x \in (A-B) \bigcup (A \bigcap C). Simply reversing the arguments, we get the reverse subset relation. Hence, the two sets are equal. Hence, A-(B-C) = (A-B) \bigcup (A \bigcap C). QED.

(d) TPT: (A \bigcup B) - C = (A-C) \bigcup (B-C).

answer (d): let x \in A\bigcup B, but x \notin C. Then, x \in A, or x \in B, or x is an element of both A and B, but x is not an element of C. Which clearly means, x is an element of A but not C, OR x is an element of B but not C. That is, x \in (A-C) \bigcup (B-C) (upon reversing the arguments, we get the other subset relations. Hence, the two sets are equal). QED.

problem (e): TPT: A-(B \bigcup C) = (A-B) \bigcap (A-C) (once again, note that for set theoretic relations with up to three sets, venn diagrams are helpful to visualize and guide the proofs..)

answer (c): let x \in A, but not in B \bigcup C. That is, x is an element of A, but not of B, not of C, or not both of B and C. That is, x is an element of A not of B, and x is an element of A not of C. That is, x \in (A-B) \bigcap (A-C). Reversing the arguments, we get the other subset relationship. Hence, the two sets are equal. Hence, A - (B \bigcup C) = (A-B) \bigcap (B-C). QED.

Problem 3:

The symmetric difference of two sets A and B, denoted by A \triangle B, is defined by A \triangle B = (A-B) \bigcup (B-A); it is the union of the difference of two sets in opposite orders. Prove the following:

3(a) Symmetric difference is associative: A \triangle (B \triangle C) = (A \triangle B) \triangle C.

Answer 3a: please refer a previous blog.

3(b): TPT: A \triangle \phi = A; and A \triangle A = \phi. (this is some sort of ‘existence of additive inverse of ‘in a symmetric relation’).

Answer 3b: both results are obvious from definition.

3(c): TPT: Symmetric difference is commutative operation: A \triangle B = B\triangle A.

answer 3c: By definition, LHS is (A-B)\bigcup (B-A) = (B-A) \bigcup (A-B), which is RHS. Hence, done.

3(d): TPT: Some sort of distributive law: A \bigcap (B \triangle C) = (A \bigcap B) \triangle (A \bigcap C).

answer 3d: Let x \in A, and also simultaneously x \in (B \triangle C). That is, x \in A, and x \notin (B \bigcap C). That is, x \in A, x \notin (A \bigcap B)\bigcap (B \bigcap C). That is, x \in RHS. Reversing the arguments, we get the other subset relation. Hence, the two sets are equal. Hence, we can say “intersection distributes over symmetric difference.” QED.

Problem 4:

A ring of sets is a non-empty class A of sets such that if A and B are in A then A \triangle B is in A and A \bigcap B is also in A. Show that A must contain the empty set, A \bigcup B and A-B. Also, show that if a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets. Also, prove that a Boolean algebra of sets is a ring of sets.

Answer 4(i): TPT: A must also contain the empty set, the set A \bigcup B and the set A-B. As A \triangle B is in A, so also A \triangle A = \phi \in A; now, it is already given that the ring of sets is non-empty, so it contains a non empty universal set also, call it U. We know from problem 2 in this blog that A - B = A \bigcap B^{'}. As U exists, so does B^{'} by definition and so A-B is in A. Also, as A-B exists, A-B^{'} exists in A, but A-B^{'}=A\bigcap B also exists in A. QED.

Answer 4(ii): TPT: If a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets.

Let A be any non-empty class of sets. Clearly, it therefore has a non empty universal set. As \phi \in U, so also \phi is contained in A. Hence, the complement of a set A is also in A. Now, A \bigcup B \in A, so U - (A \bigcup B) is in A, that is, by De Morgan law, B^{'} \bigcap A^{'} is in A. That is, again, A \bigcap B is in A. Now, since A-B is in A, hence, B-A is in A, and since A \bigcup B is in A, then (A-B) \bigcup (B-A) is in A also. Hence, A is a ring of sets.

4(iii) TPT: Show that a boolean algebra of sets is a ring of sets.

Answer 4(iii); Firstly, as a boolean algebra of sets is non-empty, and it also contains the empty set and the Universal set. As A is in A implies that A^{'} is in A, so A \bigcup B^{'} is also in A (by definition of Boolean algebra), but this is precisely that A-B is in A. Now, as A \triangle B = (A-B) \bigcup (B-A) clearly is also in A. Hence, a Boolean algebra of sets is a ring of sets.

Problem 5:

Show that the class of all finite subsets (including the empty set) of an infinite set is a ring of sets but is not a Boolean algebra.

Answer 5:

In problem 4 above, we showed that if a non empty class of sets contains the union and difference of any pair of the sets, then it is a ring of sets. The given class is a subclass of all an infinite set such that it contains finite subsets only; that is, again, we know that finite unions of finite subsets and finite intersections of finite subsets also lie in that subclass, but the complements might be infinite sets so that it need not always be a Boolean algebra of sets.

Problem 6:

Show that the class of all finite unions of closed-open intervals on the real line is a ring of sets but is not a Boolean algebra of sets.

Answer 6:

Same reasoning as above tells us that it is indeed a ring of sets; but consider for example the closed-open interval [a,b), the complement of this is not in that class as it is an infinite interval so that it is not a Boolean algebra of sets.

Problem 7:

Assuming that the Universal set U is non empty, show that Boolean algebras of sets can be described as rings of sets which contain U.

Answer 7:

As U \neq \phi, by definition of Boolean algebras, U^{'} is in this class of sets, so that the empty set is also a part of this class of sets. Again, by definition of Boolean algebras, the union of two sets of this class is also in this set so also the intersection of any two sets of this class is also in this class. So, for any two sets A and B, A-B is also in this set (as complement of B exists), and so also, A \triangle B = (A-B) \bigcup (B-A) is also in this set. In other words, this is also a ring of sets.

Regards,

Nalin Pithwa

Set theory: more basic problems to solve and clear and apply

I am producing the list of questions first so that the motivated reader can first read and try them …and can compare with my answers by scrolling down only much later; here we go:

  1. If \{ A_{i}\} and \{ B_{j}\} are two classes of sets such that \{ A_{i}\} \subseteq \{ B_{j}\}, then prove that \bigcup_{i}A_{i} \subseteq \{ B_{j}\} and \bigcap_{j} B_{j} \subseteq \bigcap_{i}A_{i}.
  2. The difference between two sets A and B, denoted by A-B, is the set of elements in A and not in B; thus, A - B = A \bigcap B^{'}. Prove the following simple properties: (a) A-B = A-(A \bigcap B) = (A \bigcup B)-B; (b) (A-B)-C = A-(B \bigcup C); (c) A - (B-C) = (A-B) \bigcup (A \bigcap C); (d) (A \bigcup B) - C = (A-C) \bigcup (B-C); (e) A - (B \bigcup C) = (A-B) \bigcap (A-C)
  3. The symmetric difference of two sets A and B, denoted by A \triangle B, is defined by A \triangle B = (A-B) \bigcup (B-A); it is thus the union of their differences in opposite orders. Prove the following : (a) Symmetric difference is associative : A \triangle (B \triangle C) = (A \triangle B) \triangle C (b) A \triangle \phi=A (c) A \triangle A = \phi (c) Symmetric difference is commutative: A \triangle B = B \triangle A (d) Some sort of distributive rule also holds: A \bigcap (B \triangle C) = (A \bigcap B) \triangle (A \bigcap C)
  4. A ring of sets is a non-empty class A of sets such that if A and B are in A, then A \triangle B and A \bigcap B are also in A. Show that A must also contain the empty set, A \bigcup B, and A-B. Show that if a non-empty class of sets contains the union and difference of sets any pair of its sets, then it is a ring of sets. Prove that a Boolean algebra of sets is a ring of sets.
  5. Show that the class of all finite subsets (including the empty set) of an infinite set is a ring of sets but is not a Boolean algebra of sets.
  6. Show that the class of all finite unions of closed-open intervals on the real line is a ring of sets but is not a Boolean algebra of sets.
  7. Assuming that the universal set U is non-empty, show that Boolean algebras of sets can be described as a ring of sets which contain U.

I will put up my solutions as soon as I can.

Regards,

Nalin Pithwa.

Symmetric difference is associative

We want to show that : A \triangle (B \triangle C) = (A \triangle B) \triangle C

Part I: TPT: LHS  \subset RHS

Proof of Part I: let x \in LHS

Then, x \in A \triangle (B \triangle C). By definition of symmetric difference,

x \in \{ A - (B \triangle C)\} \bigcup \{(B \triangle C) -A \}

Hence, x \in A, x \notin (B \triangle C), OR x \in B \triangle C, x \in A

That is, x \notin A \bigcap (B \triangle C).

Hence, x \notin A, and x \notin B \triangle C

Hence, x \notin A and x \in B \bigcap C.

Hence, x \in (B \bigcap C)-A.

Hence, x \in B, x \in C, but x \notin A.

Therefore, x \in B, but x \notin A \bigcap C. —- Call this I.

Consider y \in (A \triangle B) \triangle C.

Therefore, y \notin (A \triangle B) \bigcap C.

Therefore, y \notin C, and y \notin A \triangle B

Therefore, y \notin C, and y \in A \bigcap B.

Therefore, y \in (A \bigcap B)-C.

Hence, y \in A, y \in B, but y \notin C.

That is, y \in B, y \notin A \bigcap C. Call this II.

From I and II, LHS \subset RHS.

Part II: TPT: RHS \subset LHS.

Quite simply, reversing the above steps we prove part II.

QED.

Cheers,

Nalin Pithwa