Unit3 - Subjective Questions

The Principle of Inclusion-Exclusion (PIE) provides a way to calculate the size of the union of multiple sets by including the cardinalities of single sets, excluding the cardinalities of pairwise intersections, and re-including the cardinalities of triple intersections, and so on.

For three finite sets , , and , the formula is:

Explanation:

1. Include: Sum the sizes of the individual sets (). However, elements in the intersections are counted more than once.
2. Exclude: Subtract the sizes of the pairwise intersections to correct the double counting.
3. Include: Elements common to all three sets were added 3 times in step 1 and subtracted 3 times in step 2, meaning they are not counted at all. We must add back to ensure they are counted exactly once.

Given:

• (Total people)
• , ,

To find: (People speaking at least one language).

Using the Principle of Inclusion-Exclusion:

Calculation:

Answer: 80 people speak at least one of the languages.

1. Pigeonhole Principle (PHP):
If pigeons are placed into pigeonholes where , then at least one pigeonhole must contain more than one pigeon.

• Example: In a group of 13 people, at least two must have their birthday in the same month (since there are 13 people and only 12 months).

2. Generalized Pigeonhole Principle:
If objects are placed into boxes, then there is at least one box containing at least objects.

• Example: If 21 pigeons are placed into 4 holes, at least one hole contains pigeons.

We apply the Pigeonhole Principle.

• Pigeonholes (k): The distinct colors available. Here, (Red, Blue, Black).
• Pigeons (n): The socks pulled from the drawer.

We want to guarantee at least 2 socks of the same color (a pair). This means we want one hole to have at least 2 items.

According to PHP, if we pick socks such that , at least one color will repeat.

• If we pick 3 socks, it is possible to get one of each color (Red, Blue, Black).
• If we pick socks, it is impossible to have them all be distinct colors because there are only 3 colors.

Conclusion: The minimum number of socks required is 4.

Definition of Relation:
A binary relation from set to set is a subset of the Cartesian product . If , it is a relation on set .

Properties of Relations on Set :

1. Reflexive: A relation is reflexive if for every .
   • Notation: .
2. Symmetric: A relation is symmetric if implies for all .
3. Antisymmetric: A relation is antisymmetric if and imply .
   • Note: It is never the case that is related to and is related to unless and are identical.
4. Transitive: A relation is transitive if and imply for all .

(a) Matrix Representation ():
We define the matrix where if and $0$ otherwise.

(b) Directed Graph Representation:

• Vertices: Draw three nodes labeled 1, 2, and 3.
• Edges:
  • Draw a self-loop on node 1 (since ).
  • Draw a self-loop on node 2 (since ).
  • Draw a self-loop on node 3 (since ).
  • Draw a directed arrow from 1 to 2 (since ).
  • Draw a directed arrow from 2 to 3 (since ).

Definition of Composition: if there exists such that and .

1. Calculating :

• Start with :
  • , check starting with 2:
  • , check starting with 3:
  • , check starting with 1:
• Result:

2. Calculating :

• Start with :
  • , check starting with 1:
  • , check starting with 2:
  • , check starting with 3:
• Result:

Definition: A relation on a set is an Equivalence Relation if it is Reflexive, Symmetric, and Transitive.

Proof:

1. Reflexive:

   • For any , .
   • Since divides 0 (as ), .
   • So, is Reflexive.

2. Symmetric:

   • Let such that . Then , so for some integer .
   • Then .
   • Since is an integer, , so .
   • So, is Symmetric.

3. Transitive:

   • Let and .
   • Then and for integers .
   • Adding these equations: .
   • .
   • Since is an integer, , so .
   • So, is Transitive.

Conclusion: Since the relation is reflexive, symmetric, and transitive, it is an Equivalence Relation.

Definition:
Let be an equivalence relation on . The equivalence class of an element , denoted by or , is the set of all elements in that are related to by .

Finding Classes for the given :
We examine each element in :

• Class of 1: .
• Class of 2: .
• Class of 3: . (Same as ).
• Class of 4: .
• Class of 5: . (Same as ).

Partition:
The distinct equivalence classes are , , and .

Definition of Partial Order Relation (POSET):
A relation on a set is called a Partial Order if it satisfies the following three properties:

1. Reflexive: .
2. Antisymmetric: , if and , then .
3. Transitive: , if and , then .

The set together with the partial order is denoted as or .

Difference from Equivalence Relation:

• Symmetry vs. Antisymmetry: An Equivalence relation requires the Symmetric property (if then ), whereas a Partial Order requires the Antisymmetric property (if and , then must equal ; essentially, the relation implies a direction or hierarchy).

Steps to Draw:

1. Elements: .
2. Relation: iff divides .
3. Identify Immediate Predecessors (Covering relations):
   • 2 divides 4, 6.
   • 3 divides 6.
   • 4 divides 8, 12.
   • 6 divides 12.
   • 8 divides 24.
   • 12 divides 24.

Structure of Diagram (Bottom to Top):

• Level 1 (Minimals): 2, 3.
• Level 2:
  • 4 is above 2.
  • 6 is above 2 and 3.
