SET THEORY

  • Basic concepts
  • Notations
  • Subset
  • Algebra of sets
  • The power set
  • Orderedpairs and Cartesian product
  • Relations on sets
  • Types of relations and their properties
  • Relational matrix and the graph of a relation
  • Partitions
  • Equivalence relations
  • Partial ordering
  • Poset
  • Hasse diagram
  • Lattices and their properties
  • Sub lattices
  • Boolean algebra
  • Homomorphism.

Sets and Motivation for Boolean algebra

1 Sets

2 Algebra of Sets

3 Cartesian Products

4 Motivation of Boolean Algebra


Sets
We devote this section to brief some set theoretic notions, which will play an essential role in the lattice theory.
Set is a collection of well-defined objects. An object belonging to a set is called member or element of the set.
In most cases, set will be defined by means of a characteristic property of the objects belonging to the set. That is, for a givenproperty P(x), let {x : P(x)} denote the set of all objects x such that P(x) is true.

A set with no member is said to be an empty
set.

We use upper case letters such as A, B, C, etc., to denote sets and lower case letters such as a, b, c, x, y, z, etc, to denote
members of the sets. We denote the fact that x is an element of the set S by x  S, while x is not an element of S by x  S.
Two sets A and B are equal if and only if A and B have the same members. Equality of A and B is denoted by A=B. Wesay that A is a subset of B if and only if every member of A is also a member of B. We write A B as an abbreviation forA is a subset of B.
It is interesting to observe that, for all sets A, B and C, we have
(i) A  A [Reflexive]
(ii) A  B and B A if and only if A=B
(iii) If A  B, B  C then A C [transitive]
P(A) denote the set of all subset of A, we shall call P(A), the power set of A.
That is, P(A) = {B : B  A}

