Answer to Question #167147 in Discrete Mathematics for ramez ahmad

Question

A) Let A={1,2,3,4}A={1,2,3,4} and R a relations on A whose matrices is M_R = ⎡⎣⎢⎢⎢1010111000101011⎤⎦⎥⎥⎥[1101010011110001],                      
1) Show that (A,R)(A,R) is a poset                        (5 pts) 2) Find maximal, minimal, least and greatest if they exist    (4 pts)

Answer 1

The tables of relations R₁ and R₂ (tables at the top of the picture) can be rewritten as they are shown at the bottom of the picture.

From these tables it is clear that R₂ is a reflexive relation (for all x R₂(x,x)=1) but R₁ is not reflexive (since R₁(4,4)=0).

Both R₁ and R₂ are anti-symmetric (since their matrices are upper-triangular). This means that if $x\ne y$ and R_i(x,y)=1 then R_i(y,x)=0. Indeed, if R_i(x,y)=1then the cell (x,y) is located at the upper triangle of the matrix. Therefore, the cell (y,x) is located at the lower triangle and R_i(x,y)=0.

Both R₁ and R₂ are transitive. Indeed, the equality R_i(x,y)=1 implies that the y-column of the matrix is located to the right of the x-column of the matrix. The equality R_i(y,z)=1 implies that the z-column of the matrix is located to the right of the y-column of the matrix. therefore, the z-column is located to right of the x-column. The transitivity will be broken, if R_i(x,z)=0.

From the tables we get that this case may be possible only if x=2 and z=4.

But for all y R₁(y,z)=R₁(y,4)=0 and hence, there is no possibilities to break transitivity of R₁.

If R₂(x,y)=R₂(2,y)=1 then y must be equal to 2 and therefore $R_2(y,z)=0\ne 1$. This also implies that R₂ is transitive.

Since R₁ and R₂ are ant-i-symmetric and transitive relations, they are partial orders on A.

With respect to the relation R₁ 2 and 4 are two maximal elements, but not the greatest, and 3 is a minimal element. As it is a unique minimal element, it is the least element also.

With respect to the relation R₂ 2 and 4 are two minimal elements, but not the least, and 3 is a maximal element. As it is a unique maximal element, it is the greatest element also.