• Level 3:
  • 8 is above 4.
  • 12 is above 4 and 6.
• Level 4 (Maximal):
  • 24 is above 8 and 12.

Edges to Draw:
(2,4), (2,6), (3,6), (4,8), (4,12), (6,12), (8,24), (12,24).

Definitions:

1. Maximal Element: An element is maximal if there is no element such that $m
   eq xm \preceq x$. (In a Hasse diagram, it is an element with no edges going up from it).
2. Minimal Element: An element is minimal if there is no element such that $m
   eq xx \preceq m$. (In a Hasse diagram, it is an element with no edges coming up from below).
3. Greatest Element (Maximum): An element is the greatest element if . This element must be unique if it exists.
4. Least Element (Minimum): An element is the least element if . This element must be unique if it exists.

Can a POSET have more than one maximal element?
Yes. A POSET can have multiple maximal (and minimal) elements. However, if it has multiple maximal elements, it has no Greatest element.

Definition of Lattice:
A Lattice is a Partially Ordered Set in which every pair of elements has both a Least Upper Bound (LUB) and a Greatest Lower Bound (GLB) contained within .

Operations:

1. Join () / LUB: The Least Upper Bound of and , denoted , is an element such that , , and if any other element satisfies this, then .
2. Meet () / GLB: The Greatest Lower Bound of and , denoted , is an element such that , , and if any other element satisfies this, then .

Statement:
For any elements in a Lattice :

Proof of (1):

• By definition of GLB, .
• Also, by reflexivity, .
• Thus, is an upper bound of .
• Since is the least upper bound, .
• Conversely, by definition of LUB, .
• By antisymmetry, if and , then . Therefore, .

Proof of (2):

• By definition of LUB, .
• Also, .
• Thus, is a lower bound of .
• Since is the greatest lower bound, .
• Conversely, by definition of GLB, .
• By antisymmetry, .

1. Distributive Lattice:
A lattice is distributive if the meet and join operations distribute over each other for all :

• Example: The power set of any set under and is a distributive lattice.

2. Complemented Lattice:
A lattice is complemented if:

• It is a Bounded Lattice (has a Least element $0$ and Greatest element $1$).
• For every element , there exists at least one complement such that:

Key Difference: Distributive refers to the algebraic distribution of operators, while Complemented refers to the existence of "opposite" elements that combine to form the bounds of the lattice.

Definition of Sublattice:
Let be a lattice. A non-empty subset of is called a sublattice of if itself is a lattice with respect to the same operations and defined on .

Condition:
A non-empty subset is a sublattice if and only if is closed under the operations of meet and join defined in .

Specifically:

1. For every , the element (calculated in ) must belong to .
2. For every , the element (calculated in ) must belong to .

Analysis:

• Set: .
• Relation: Subset Inclusion .

To prove it is a Lattice:
We must show that for any two sets , the Least Upper Bound (LUB) and Greatest Lower Bound (GLB) exist in .

1. Join / LUB ():

• The LUB of two sets and in a power set lattice is their Union .
• Since the union of any two subsets of is also a subset of , .
• is the smallest set containing both and .

2. Meet / GLB ():

• The GLB of two sets and is their Intersection .
• Since the intersection of any two subsets of is a subset of , .
• is the largest set contained in both and .

Conclusion:
Since every pair of elements has a unique LUB (Union) and GLB (Intersection) within the set, is a Lattice.

Definitions:

• A Bounded Lattice is a lattice that has a Least element (usually denoted $0$) and a Greatest element (usually denoted $1$).
• A Finite Lattice is a lattice with a finite number of elements, say .

Proof:

1. Finding the Greatest Element ($1$):

   • Since is a lattice, the join () of any two elements exists.
   • Consider the join of all elements in the finite set: .
   • By definition of join, for all .
   • Therefore, is the greatest element of .

2. Finding the Least Element ($0$):

   • Similarly, the meet () of any two elements exists.
   • Consider the meet of all elements: .
   • By definition of meet, for all .
   • Therefore, is the least element of .

Conclusion: Since a greatest element and a least element can always be constructed for a finite set using the lattice operations, every finite lattice is bounded.

1. Inverse Relation ():
The inverse of a relation from set to is the relation from to defined by .

2. Complement of a Relation ():
The complement of a relation on set is the set of all pairs in the Cartesian product that are NOT in . .

Calculation:
Given and .

• Find :
  Swap components of : .

• Find :
  Total pairs in pairs.
  contains all pairs EXCEPT and .
  .

Structure Analysis:

• is at the bottom.
• and are above .
• is above both and .
• is above .

Checking Lattice Properties (Existence of LUB and GLB for all pairs):

1. Pair :

   • LUB (): The upper bounds for and are and . The least of these is . So .
   • GLB (): The lower bound for and is . So .

2. Comparable pairs (e.g., ):

   • Since , LUB is , GLB is .

Conclusion:
In this structure (often called the 'Diamond' lattice if extended, but here specifically a simple diamond shape between a and d), every pair of elements has a unique supremum and infimum.

• For any , , , etc.

Yes, this Hasse diagram represents a Lattice.