4. a) The 16 relations on the set {0, 1} are listed below.
R1 = Ø
R2 = { (0, 0) }
R3 = { (0, 1) }
R4 = { (1, 0) }
R5 = { (1, 1) }
R6 = { (0, 0), (0, 1) }
R7 = { (0, 0), (1, 0) }
R8 = { (0, 0), (1, 1) }
R9 = { (0, 1), (1, 0) }
R10 = { (0, 1), (1, 1) }
R11 = { (1, 0), (1, 1) }
R12 = { (0, 0), (0, 1), (1, 0) }
R13 = { (0, 0), (0, 1), (1, 1) }
R14 = { (0, 0), (1, 0), (1, 1) }
R15 = { (0, 1), (1, 0), (1, 1) }
R16 = { (0, 0), (0, 1), (1, 0), (1, 1) }
b) Now determine which of these relations are partial order relations, that is, which of these relations are reflexive, antisymmetric and transitive.
R1 = Ø is not a partial order (not
reflexive).
R2 = { (0, 0) } is not a partial order (not reflexive).
R3 = { (0, 1) } is not a partial order (not reflexive).
R4 = { (1, 0) } is not a partial order (not reflexive).
R5 = { (1, 1) } is not a partial order (not reflexive).
R6 = { (0, 0), (0, 1) } is not a partial order (not reflexive).
R7 = { (0, 0), (1, 0) } is not a partial order (not reflexive).
R8 = { (0, 0), (1, 1) } is a partial order. It is reflexive (for all x in the set {0, 1} x R8 x),
antisymmetric (for all distinct x, y in {0, 1}, if x R8 y then y is not related
to x), transitive (for all x, y, z in {0,1}, if x R8 y and y R8 z
then x R8 z).
R9 = { (0, 1), (1, 0) } is not a partial order (not reflexive).
R10 = { (0, 1), (1, 1) } is not a partial order (not reflexive).
R11 = { (1, 0), (1, 1) } is not a partial order (not reflexive).
R12 = { (0, 0), (0, 1), (1, 0) } is not a partial order (not reflexive).
R13 = { (0, 0), (0, 1), (1, 1) }is a partial order.
It is reflexive (for all x in the set {0, 1} x R13 x), antisymmetric (for all
distinct x, y in {0, 1}, if x R13 y then y is not related to x), transitive
(for all x, y, z in {0, 1}, if x R13 y and y R13 z then x R13
z).
R14 = { (0, 0), (1, 0), (1, 1) }is a partial order.
It is reflexive (for all x in the set {0, 1} x R14 x), antisymmetric (for all
distinct x, y in {0, 1}, if x R14 y then y is not related to x), transitive
(for all x, y, z in {0, 1}, if x R14 y and y R14 z then x R14
z).
R15 = { (0, 1), (1, 0), (1, 1) }is not a partial order (not reflexive).
R16 = { (0, 0), (0, 1), (1, 0), (1, 1) }is not a partial order (it is reflexive
and transitive, but not antisymmetric).