And more discrete math fun!
Pages: 12
As you've likely noticed, I can't find a decent math forum so here I am again! I was actually sick during the lecture for this section, and the book is kind of rough so here's a question:
Right now I have this set as NOT being reflexive because not every element is related to itself. There is no (3,3) relation.
IS symmetric because when xRy is true, yRx is also true. (I'm not sure if this valid or not though. Do ALL elements have to have symmetric properties for this to be true? ie, do I need R = {(1,3),(3,1),(2,3),(3,2)} as well?)
Set S is NOT transitive, because when xRy is true, yRz when xRz is NOT true. Also don't know if this is valid.
Basically, do all three properties need to be met for all elements for them toe be true? Book only specifies that the reflexive property must be met in all elements for the set to be reflexive.
Hope I explained my problem good enough!
Thanks
Determine which of the reflexive, symmetric, and transitive properties are satisfied with the given relation R defined on set S. S = {1,2,3} and R = {(1,1),(1,2),(2,1),(2,2)} |
Right now I have this set as NOT being reflexive because not every element is related to itself. There is no (3,3) relation.
IS symmetric because when xRy is true, yRx is also true. (I'm not sure if this valid or not though. Do ALL elements have to have symmetric properties for this to be true? ie, do I need R = {(1,3),(3,1),(2,3),(3,2)} as well?)
Set S is NOT transitive, because when xRy is true, yRz when xRz is NOT true. Also don't know if this is valid.
Basically, do all three properties need to be met for all elements for them toe be true? Book only specifies that the reflexive property must be met in all elements for the set to be reflexive.
Hope I explained my problem good enough!
Thanks
And another problem that I have no clue on. Same rules apply to first one:
All I can take from this is that |x| = |y|, but what does that matter?
| S is the set of all real numbers and xRy means that x^2 = y^2 |
All I can take from this is that |x| = |y|, but what does that matter?
For a relation to be reflexive, for any x, xRx must be true.
For a relation to be transitive, for any x, y, z, if xRy and yRz, then xRz must be true.
For a relation to be symmetric, for any x, y, if xRy, then yRx must be true.
Note that something like R = {} is transitive and symmetric, but not reflexive.
Elements cannot be reflexive or transitive, the relation as a whole has those properties.
For a relation to be transitive, for any x, y, z, if xRy and yRz, then xRz must be true.
For a relation to be symmetric, for any x, y, if xRy, then yRx must be true.
Note that something like R = {} is transitive and symmetric, but not reflexive.
Elements cannot be reflexive or transitive, the relation as a whole has those properties.
So, with the above set. It is NOT reflexive, IS symmetric, and NOT transitive?
Could you explain that a little more? I don't quite understand
| Note that something like R = {} is transitive and symmetric, but not reflexive. |
Could you explain that a little more? I don't quite understand
It is transitive. (aRa and aRc => aRc) is true for all a,c in S. Note that this condition is a special case of (aRb and bRc => aRc), where a=b (it's not possible in this case for a!=b!=c!=a, since R is only applied to two elements of S).
In particular, (1R1 and 1R2 => 1R2) and (2R2 and 2R1 => 2R1).
In particular, (1R1 and 1R2 => 1R2) and (2R2 and 2R1 => 2R1).
Last edited on
| In particular, (1R1 and 1R2 => 1R2) and (2R2 and 2R1 => 2R1) |
That's not transitive, I dont think. I think transitive would be 1R1 and 1R2 then 2R3, would mean in fact that 1R3
But R isn't applied to more than two elements of S, and the condition for transitiveness doesn't require a, b, and c to be three distinct values. If it did require that, firedraco's example of {} being transitive would be false.
Last edited on
Sorry I had it a little wrong, or had something extra perhaps
xRz when xRy and yRz.
BUT, I don't believe it is transitive if xRz directly
xRz when xRy and yRz.
BUT, I don't believe it is transitive if xRz directly
| Could you explain that a little more? I don't quite understand |
It is transitive because the statement:
For all x, y, z: xRy & yRz -> xRz
is always true; since there are no pairs in R, xRy & yRz is always false, hence the conditional is always true.
It is symmetric for the same reason (no pairs in R, xRy is always false).
It is NOT reflexive because reflexivity is:
For all x, xRx.
Which is obviously always false, since there is nothing in R.
| I think transitive would be 1R1 and 1R2 then 2R3 |
No. The definition of transitivity is:
For all x, y, z: xRy & yRz -> xRz
x, y, z do not have to be distinct elements, they can all be equal or not, it doesn't matter.
| BUT, I don't believe it is transitive if xRz directly |
I don't understand what you mean by "if xRz directly". Could you rephrase?
Last edited on
Here I'll give an example
With how the professor taught he said this:
2R4 because 2R3 and 3R4, so this is transitive (indirect was just a word I put on it)
1R3 is not transitive, because it had direct relation, right there. Even though there is a 2R3, and 1R2
S = {1,2,3,4} R = {(1,1),(1,2),(1,3),(1,4),(2,3),(3,4)} |
With how the professor taught he said this:
2R4 because 2R3 and 3R4, so this is transitive (indirect was just a word I put on it)
1R3 is not transitive, because it had direct relation, right there. Even though there is a 2R3, and 1R2
IMO, that is incorrect. You cannot say that R is transitive because of that.
Also, I say again, elements (like 1R3) *cannot* be transitive, the *relation* as a whole is transitive or not.
Btw, sorry for the massive edit. :P
Also, I say again, elements (like 1R3) *cannot* be transitive, the *relation* as a whole is transitive or not.
Btw, sorry for the massive edit. :P
Let's examine the condition in detail:
What the condition says, mathematically, is that for all triples (a,b,c): IF (aRb and bRc are true) THEN aRc must also be true. Therefore, to prove that the relation is not transitive, you need to find a case where (aRb and bRc) is true AND aRc is false. A case where both are false doesn't disprove the transitivity of the relation.
1) 1R1: T
2) 1R2: T
3) 1R3: F
4) 2R1: T
5) 2R2: T
6) 2R3: F
7) 3R1: F
8) 3R2: F
9) 3R3: F
(#1 and #1 => #1) is true.
(#1 and #2 => #2) is true.
#3 is false, but so is (#1 and #3), so this is not a counterexample.
(#2 and #4 => #1) is true.
(#2 and #5 => #2) is true.
#3 is false, but so is (#2 and #6), so this is not a counterexample.
(#3 and #7) is false. Not a counterexample.
(#3 and #8) is false. Not a counterexample.
(#3 and #9) is false. Not a counterexample.
(#4 and #1 => #4) is true.
(#4 and #2 => #5) is true.
(#4 and #3) is false.
And so on. If you continue the analysis, you'll find there's not one case that serves as a counterexample.
What the condition says, mathematically, is that for all triples (a,b,c): IF (aRb and bRc are true) THEN aRc must also be true. Therefore, to prove that the relation is not transitive, you need to find a case where (aRb and bRc) is true AND aRc is false. A case where both are false doesn't disprove the transitivity of the relation.
1) 1R1: T
2) 1R2: T
3) 1R3: F
4) 2R1: T
5) 2R2: T
6) 2R3: F
7) 3R1: F
8) 3R2: F
9) 3R3: F
(#1 and #1 => #1) is true.
(#1 and #2 => #2) is true.
#3 is false, but so is (#1 and #3), so this is not a counterexample.
(#2 and #4 => #1) is true.
(#2 and #5 => #2) is true.
#3 is false, but so is (#2 and #6), so this is not a counterexample.
(#3 and #7) is false. Not a counterexample.
(#3 and #8) is false. Not a counterexample.
(#3 and #9) is false. Not a counterexample.
(#4 and #1 => #4) is true.
(#4 and #2 => #5) is true.
(#4 and #3) is false.
And so on. If you continue the analysis, you'll find there's not one case that serves as a counterexample.
Last edited on
You know I just thought of it, and you're right. The transitive property is kind of like an implicit relation. If you make it explicit, that changes nothing about the relation.
If A = B, and B = C, then through this property A = C.
If I go straight out and say now that A = C, there is nothing wrong with that, that I can see at least.
Now with that empty set, I am still confused. If there are NO elements in the set, how are any of the properties true? The only thing I could see that would possibly be true, is what you say is false, that is the reflexive property.
The way I see it, and empty set is just a set with the null character (could be wrong here?). So if there was only one element in a set, it HAS to be related to itself, there is nothing else in the set to be related to
EDIT: To respond to helios
So, I was correct in thinking that if there was a direct relation between two elements, then there can't be any transitivity between those two?
If A = B, and B = C, then through this property A = C.
If I go straight out and say now that A = C, there is nothing wrong with that, that I can see at least.
Now with that empty set, I am still confused. If there are NO elements in the set, how are any of the properties true? The only thing I could see that would possibly be true, is what you say is false, that is the reflexive property.
The way I see it, and empty set is just a set with the null character (could be wrong here?). So if there was only one element in a set, it HAS to be related to itself, there is nothing else in the set to be related to
EDIT: To respond to helios
So, I was correct in thinking that if there was a direct relation between two elements, then there can't be any transitivity between those two?
Last edited on
| Now with that empty set, I am still confused. If there are NO elements in the set, how are any of the properties true? The only thing I could see that would possibly be true, is what you say is false, that is the reflexive property. |
They are true through the definition of the -> symbol:
A B A->B
T T T
T F F
F T T
F F T
Note that when the A (the antecedent) is false, the conditional is true.
| The way I see it, and empty set is just a set with the null character (could be wrong here?). So if there was only one element in a set, it HAS to be related to itself, there is nothing else in the set to be related to |
No, the empty set has nothing, i.e. for all x,y, xRy is false.
Last edited on
| If there are NO elements in the set, how are any of the properties true? |
Last edited on
Oh I feel like these symbols are important. What do
-> and
=>
mean? Professor nor the book have mentioned either
-> and
=>
mean? Professor nor the book have mentioned either
Really? I would expect that you would've gone through some logic at least to get there.
http://en.wikipedia.org/wiki/List_of_logic_symbols
http://en.wikipedia.org/wiki/List_of_logic_symbols
The arrows are material implication.
http://en.wikipedia.org/wiki/Material_implication
Sheesh firedraco, helios. I keep having to refresh to make sure I'm not posting after you've already answered, heh.
http://en.wikipedia.org/wiki/Material_implication
Sheesh firedraco, helios. I keep having to refresh to make sure I'm not posting after you've already answered, heh.
Ok so if the former is true, the latter is also true. If the former is false, nothing is said about the latter.
And yea there is a logic course but it's the prereq to the next discrete math course. I guess this is the intro to discrete?
And now this is starting to make more sense. Cool!
Now, what about my second question up there :D
And yea there is a logic course but it's the prereq to the next discrete math course. I guess this is the intro to discrete?
And now this is starting to make more sense. Cool!
Now, what about my second question up there :D
Is this the question you're referring to?
About transitivity:
Elements do not have transitivity between them. Relations as a whole are transitive or not if and only if they fulfill the condition:
For all x,y,z: xRy & yRz -> xRz
You might want to rephrase your question, or restate it.
| So, I was correct in thinking that if there was a direct relation between two elements, then there can't be any transitivity between those two? |
About transitivity:
Elements do not have transitivity between them. Relations as a whole are transitive or not if and only if they fulfill the condition:
For all x,y,z: xRy & yRz -> xRz
You might want to rephrase your question, or restate it.
Pages: 12