The words set and space are often used in loose context to one another. A set is merely an amorphous collection of elements, without coherence or form. When some kind of algebraic or geometric structure is imposed on a set, so that its elements are organized into a systematic whole, then it becomes a space.

# Category: undergrad algebra

# Symmetric Difference is associative

# Exercises based on system of sets

**Reference: Introductory Real Analysis, Kolomogorov and Fomin, Dover Publications, Translated and edited by Richard A. Silverman:**

Problem 1:

Let X be an uncountable set, and be the ring consisting of all finite subsets of X and their complements. Is a -ring also?

Problem 2:

Are open intervals Borel sets ?

Problem 3:

Let be a function defined on a set M and taking values in a set N. Let be a system of subsets of M, and let denote the system of all images of sets . Moreover, let be a system of subsets of N, and let denote the system of all preimages of of sets . Prove that

(i) If is a ring, so is

(ii) If is an algebra, so is

(iii) If is a borel algebra, then so is

(iv)

(v) .

Which of these assertions remain true if os replaced by and by f?

Regards,

Nalin Pithwa

# Equivalence relations and partitions: some core basic theorems

Suppose R is an equivalence relation on a set S. For each a in S, let [a] denote the set of elements of S to which a is related under R, that is,

We call [a] the equivalence class of a in S under R. The collection of all such equivalence classes is denoted by S/R, that is, . It is called the quotient set of S by R.

The fundamental property of an equivalence relation and its quotient set is contained in the following theorem:

**Theorem I:**

Let R be an equivalence relation on a set S. Then, the quotient set S/R is a partition of S. Specifically,

(i) For each , we have .

(ii) if and only if .

(iii) If , then [a] and [b] are disjoint.

*Proof of (i):*

Since R is reflexive, for every and therefore .

*Proof of (ii):*

Assume: .

we want to show that . That is, we got to prove, (i) and (ii) .

Let ; then, . But, by hypothesis and so, by transitivity, . Accordingly, . Thus, .

To prove that , we observe that implies, by symmetry, that . Then, by a similar argument, we obtain . Consequently, .

Now, assume .

Then by part (i) of this proof that for each , we have . So, also, here ; hence, .

*Proof of (iii):*

Here, we prove the equivalent contrapositive of the statement (iii), that is:

If then .

if then there exists an element with . Hence, and . By symmetry, , and, by transitivity, . Consequently, by proof (ii), .

The **converse of the above theorem is also true. **That is,

**Theorem II:**

Suppose is a partition of set S. Then, there is an equivalence relation on S such that the set of equivalence classes is the same as the partition .

Specifically, for , the equivalence in Theorem I is defined by if a and b belong to the same cell in P.

Thus, we see that there is a one-one correspondence between the equivalence relations on a set S and the partitions of S.

*Proof of Theorem II:*

Let , define if a and b belong to the same cell in P. We need to show that is reflexive, symmetric and transitive.

(i) Let . Since P is a partition there exists some in P such that . Hence, . Thus, is reflexive.

(ii) Symmetry follows from the fact that if , then .

(iii) Suppose and . Then, and . Therefore, . Since P is a partition, . Thus, and so . Thus, is transitive.

Accordingly, is an equivalence relation on S.

Furthermore,

.

Thus, the equivalence classes under are the same as the cells in the partition P.

More later,

Nalin Pithwa.

# 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 be the set of real numbers and let the symbols have their conventional meanings:

a) Show that

b) List the elements of

c) Show that

**Question 2:**

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

2a)

2b)

2c)

2d)

**Question 3:**

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

(a) … 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)

(c) .

**Question 4:**

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

i)

ii)

iii)

iv)

**Question 5:**

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

(i) for any set B, we have :

(ii) if each is a subset of a given set S, then

**Question 6:**

Prove that if , , and are functions, then

**Question 7:**

Let be a function, let A and B be subsets of X, and let C and D be subsets of Y. Prove that:

(i)

(ii)

(iii)

(iv)

(v)

(vi)

**Question 8:**

(a) Prove that a function f is one-to-one if and only if for all .

(b) Prove that a function f is onto if and only if for all .

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 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 .

**Proof:**

*By contradiction:*

Assume that the statement of the theorem is not true so that for some a and b, we have for every positive integer n. Then, the set consists entirely of positive integers. By the Well-Ordering Principle, S will possess a least element, say, . Notice that also lies in S; because S contains all integers of this form. Further, we also have contrary to the choice of 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 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 belong to S, then 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.