mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   R.D Silverman's number theory homework (https://www.mersenneforum.org/showthread.php?t=14901)

science_man_88 2011-01-21 15:47

[QUOTE=R.D. Silverman;247935]Then your question was not completely stated.[/QUOTE]

Beef it out in PM people! why else would PM be in this forum?

Mr. P-1 2011-01-21 15:56

[QUOTE=science_man_88;247933]according to sharing at least one parent yes son~son is true, with x!~x then it can't be possible hence any transitive or reflexive forms that need it are disallowed to be equivalence relations.[/QUOTE]

Lets use a different symbol for xilman's variant. Lets call his relation #. So Son ~ Son, but Son !# Son.

To show that a property (symmetry, reflexivity, transitivity) does not hold, you only need to find a single counter example. So Son # Daughter AND Daughter # Son BUT Son !# Son proves that # is not transitive. And you've already shown that it's not reflexive. Is it symmetric?

To show that a property does hold, you need to show this for every combination of variables. To show that ~ is symmetric, you need to show that for every combination of values of x and y, IF x ~ y THEN y ~ x. So far, you've only looked at one particular instance: x = Son, y = Daughter. To show that ~ is transitive, you need to show that for every combination of values of x, y, and z, IF x ~ y AND y ~ z THEN x ~ z. Again, so far, you've only looked at one particular instance: x = z = Son, y = Daughter.

science_man_88 2011-01-21 16:03

[QUOTE=Mr. P-1;247937]Lets use a different symbol for xilman's variant. Lets call his relation #. So Son ~ Son, but Son !# Son.

To show that a property (symmetry, reflexivity, transitivity) does not hold, you only need to find a single counter example. So Son # Daughter AND Daughter # Son BUT Son !# Son proves that # is not transitive. And you've already shown that it's not reflexive. Is it symmetric?

To show that a property does hold, you need to show this for every combination of variables. To show that ~ is symmetric, you need to show that for every combination of values of x and y, IF x ~ y THEN y ~ x. So far, you've only looked at one particular instance: x = Son, y = Daughter. To show that ~ is transitive, you need to show that for every combination of values of x, y, and z, IF x ~ y AND y ~ z THEN x ~ z. Again, so far, you've only looked at one particular instance: x = z = Son, y = Daughter.[/QUOTE]

Well since son~daughter is reversible and then still true I would think yes. The relation of sibling is a reversible relation so in this case = reverses to = not to [TEX]\ne[/TEX] and hence both sides hold so it is confirmed.

axn 2011-01-21 16:27

[QUOTE=xilman;247895]Your analysis is correct, given your definition of "sibling".[/QUOTE]

[QUOTE=science_man_88;247893]2) in my definition of sibling it can roughly be defined as having at least one parent in common(at home or biologically)[/QUOTE]

His analysis is correct, insofar as the set is a very small one lacking any counterexamples. However, if we start with a more realistic set, by his definition, the relation is not transitive (think of step siblings sharing a half sibling).

Mr. P-1 2011-01-21 16:28

[QUOTE=science_man_88;247939]Well since son~daughter is reversible and then still true I would think yes. The relation of sibling is a reversible relation so in this case = reverses to = not to [TEX]\ne[/TEX] and hence both sides hold so it is confirmed.[/QUOTE]

You're still not expressing yourself clearly.

One way to do show what you need to show would be by brute force: list every single combination of x and y, or x, y, and z, and verify that the conditions hold.

That's only practical in this case because the underlying set S is so small. Here's a smarter way:

Proposition: ~ is symmetric.

Proof: we need to show that x ~ y IMPLIES y ~ x. Consider the case where x = y. Then we can substitute x for y in that statement:

x ~ x IMPLIES x ~ x

which is trivially true. Now consider the case where x != y. There are just two cases where this is true: Son ~ Daughter and Daughter ~ Son, and each implies the other is a true statement.

Proposition: ~ is transitive.

Proof: we need to show that x ~ y AND y ~ z IMPLIES x ~ z. Consider the case where x = y. Substituting, we get

x ~ x AND x ~ z IMPLIES x ~ z

which is trivially true. Can you complete this proof? (Hint: what other cases do you need to consider?)

science_man_88 2011-01-21 16:48

[QUOTE=Mr. P-1;247942]You're still not expressing yourself clearly.

One way to do show what you need to show would be by brute force: list every single combination of x and y, or x, y, and z, and verify that the conditions hold.

That's only practical in this case because the underlying set S is so small. Here's a smarter way:

Proposition: ~ is symmetric.

Proof: we need to show that x ~ y IMPLIES y ~ x. Consider the case where x = y. Then we can substitute x for y in that statement:

x ~ x IMPLIES x ~ x

which is trivially true. Now consider the case where x != y. There are just two cases where this is true: Son ~ Daughter and Daughter ~ Son, and each implies the other is a true statement.

Proposition: ~ is transitive.

Proof: we need to show that x ~ y AND y ~ z IMPLIES x ~ z. Consider the case where x = y. Substituting, we get

x ~ x AND x ~ z IMPLIES x ~ z

which is trivially true. Can you complete this proof? (Hint: what other cases do you need to consider?)[/QUOTE]

Proposition: ~ is reflexive

Proof: we need to show that x~x. I based my statement on :

if x "is a child of" y and x "is a child of" y implies x "is a sibling of"x but I know this isn't acceptable.

CRGreathouse 2011-01-21 16:57

sm, I think P-1 was asking for you to finish the proof of transitivity, not to prove reflexivity.

science_man_88 2011-01-21 17:13

[QUOTE=CRGreathouse;247955]sm, I think P-1 was asking for you to finish the proof of transitivity, not to prove reflexivity.[/QUOTE]

Well then, now considering the case x!=y

we get:

x~y and y~z implies x~z ? If not then no I can't complete the proof.

Mr. P-1 2011-01-21 18:01

[QUOTE=CRGreathouse;247955]sm, I think P-1 was asking for you to finish the proof of transitivity, not to prove reflexivity.[/QUOTE]

Yes, I only gave a partial proof. Sorry I wasn't clear.

Mr. P-1 2011-01-21 18:06

[QUOTE=science_man_88;247961]Well then, now considering the case x!=y[/QUOTE]

Instead of x!=y, try setting some other combination of two variables equal.

BTW, do you understand why

x ~ x AND x ~ z IMPLIES x ~ z

is trivially true?

science_man_88 2011-01-21 18:18

[QUOTE=Mr. P-1;247971]Instead of x!=y, try setting some other combination of two variables equal.

BTW, do you understand why

x ~ x AND x ~ z IMPLIES x ~ z

is trivially true?[/QUOTE]

because x~x is trivially true by my definition of ~ and x~z implies x~z is also trivially trues hence the whole thing is trivially true ?


All times are UTC. The time now is 21:52.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.