Example 1:
Let A = {1,2,3}
Then P(A) = { , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.
Let A be a finite set of n elements, say A= {a1, a2, …, an}, then P(A) consists of  , the n sets {ai} containing single element,nC2 sets {ai, aj / i j}containing two elements, etc. In general P(A) contains nCi subsets containing i distinct elements of A, for
1 i  n. Therefore the number of elements in P(A) is1+ nC1 + nC2 + ……….+ nCn = (1+1)n = 2n.
Algebra of Sets
In this section we define, union of two sets, intersection of two sets, complement of a set and we brief some of their basicproperties and their operations.
Given sets A and B, their union A Bconsists of all elements in A or B or both.
That is,A B = {x / x  A or x  B}.
It is interesting to observe that the union operation on sets has properties:

  1. A A = A (Idempotent)
  2. A B = B A (Commutative)
  3. A  = A
  4. (A B) C = A (B  C) (Associative)
  5. A B = B if and only if A B
  6. A  (A B) and B  (AB)

Given sets A and B, their intersection A B consists of all objects which are in both A and B.
Thus, A  B = {x / x  A and x  B} .Two sets A and B are said to be disjoint if and only if A  B =  .
The intersection operation on sets has the following evident properties:

  1. A  A = A (Idempotent)
  2. A  B = B  A (Commutative)
  3. A  = 
  4. (A  B)  C = A  (B  C) (Associative)
  5. A  B = A if and only if A  B
  6. (A  B)  A and (A  B)  B

An important property connecting  and  is the distributive law.
(i) A  (B  C) = (A  B)  (A  B)
(ii) A  (B  C) = (A  B) (A  C)
Proof:
A  (B  C) = {x / x  A and x  B  C}
= {x / x  A and (x  B or x C)}
= {x / (x  A and x  B) or (x  A and x  C)}
= {x / x  A  B or x A  C}
= (A  B)  (A  C)
Similarly, A  (B  C) = (A  B)  (A  C) can be proved.
It is very interesting to observe that A  (A  B) = A, for A  (A  B) and A  A,
therefore, A  (A  B) = A.
Similarly, A  (A  B) = A, for (A  B)  A and A  A, hence, A  (A  B) = A.
Thus, for sets A and B, we have,
A(AB) = A; A(AB) = A [Absorption law].
By the difference, B\A, of the sets B and A, we mean the set of all those objects in B which are not in A.
Thus, B\A = {x : x B and x  A}.
The symmetric difference, A B, of sets A and B is the set (A\B)  (B\A).
Let X be given set. If we deal with subset of X then we call X is a universal set. If A  X, then the complementof Ais defined to be X\A.
Thus,= {x / x  X and x  A}
It is clear that whenever we use complements, it is assumed that we are dealing only with subset of some fixed universal set X.

The following properties can be easily verified:

Cartesian Products
In this section we define Cartesian product of sets. Cartesian product set A B of two arbitrary sets A and B is the set ofall pairs (a, b) such that a A and b B. That is, A  B = {(a,b) / a  A and b B}. Note that the sets A and B need not be
distinct in the Cartesian product.
In the product A  B, the element (a1, b1) and (a2, b2) are regarded as equal if and only if a1 = a2 and b1 = b2. Thus, if Aconsists of m elements a1, a2, … , am and B consists of n elements b1, b2, … ,bn , then A  B consists of mn elements (ai, bj),
1  i  m, 1  j  n.

Motivation of Boolean Algebra
In this section we shall discuss the motivation of Boolean algebra. From the Section Algebra of Sets, it is interesting toobserve that, if A is any set, then the binary operations,  and  on the set P(A) satisfy the following properties

  1. Commutative law,
  2. Associative law,
  3. Absorption law,
  4. Idempotent property and
  5. Distributive law.

and the uninary " - " operation on P(A) satisfies the De Morgan's law. So it is tempting to ask the question:
"Are there other sets like P(A) and binary operations like  and  satisfying commutative law, associative law,
absorption law, idempotent property and distributive law and uninary operation "-" satisfying De Morgan's law?".
Indeed there are many such sets and such binary and uninary operations on such sets satisfying the above mentioned laws and property. In fact, one of the main motivations of Boolean Algebra is a search of such sets and understanding their
algebraic structure.

Try Yourself:

  1. Give proofs for all the properties about the set inclusion "  ", union of sets intersection of sets and complement of a setmentioned in the Sections 1.1and1.2.

Partially Ordered Set and Hasse Diagram

1 Relation and Poset

2 Hasse Diagram

3 Totally Ordered Set and Dual Poset

4 Extremal Elements of Partially Ordered Sets


Relation and Poset
In this section we define relation and special type of relation called reflexive, symmetric, anti-symmetric and transitive relationand we discuss examples on these relations. Further, we define partial ordering relation and posets and discuss some examples
of posets.
Let A and B the non-empty sets. A relation R from A to B is a subset of A  B. Relation from A to A is called relation on A.
If (a, b) R then we write aRb and say that "a is in relation R to b". Also, if a is not in relation R to b, we write ab.
Example:
Let A = B = Z+, the set of all positive integers. The relation R is defined on Z+ in the following way aRb if and only if a divides b.
So, 6 R 18, but 38
A relation R on a set A is reflexive if (a, a) for every a A, that is, if aRa for all a A.
Example:
Let A= {1,2,3} and let R = {(1,1), (2,2), (3,3), (1,2) (1,3)}
Then R is reflexive, while R' = {(1,1), (2,2), (2,1), (1,2)} is not a reflexive, for (3,3) R', i.e., 33.
A relation R, on a set A, is anti-symmetric if whenever aRb and bRa, then a = b.That is, R is anti-symmetric whenevera  b we must have either ab or ba.

Example 1:
Let X be a set and let A  X and B  X. Then from the Section 1.1, it is clear that A = B. Therefore, " " is anti-symmetric
on the set of subsets of X.
Example 2:
Let A=Z+, the set of all positive integer. Define R on A by aRb if and only if a b that is "a divides b".
Then, if a R b and b R a, i.e., ab and ba, then there exist integers c, d  Z+ such that b = ca and a = db.
Therefore, b = cbd.
So, 1 = cd. Therefore c = d = 1.
Hence a = b.
Therefore, R is anti-symmetric on Z+
Example 3:
Let A = Z, the set of integers and let R = {(a, b)  A  A / a < b}, i.e., R is usual "less than".
If a  b, then either a < b or b < a, that is, equivalently, if a  b then either b a or ab.
Hence,if a  b then either ab or ba is true.
Therefore, "<", usual "less than", is anti-symmetric.
[Note that in the anti-symmetric relation symmetryness will happen only with equal elements and symmetryness will neverhappen between the unequal elements].
We say that a relation R on a set A is transitive if aRb and bRc then aRc.
Example:
Let A={1,2,3,4} and let R={(1,2), (2,1), (1,1), (2,2), (2,3), (2,3)}. Then R is transitive.
Let R={(1,2) (1,3), (4,2)}. Then R is also transitive, because we cannot find elements a, b, and c in A such that aRb and bRc,
but a c. So, we conclude that R is transitive.
A relation R on a set A is called a partial order relation or partial ordering if R is reflexive, anti-symmetric andtransitive.
A non-empty set A together with a partial order relation R, (A, R), is called partially ordered set or poset.
Partial order relations are "hierarchical relations", usually we write  instead of R for partial ordering.Thus, (A,  ) denote a partially ordered set or poset.
Example 1:
Let A be a non empty set. Consider the power set P(A), the set of subsets of A, together with the relation set inclusion, " ".Then (P(A),  ) is a poset.
For, S  S, for all S P(A).
Therefore,  is reflexive.
If S  T and T  S, for S, T P(A),
then S = T (since S = T if and only if S  T and T  S).
Therefore,  is anti-symmetric.
Also, if S  T and T  U, then by definition of  , it is clear that S U.
Therefore,  is transitive.
Hence, (P(A),  ) is a partially ordered set.
Example 2:
Let A = Z+ and let a  b if and only if ab then (A, ) is a poset.
For, since a = 1.a , a  Z+, i.e., aa,  a  Z+.
Therefore " " is reflexive.
If ab and bc, then there exists d1 and d2 in Z+, such that b = d1a and c = d2b.
So, we have c = d2d1a.
As d1, d2 Z+, d2d1 Z+
Then ac.
Hence, "  " is transitive.
Already we have seen that " " is anti-symmetric.
Thus, "  " is partial ordering.
Hence, (A,  ) is a poset.
Example 3:
(R,  ) is a poset, where R is the set of all real number and "  " is "usual less than or equal to " (Prove!).
Example 4:
(P(S),  ) is not a poset, for, the relation  is anti-symmetric and transitive but not reflexive so it is not a poset.
Example 5:
Let S be the set of all subgroups of a group G. Then (S,  ) is a poset (Prove!)
Example 6:
Let S be the set of all normal subgroups of G. then (S,  ) is a poset (Prove!).
Example 7:
Let S = {( i1, i2,…,in) / ir= 0 or 1, 1  r  n}
Define (i1,i2,…,in) R ( j1,j2,…,jn ) if and only if i1  j1, i2  j2,…,in jn.
Then (S,R) is a poset (Prove!).
Hasse Diagram
In this section we discuss the diagrammatic representation of a poset.
In a poset (A,  ), if a  b and a b then we write a < b. Further, in a poset (A,  ), we say that a is a cover of b if a < band there exists no u such that a < u < b.
A finite poset can be represented graphically, such a diagram of a poset is called Hasse diagram.

We represent theelements of A by points in the plane. If b is a cover of a then we place b above a and connect the two points a and b by a
straight line (actually directing from a to b). Thus, if a < b if and only if there is a ascending broken line (a path) connecting a to b.
If no line connecting a and b and a  b, then a and b are not related or not comparable, that is, we have neither a  b nor b  a.
Example:
1. Hasse diagram of the poset ({1,2,3,4,5},  ), where  is "usual less than or equal to" is given below.

2. Consider the poset (P(A3),  ), where A3 = {a, b, c}. The Hasse diagram of (P(A3),  ) is given below :

Note that actually all the lines should have upward directions. Since all the lines are having only one direction, it is a conventionto draw without direction in the lines. Thus, in the Hasse diagram every path has only upward direction, i.e., there cannot be any
path connecting top to bottom in the downward direction.
In the above example we see that {a} and {a, b, c} are related, since there is an ascending path from {a} to {a, b, c}, while {a}and {b} are not related or not comparable, since there is no ascending path connecting {a} and {b}.
3. Let Dn denote the set of all positive divisiors of a positive integer n.
Hasse diagram of the poset (D12, ) is given below.

Conversely, if we have a Hasse diagram then we can describe the poset, that is, we can describe the partial order relation.
For example, consider the Hasse diagram given below :

Then the set is {a, b, c, d, e, f, g} and the relation is {(a, a) (a, c) (a, d), (a,e), (a, f), (a, g), (b, b), (b, c), (b, d), (g, e), (g, f),(b, g), (c, c), (c, d), (c, e), (c, f), (c, g), (d, d), (d, e), (d, f), (d, g), (e, e), (e, g), (f, f), (f, g), (g, g)}.
One can check that  is indeed partial ordering.
So, we conclude that for the finite poset it is enough to just give the Hasse diagram to describe the poset.
Remark:
From the above examples of the posets, we observe that in a poset it is not necessary that all the pair of elements are related orcomparable, that is, in a poset not necessarily all the elements are ordered. That is the reason we call such sets (posets) aspartially ordered set.

Totally Ordered Set and Dual Poset
In this section we define totally ordered set and dual poset and discuss about them.
A partial order relation  on a set A is called a total order (or linear order) if, for each a, b A either a  b or b  a.
If is a totally order on a set A, then (A,  ) is called totally ordered set or linearly ordered set or chain.

Example 1:
The poset (N,  ), where N is the set of all natural numbers and  is the usual "less than or equal to", is a totally ordered set, sincefor any two a, b  N, we have either a  b or b  a.
In fact, ( Z,  ), ( Q,  ) ( R,  ), are all totally ordered set, where Z, the set of all integers, Q, the set of all rational numbers andR, the set of all real number and  is usual less than or equal to. Also, any finite subset of either Z or Q or R with usual "less than
or equal to" are also totally ordered sets.
Example 2:
( D30, ) is not a totally ordered set (Prove !)

Try yourself:
Let L be the set of complex numbers z = x + iy, where x and y are rationals.
Define a partial order "  " on L by: x1 + iy1 x2 + iy2 if and only if y1 y2.
Is ( L,  ) a totally ordered set. If not, what is the additional condition needed in order to make ( L,  ) into a chain?

Remark 1:
From the definition of totally ordered set, it is clear that any two elements in a totally ordered set are related or comparable. Thatis, in a totally ordered set all the elements are ordered or related. That is the reason we call such sets as totally ordered set.
If R is a relation from A to B then R-1 defined by (a, b) R-1 if and only if (b, a) R, is a relation from B to A, called theconverse relation of R.
Remark 2:
If (A, R) is a partially ordered set then (A, R-1) is a partial ordered set.
Proof:
Let (A, R) be a poset. Then R is a partial ordering on A. Therefore, R is reflexive, anti-symmetric and transitive.
Now we shall prove that R-1 is reflexive, anti-symmetric and transitive.
Since R is reflexive, we have, (a, a) R ,for all a  A.
Therefore, (a, a) R-1,for all a  A also.
Thus, R-1is reflexive.
If aR-1b and bR-1a, then by definition of R-1 we have bRa and aRb.
Since R is anti-symmetric, we have a = b. Therefore, R-1 is anti-symmetric.
Let aR-1b and bR-1c. Then by definition of R-1, we have bRa and cRb.
Since R is transitive, we have cRa. Therefore, aR-1c. Thus, R-1 is transitive.
Hence (A, R-1) is a partially ordered set.
Note:
Since we use  for denoting partial ordering we denote  for its converse. Thus, if (A,  ) is a partial ordered set then (A,  ) isalso partial ordered set. The poset (A,  ) is called dual poset to the poset (A,  ).
Remark 3: (Duality Principle)
Every statement or formula or expression on an ordered set (A,  ) remains correct if everywhere in the statement the relation is replaced by its converse relation  .

Extremal Elements of Partially Ordered Sets
In this section we discuss about the extremal elements of a poset. Let (A,  ) be a poset. An element a A is called a maximalelement of A if there is no element c in A such that a < c. An element b A is called a minimal element of A if there is noelement c in A such that c < b. An element a A is called a greatest element of A if x  a, for all x A. Similarly, anelement a A is called a least element of A if a x, for all x A.
Example:
Consider the following poset represented by the following Hasse diagram
In this poset, a, f and i are minimal elements c, h, k are maximal elements, there is a no greatest element and there is no leastelement.

Consider the following posets represented by Hasse diagrams.

In the poset (i),a is the least and minimal element and d is the greatest and maximal element.
In the poset (ii), a is the least and minimal element and d and e are maximal elements but there is no greatest element.
Remark:
In a poset, least element or greatest element need not always exist. It is clear that least element is a minimal element and greatestelement is a maximal element but not conversely.

Try yourself:

  1. Let (A,  ) be a finite non empty poset. Then prove that A has at least one maximal element and at least one minimal
    element.
  2. Let (A, ) be a poset. Then prove that if least element or greatest element exist then they are unique.

Let (A,  ) be a poset and B A.

  1. a  A is called an upper bound of B if and only if b a, for all b  B.
  2. a  A is called a lower bound of B if and only if a b, for all b  B.
  3. An lower bound g of B is called a greatest lower bound or infimum if and only if h  g for every lower bound h ofB in A and it is denoted by inf B or GLB of B.
  4. An upper bound v of B is called least upper bound or superimum if and only if v  u for all upper bound u of B in Aand it is denoted by sup B or LUB of B.

Example:
Consider the poset (D30 ,), i..e ({30, 15, 10, 6, 5, 3, 2, 1},  ).
LetB = {2, 3, 6}. Then inf B = 1, upper bounds of B are 6 and 30 but supB = 6.

Try yourself:
1.Let (A,  ) be a poset and let B  A. Prove that if inf B or sup B exist then they are

unique.

2. On the set A = {a, b, c}, find all partial orders  in which a  b?

3. If (A,  ) is a poset and A' is a subset of A. check whether (A', ' ) is also a poset, where ' is the restriction of  to A.

4. Construct the Hasse diagram of (D30 ,) and (P(A3), ), where A3 = {1,2,3} Do they have structural similarity?

5. Find ( i ) all the lower bound of B.
( ii ) all the upper bound of B.
( iii ) the least upper bound of B.
( iv ) the greatest lower bound of B, where B = {c, d, e} in the poset represented by the followingposet.

6. Whether every finite poset has maximal element? If yes, justify your answer

Lattices

1 Lattice Ordered Sets

2 Algebraic Lattice

3Sub lattices, Direct Product and Homomorphism

3.1Sub lattices

3.2 Direct Product of Lattices

3.3 Homomorphism

3.4 Special Lattices

3.4.1 Isotone, Distributive and Modular Inequalities

3.4.2 Modular Lattices

3.4.3 Distributive Lattices

3.4.4 Complemented Lattices

Lattices
In this section we introduce lattices as special type of partial ordered set and we discuss basic properties of lattices and someimportant type of special lattices.
Lattice Ordered sets
In this section we define lattice ordered sets and see some examples.
A poset (L, ) is called lattice ordered set if for every pair of elements x, y L, thesup (x, y) and inf (x, y) exist in L.
Example 1:
Let S be a nonempty set. Then (P(S),  ) is a lattice ordered set. For (P (S),  ) is a poset. Further for any subsets A, B of S,
inf (A, B) = A  B P(S) and sup (A, B) = A B  P(S).

Example 2:
Every totally ordered set is a lattice ordered set (Prove !).
Example 3:
Consider the set of all positive integer Z+ with divisor as a relation, i.e., a  b if and only if ab.Then (Z+ , ) is a poset.
For, if a, b Z+, then inf (a, b) = GCD(a, b) Z+ and sup (a, b) = LCM(a, b) Z+.
Thus, inf (a, b) and sup (a,b) exist in Z+ for any two element a, b  Z+.
Hence (Z+ , ) is a lattice ordered set.

In fact (Dn, ) ( Dn denotes the set of all positive divisors of positive number n ) is alsoa lattice ordered set.
Example 4:
Consider the set B, where Bn = {(l1, l2, … , ln) / li = 0 or 1, for 1 r n}.
Define the relation ' by (i1, i2, … , in) ' (j1, j2, … , jn) if and only if irjr , 1 r n.
Note that here in the expression ir jr,  is usual less than or equal to.
We have already seen in Example 7 of Section 6.2.1 that (Bn, ') is a poset.
Observe that
inf [ (i1, i2, ….. ,in), (j1, j2, … , jn)] = (min (i1, j1), min (i2,j2), …. , min (in, jn) ) and
sup [ (i1, i2, … , in), (j1, j2, … , jn)] = (max (i1, j1), max (i2,j2), …. , max (in, jn) )
Since min (ir, jr) and max (ir, jr) is either 0 or 1,
so, inf { (i1, i2,… , in), (j1,j2, .. ,jn) } and sup { (i1, i2, … , in), (j1, j2, … , jn) } exist in B.
Thus, (Bn,  ) is a lattice ordered set.
Example 5:
Poset represented by the Hasse diagram is not a lattice ordered set since inf (a, b) does not exist.

Example 6:
Poset represented by the Hasse diagram is not a lattice ordered set as sup (f, g) does not exist.