Discrete math - hard question

Question

Let R be the “greater than” relation on the set of integers, formally defined as follows:

for all x, y ∈ Z, x R y ß> x > y.

Please show your work to determine whether or not the given relation is:

(a) Reflexive:

(b) Symmetric:

(c) Anti-symmetric:

(d) Transitive

Answer 1

(a)

Since reflexivity is universally quantified, we need only provide one counter example to prove it is not true if it is indeed not true (which is indeed the case).

Choose zero. Zero is not greater than zero (though all integers are counter examples). Therefore R is not reflexive.

(b)

Symmetry is also universally quantified. So, as a counter example choose zero and one. One is greater than zero, but zero is not greater than one.

(c)

Let (a, b) be in R, which is to a > b. Then (by definition of ">") a is not equal to b and (b,a) is not in R. This logically implies the definition of antisymmetric which is if [(a,b) is in R and a is not equal to b] then (b,a) is not in R. Symbolically (where ~ is "NOT"): P --> (Q & S) is equivalent by material implication to ~P or (Q & S). By distribution we get (~P or Q) & (~P or S). By conjunction elimination we get ~P or S. By disjunction introduction we get (~P or ~Q) or S. By Demorgan we get ~(P &Q) or S. By material implication we get (P & Q) --> S.

Another common definition of antisymmetric (using the statements represented by P, Q, and S) is (P & ~S) --> ~Q. Equivalent to this (by contrapositive) is Q --> ~(P & ~S). Equivalent to this by Demorgan is Q --> (~P or ~~S). Equivalent to this by double negation is Q --> (~P or S). So, assume by conditional proof that a = b. Then (a,b) is not in R and (b,a) is not in R. Symbolically this is Q --> (~P & S). By conjunction elimination we get Q --> ~P. By disjunction introduction we get Q --> (~P or S), which is the aforementioned equivalent to the definition of antisymmetric.

(d)

Assume by conditional proof that a > b and b > c. Additive property of > gives us a + b > b + c. Subtracting b on both sides gives us a > c. Therefore if a > b and b > c, then a > c, which is the definition of transitive.