2
$\begingroup$

Main question: Is my solution for this proof correct? Also, I have some questions about my solution and the definitions of Reflexive, Symmetric, and Transitive. Here is the question and here is my solution.

This is the question in full:

"Determine if reflexive, symmetric, and transitive for the following: O is the relation defined on $\mathbb{Z}$ as follows: For all m,n ∈ $\mathbb{Z}$, m O n ⇔ m-n is odd"

This is my solution:

Reflexive: Must show x O x. We can observe that x-x = 0, which is not odd, thus there is no x O x, therefore not reflexive.

Symmetric: For all integers m and n, if m O n then n O m. Proof via contradiction: Suppose ! n O m, then we can gather n - m is not odd. Thus n - m = 2k where k is an integer. But observe m - n = -(n-m), via substitution we can see m-n= -(2k) = 2(-k) but then this entails that m-n is equal to 2(-k) which means it is positive, a contradiction. Thus our original statement is symmetric.

Transitive:
via definition, for all integers m,n,p, if m O n and n O p then m O p. This is false, via proof of negation. "there exist integers m,n,p, so m O n and n O p but !m O p" Suppose integers m,n,p exist, let m=7, n=4, p=1. Observe 7-4=3 which is odd, and 4-1=3 which is odd, but 7-1=6 which is even - thus original statement is not transitive.

Some clarity issues: (assuming my solution is correct) (edit: I hope this is okay, asking for additional clarity within a question)

1) Does the n in this specific example have to do anything with reflexivity?

My textbook defines reflexive as "R is reflexive if, and only if for all x ∈ A, x R x."

Ok but in this question above, it's defined for all m and n. From my understanding, reflexive means it simply has a relationship to itself. i.e. in an independent example, the set A = {1,2,3,4}, it is only reflexive if (1,1), (2,2) (3,3) and (4,4) exist. So to clarify, it has nothing to do with the n in the original question then?

So if I had the number line laid out, I would be looking at 1 and then 2 and then 3 and ..... etc for infinite - and then seeing if that selected integer (m in this case) had a relationship with itself?

So when the original statement has reference to "m,n ∈ $\mathbb{Z}$" it's really just saying the relationship requires two different integers, am I right? But as per reflexive, in this case, I am only looking at one integer (m) at a time, and if it has a relationship with itself. Am I right in my thinking?

2) Is a relationship symmetric so long as the negation cannot be proved? Even if there are no relationships within the set?

Symmetry defined by my text is: R is symmetric if and only if , for all x,y ∈ A, if x R y then y R x.

By the way this is worded, can I safely assume it can only be false if there is a relationship to begin with? Say I modified the original question so it is defined only on the set A = {7,9} or A = {1}. Then no relationship can exist in either set, correct? But regardless, is it safe to say this is not reflexive BUT is symmetric as it does not defy the definition of symmetry?

3) Likewise for transitive -

what if the original question had a defined set and it had no relationship (that is say they were all positive when m-n)? Is it still transitive?

Thank you.

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

1) In all parts of the definition of the relation $m$ O $n$, the integers $m$ and $n$ could possibly be the same - there's nothing ruling it out.

2) and 3) If the relation is the empty relation, then it is indeed symmetric and transitive! This is related to the fact that an implication "if $p$ then $q$" is indeed true if $p$ is always false - we call such an implication "vacuously" true. So the empty relation, if you like, is "vacuously symmetric and transitive".

One more comment: a shorter proof of symmetry for O is "if $m$ O $n$, then $m-n$ is odd, hence $m-n=2k+1$ for some integer $k$; but then $n-m=-(2k+1) = 2(-k-1)+1$ is also odd, and so $n$ O $m$."

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ I presume my solution is valid then? (It's one of the questions without solutions in my text (Discrete Math by Susanna S. Epp if anyone was curious). That vacuous truth does make sense! Lastly on the symmetrical proof, I like your version more, it's clean. But to clarify one thing, from the textbook solutions and definitions, Odd = 2k+1 and even = 2k, I presume k can be +/- (like in my solution and yours) because k is just "some integer" and the definitions as I recall state nothing about +/- . $\endgroup$ – supakutdiamnds Aug 15 '15 at 3:28
  • $\begingroup$ Yes, odd and even integers can be negative (as can the $k$) - of course that's important in this proof. Your proof of (2) seems valid to me, although you wrote "positive" in its last sentence when you meant "even". $\endgroup$ – Greg Martin Aug 15 '15 at 4:18
2
$\begingroup$

For symmetric, $n-m =m-n-2(m-n) $.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.