Define the following two relations over N 012 nRm iff n and

Define the following two relations over N = {0,1,2,...}: nRm iff n and m have the same number of digits nPm iff n does not have more digits than m Determine whether these new relations R and P are reflexive, symmetric, antisymmetric, transitive, equivalence relations, partial orders, and total orders.

Solution

Reflexive

a number n trivially has same number of digits as itself. Hence, nRn

A number also does not have more digits that itself. Hence, nPn

Hence, R and P are both reflexive

Symmetric

nRm implies n and m have same number of digits ,hence mRn is also true.

nPm implies n does not have more digits than m but this does not imply m does not have more digits than m. Hence, mPn need not be true.

Hence, R is symmetric , P is not symmetric.

Antisymmetric

R is symmetric hence, nRm implies mRn and vice versa. but nRm and mRn does not imply n=m, it only means n and m have equal number of digits.

nPm implies n does not have more digits than m

mPn implies m does not have more digits than n

Hence, nPm=mPn means m=n

Hence , neither R nor P is antisymmetric

Transitive

nRm,mRp implies n and m have equal number of digits, m and p have equal number of digits

Hence, n and p have equal number of digits ie nRp

nPm,mPk implies n does not have more digits than m, m does not have more digits than k hence, n does not have more digits than k

Hence, nPk.

Hence, both R and P are transitive.

Equivalence relation

R is reflexive,symmetric and transitive. Hence R is an equivalence relation

P is not symmetric hence P is not an equivalence relation

Partial order

A partial order requires antisymmetry property ,hence neither R or P is a partial order.

Total order

Total order also requires antisymmetry property, hence neither R or P is a total order.