Question

Define relation R on the set of natural numbers as follows: xRy iff each each prime factor of x is a factor of y. Prove that X is a partial order.

Answer 1

Answer: This relation is reflexive, antisymmetric and transitive so it is a partial order relation.

Step-by-step explanation: A relation is called a partial order relation if and only if it is reflexive, antisymmetric and transitive. We will check these three characteristics for the given relation.

Reflexive: We need to have that for all
`x\in\mathbb{N}`,
`xRx`. This is obviously true since each prime factor of
`x` is certainly a factor of
`x`.

Antisymmetric: We need to show that for all
`x,y\in\mathbb{N}` if both
`xRy` and
`yRx` then it must be
`x=y`. To show this suppose that two, otherwise arbitrary, natural numbers
`x` and
`y` are taken such that
`xRy` and
`yRx`. The first of these two says that every prime factor of
`x` is a factor of
`y`. The second one says that every prime factor of
`y` is a factor of
`x`. This means that every prime factor of
`x` is also the prime factor of
`y` and that every prime factor of
`y` is the prime factor of
`x` i.e. that
`x` and
`y` have the same prime factors meaning that they have to be equal.

Transitive: The relation is called transitive if from
`xRy` and
`yRz` then it must also be
`xRz`. To see that this is true of the given relation take some natural numbers
`x,y` and
`z` such that
`xRy` and
`yRz`. The first condition means that each prime factor of
`x` is the factor of
`y` i.e. that all the prime factors of
`x` are contained among the prime factors of
`y`. The second condition means that each prime factor of
`y` is a factor of
`z` i.e. that all the prime factors of
`y` are contained among the prime factors of
`z`. So we have that all of the prime factors of
`x` are contained among the prime factors of
`y` and they themselves are contained among the prime factors of
`z`. This means that certainly all of the prime factors of
`x` are contained among the prime factors of
`z` meaning by the given definition of
`R` that
`xRz` which is what we needed to show.