Some more foundation mathematics — notions from set theory: Tutorial problems

It’s a strange way of starting a lecture that I adopt..sometimes…I first give my students quizzes or exams…Here is some foundation mathematics for my deserving students and also, if any of my reader is interested:

Basic Notions from Set Theory:

Reference: Introduction to Analysis, Maxwell Rosenlicht, Dover Publications,

Dover Pub, math link: http://store.doverpublications.com/by-subject-mathematics.html

Exercises:

Question 1:

Let \Re be the set of real numbers and let the symbols <, \leq have their conventional meanings:

a) Show that \{ x \in \Re: 0 \leq x \leq 3\} \bigcap \{x \in \Re: -1 <x <1 \}=\{ x \in \Re: 0 \leq x <1\}

b) List the elements of

(\{2,3,4 \} \bigcup \{ x \in \Re: x^{2}-4x+3 = 0\}) \bigcap \{x \in \Re: -1 \leq x < 3 \}

c) Show that

(\{ x \in \Re: -2 \leq x \leq 0\} \bigcup \{ x \in \Re: 2 < x <4\}) \bigcap \{ x \in \Re: 0 \leq x \leq 3\} = \{ x \in \Re: 2 < x \leq 3\} \bigcup \{ 0\}

Question 2:

If A is a subset of the set S, prove that :

2a) (A^{'})^{'}=A

2b) A \bigcup A = A \bigcap A = A \bigcup \phi = A

2c) A \bigcap \phi = \phi

2d) A \times \phi = \phi

Question 3:

Let A, B, C be elements of a set S. Prove the following statements and illustrate them with diagrams:

(a) A^{'} \bigcup B^{'} = (A\bigcap B)^{'}… a De Morgan law. In words, it can be said that the union of two complements is the complement of the intersection of the two.

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

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

Question 4:

If A, B, C are sets, then prove that :

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

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

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

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

Question 5:

Let f be a non-empty set and for each i \in I, let X be a set. Prove that

(i) for any set B, we have :

B \bigcap \bigcup_{i \in I}X_{i} = \bigcup_{i \in I}(B \bigcap X_{i})

(ii) 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})^{'}

Question 6:

Prove that if f: X \rightarrow Y, g: Y \rightarrow Z, and h: Z \rightarrow W are functions, then

h \circ (g \circ f) = (h \circ g) \circ f

Question 7:

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:

(i) f(A \bigcup B) = f(A) \bigcup f(B)

(ii) f(A \bigcap B) \subset f(A) \bigcap f(B)

(iii) f^{-1}(C \bigcup D) = f^{-1}(C) \bigcup f^{-1}(D)

(iv) f^{-1}(C \bigcap D) = f^{-1}(C) \bigcap f^{-1}(D)

(v) f^{-1}(f(A)) \supset A

(vi) f(f^{-1}(C)) \subset C

Question 8:

(a) Prove that a function f is one-to-one if and only if f^{-1}(f(A)) = A for all A \subset X.

(b) Prove that a function f is onto if and only if f(f^{-1}(C)) = C for all C \subset Y.

Cheers,

Nalin Pithwa

PS: These tutorial problems can be used for IIT JEE Maths, Pre RMO, RMO Maths etc. also.

Some foundation mathematics

Well-Ordering Principle:

Every non-empty set S of non-negative integers contains a least element; that is, there is some integer a in S such that a \leq b for all b’s belonging to S.

Because this principle plays a role in many proofs related to foundations of mathematics, let us use it to show that the set of positive integers has what is known as the Archimedean property.

Archimedean property:

If a and b are any positive integers, then there exists a positive integer n such that na \geq b.

Proof:

By contradiction:

Assume that the statement of the theorem is not true so that for some a and b, we have na <b for every positive integer n. Then, the set S = \{ b-na : n \in Z^{+}\} consists entirely of positive integers. By the Well-Ordering Principle, S will possess a least element, say, b-ma. Notice that b- (m+1)a also lies in S; because S contains all integers of this form. Further, we also have b-(m+1)a=(b-ma)-a<b-ma contrary to the choice of b-ma as the smallest integer in S. This contradiction arose out of original assumption that the Archimedean property did not hold; hence, the proof. QED.

First Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

a) the integer 1 belongs to S.

b) Whenever the integer k is in S, the next integer k+1 is also in S.

Then, S is the set of all positive integers.

Second Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

a) the integer 1 belongs to S.

b) If k is a positive integer such that 1,2,\ldots k belong to S, then (k+1) must also be in S.

Then, S is the set of all positive integers.

So, in lighter vein, we assume a set of positive integers is given just as Kronecker had observed: “God created the natural numbers, all the rest is man-made.”

More later,

Nalin Pithwa.

Precursor to Algebra: Herstein shows a way!

Reference: Abstract Algebra, 3rd edition, I. N. Herstein, Prentice Hall International Edition.

Problems:

  1. Let S be a set having an operation * which assigns an element a*b of S for any a,b \in S. Let us assume that the following two rules hold:

i) If a, b are any objects in S, then a*b = a

ii) If a, b are any objects in S, then a*b=b*a

Show that S can have at most one object.

II. Let S be the set of all integers 0, \pm 1, \pm 2, \pm 3, \ldots, \pm n, \ldots. For a, b in S, define * by a*b=a-b. Verify the following:

(i) a*b \neq b*a unless a=b.

(ii) (a*b)*c \neq a*(b*c) in general. Under what conditions on a, b, c is (a*b)*c=a*(b*c)?

(iii) the integer 0 has the property that a*0=a for every a in S.

(iv) For a in S, a*a=0.

III) Let S consist oif f the two objects \square and \triangle. We define the operation * on S by subjecting \square and \triangle to the following conditions:

i) \square * \triangle = \triangle = \triangle * \squarei

ii) \square * \square =\square

iii) \triangle * \triangle=\square

of verify by explicit calculations that if a, b, c are any elements of S (that is, a, b and c can be any of \square or \triangle then

i) a*b is in S

ii) (a*b)*c=a*(b*c)

iii) a*b=b*a

iv) There is a particular a in S such that $la=latex a*b=b*a=b$ for all b in S.

,v) Given b in S, then b*b=a where a is the parituclar element in part “iv” above.

Cheers,

Nalin Pithwa