Tutorial on Basic Set Theory and Functions: for PRMO, RMO and IITJEE Mains maths

I) Prove that every function can be represented as a sum of an even function and an odd function.

II)Let A, B, C be subsets of a set S. Prove the following statements and illustrate them with Venn Diagrams:

2a) The famous DeMorgan’s laws in their basic forms: A^{'} \bigcup B^{'} = (A \bigcap B)^{'} and A^{'} \bigcap B^{'} = (A \bigcup B)^{'}. Assume that both sets A and B are subsets of Set S. In words, the first is: union of complements is the complement of intersection; the second is: intersection of two complements is the complement of the union of the two sets.

Sample Solution:

Let us say that we need to prove: A^{'}\bigcap B^{'}=(A \bigcup B)^{'}.

Proof: It must be shown that the two sets have the same elements; in other words, that each element of the set on LHS is an element of the set on RHS and vice-versa.

If x \in A^{'} \bigcap B^{'}, then x \in A^{'} and x \in B^{'}. This means that x \in S, and x \notin A and x \notin B. Since x \notin A and x \notin B, hence x \notin A \bigcup B. Hence, x \in (A \bigcup B)^{'}.

Conversely, if x \in (A \bigcup B)^{'}, then x \in S  and x \notin A \bigcup B. Therefore, x \notin A and x \notin B. Thus, x \in A^{'} and x \in Y^{'}, so that x \in A^{'} \bigcap B^{'}. QED.

2b) A \bigcap (B \bigcup C) = (A \bigcap B)\bigcup (A \bigcap C).

2c) A \bigcup (B \bigcap C) = (A \bigcup B) \bigcap (A \bigcup C)

III) Prove that if I and S are sets and if for each i \in I, we have X_{i} \subset S, then (\bigcap_{i \in I} X_{i})^{'} = \bigcup_{i \in I}(X_{i})^{'}.

Sample Solution: 

It must be shown that each element of the set on the LHS is an element of the set on RHS, and vice-versa.

If x \in (\bigcap_{i \in I} X_{i})^{'}, then x \in S and x \notin \bigcap_{i \in I} X_{i}. Therefore, x \notin X_{i}, for at least one j \in I. Thus, x \in (X_{i})^{'}, so that x \in \bigcup_{i \in I}(X_{i})^{'}.

Conversely, if x \in \bigcup_{i \in I}(X_{i})^{i}, then for some j \in I, we have x \in (X_{i})^{'}. Thus, x \in S and x \notin X_{i}. Since x \notin X_{i}, we have x \notin \bigcap_{i \in I}X_{i}. Therefore, x \in \bigcap_{i \in I}(X_{i})^{'}. QED.

IV) If A, B and C are sets, show that :

4i) (A-B)\bigcap C = (A \bigcap C)-B

4ii) (A \bigcup B) - (A \bigcap B)=(A-B) \bigcup (B-A)

4iii) A-(B-C)=(A-B)\bigcup (A \bigcap B \bigcap C)

4iv) (A-B) \times C = (A \times C) - (B \times C)

V) Let I be a nonempty set and for each i \in I let X_{i} be a set. Prove that

5a) for any set B, we have : B \bigcap \bigcup_{i \in I} X_{i} = \bigcup_{i \in I}(B \bigcap X_{i})

5b) if each X_{i} is a subset of a given set S, then (\bigcup_{i \in I}X_{i})^{'}=\bigcap_{i \in I}(X_{i})^{'}

VI) Prove that if f: X \rightarrow Y, g: Y \rightarrow Z, and Z \rightarrow W are functions, then : h \circ (g \circ f) = (h \circ g) \circ f

VII) Let f: X \rightarrow Y be a function, let A and B be subsets of X, and let C and D be subsets of Y. Prove that:

7i) f(A \bigcup B) = f(A) \bigcup f(B); in words, image of union of two sets is the union of two images;

7ii) f(A \bigcap B) \subset f(A) \bigcap f(B); in words, image of intersection of two sets is a subset of the intersection of the two images;

7iii) f^{-1}(C \bigcup D) = f^{-1}(C) \bigcup f^{-1}(D); in words, the inverse image of the union of two sets is the union of the images of the two sets.

7iv) f^{-1}(C \bigcap D)=f^{-1}(C) \bigcap f^{-1}(D); in words, the inverse image of intersection of two sets is intersection of the two inverse images.

7v) f^{-1}(f(A)) \supset A; in words, the inverse of the image of a set contains the set itself.

7vi) f(f^{-1}(C)) \subset C; in words, the image of an inverse image of a set is a subset of that set.

For questions 8 and 9, we can assume that the function f is f: X \rightarrow Y and a set A lies in domain X and a set C lies in co-domain Y.

8) Prove that a function f is 1-1 if and only if f^{-1}(f(A))=A for all A \subset X; in words, a function sends different inputs to different outputs iff a set in its domain is the same as the inverse of the image of that set itself.

9) Prove that a function f is onto if and only if f(f^{-1}(C))=C for all C \subset Y; in words, the image of a domain is equal to whole co-domain (which is same as range) iff a set in its domain is the same as the image of the inverse image of that set.

Cheers,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.