Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Somewhat difficult proof of a transitive relation

  1. Aug 10, 2011 #1
    1. The problem statement, all variables and given/known data

    Suppose A is a set and F ⊆ P(A). Let R = {(a,b) ∈ A x A | for every X ⊆ A\{a,b}, if X∪{a} ∈ F, then X∪{b} ∈ F}. Show that R is transitive.

    * P(A) is the powerset of A.


    2. Relevant equations

    I am looking for an informal, "naive" proof- the text this exercise comes from is not axiomatic one.


    3. The attempt at a solution

    So far I have come up with:

    Let a,b,c ∈ A and suppose (a,b) ∈ R and (b,c) ∈ R. Let X ⊆ A\{a,c} and also assume X∪{a} ∈ F. But then X∪{a} ∈ P(A), which in turn means X∪{a} ⊆ A.



    *I am struggling with a way to show X∪{c} ∈ F, which is (at least what seems to me to be) what is required to prove (a,c) ∈ R.
     
    Last edited: Aug 10, 2011
  2. jcsd
  3. Aug 10, 2011 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Suppose [itex](a,b)\in R[/itex] and [itex](b,c) \in R[/itex]. You want to show that [itex](a,c) \in R[/itex].

    Choose any [itex]X \subseteq A \setminus \{a,c\}[/itex]. Then neither [itex]a[/itex] nor [itex]c[/itex] is in [itex]X[/itex].

    It may or may not be true that [itex]b \in X[/itex].

    If [itex]b \not\in X[/itex], then [itex]X \subseteq A \setminus \{a,b\}[/itex] and [itex]X \subseteq A \setminus \{b,c\}[/itex] and the rest is straightforward.

    What happens if [itex]b \in X[/itex]?
     
  4. Aug 10, 2011 #3
    The reasoning for the case (presented above) in which b is not an element of X seems to use the vacuous truth which results by writing out the meaning of subset and applying the fact that b is not an element of X to the statements implied by (a,b) ∈ R and (b,c) ∈ R.

    If b ∈ X, then b ∈ A and not b ∈ {a,c}....Perhaps I have been looking at this problem for too long, but i cannot seem to apply this anywhere.
     
  5. Aug 10, 2011 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'm not sure what you mean by vacuous truth.

    Let [itex]X[/itex] be as I indicated above, and suppose that [itex](a,b) \in R[/itex] and [itex](b,c) \in R[/itex]. We want to prove that [itex](a,c) \in R[/itex].

    If [itex]b \not\in X[/itex], then [itex]X \subseteq A \setminus\{a,b\}[/itex] and [itex]X \subseteq A \setminus\{b,c\}[/itex].

    Now suppose that [itex]X \cup\{a\} \in F[/itex].

    Since [itex](a,b) \in R[/itex], it follows that [itex]X \cup\{b\} \in F[/itex]. Then, since [itex](b,c) \in R[/itex], it follows that [itex]X \cup\{c\} \in F[/itex].

    What can you conclude from this?

    The reason why [itex]b \not\in X[/itex] is important is because this means that [itex]X[/itex] is a valid "test set" in the definition of [itex]R[/itex] for both [itex](a,b)[/itex] and [itex](b,c)[/itex].

    So now you need to come up with an argument that works if [itex]b \in X[/itex].
     
    Last edited: Aug 10, 2011
  6. Aug 10, 2011 #5
    What i was referring to was this:

    We assumed b ∉ X. We also assumed (a,b),(b,c) ∈ R. The logical definition of this, in particular for (a,b) ∈ R, is (∀X ⊆ A\{a,b})(X∪{a} ∈ F → X∪{b} ∈ F). It is analogous for (b,c) ∈ R. The definition of subset is (∀k)(k ∈ X → k ∈ A\{a,b}). Lastly, we have assumed X ⊆ A\{a,c}. By vacuous truth I am referring to the justification that X ⊆ A\{a,b}, which allows us to use (a,b) ∈ R given these premises- unless I am still making an error or regarding the proof in an unneccesary manner?
     
  7. Aug 10, 2011 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    All the statements you made are correct. I guess I was confused by your use of the word "vacuous."

    The assumption that [itex]b \not\in X[/itex] means that the rest of the argument is valid, in particular, [itex]X[/itex] meets the criteria needed to draw a useful conclusion from the facts that [itex](a,b) \in R[/itex] and [itex](b,c) \in R[/itex].

    I think you can make a similar argument if [itex]b \in X[/itex], but in that case you can't use [itex]X[/itex] itself to draw the conclusions.
     
  8. Aug 10, 2011 #7
    This is a bit sidetracked, but I'd just like to ascertain that I'm using the term "vacuous" correctly... since the antecedent in the definition of subset above isn't satisfied (since we have b ∉ X for arbitrary b and that definition has k ∈ X for arbitrary k), doesn't that make X ⊆ A\{a,b} vacuously true? Or was it simply the phrasing which was confusing in my previous post?

    Also, thank you for your help jbunniii. I'll post a full copy of my proof once I have it done on paper.
     
  9. Aug 10, 2011 #8

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    But [itex]b[/itex] isn't arbitrary. It's a specific element, which along with two other specific elements [itex]a[/itex] and [itex]c[/itex], are assumed to satisfy [itex](a,b) \in R[/itex] and [itex](b,c) \in R[/itex].

    The two cases I am then considering are whether or not that specific [itex]b[/itex] is in the candidate set [itex]X[/itex] that I defined above. Depending on how I choose [itex]X[/itex], this may or may not be true. There are valid choices of [itex]X[/itex] with [itex]b \in X[/itex], and other valid choices of [itex]X[/itex] with [itex]b \not\in X[/itex]. I must show that the desired result is true for all valid choices.

    I consider the two possibilities separately. If [itex]b \not \in X[/itex], then that implies that [itex]X \subseteq A \setminus \{a,b\}[/itex]. It's not vacuously true. It's true precisely because [itex]b \in X[/itex].

    When I consider the other possibility, [itex]b \in X[/itex], then [itex]X \not \subseteq A \setminus \{a,b\}[/itex] and this introduces a complication that needs to be overcome.

    Sorry in advance if I'm not addressing your question correctly. It might just be a question of language. To me, "vacuously true" would be a statement like "if pigs can fly, then all cats are blue." Whereas the example above is more like "if 3 is in the set X, then X cannot consist only of even numbers." Hope that makes sense.

    In any case, I look forward to seeing your proof, especially the [itex]b \in X[/itex] case, which I haven't worked out myself yet.
     
  10. Aug 10, 2011 #9
    hmmmmm. There's a hint which suggests working with the sets (XU{a})\{b} and (XU{c})\{b} for this case. Trying to work off that here. Also the fact that F is a subset of P(A) must play in somewhere.
     
  11. Aug 10, 2011 #10
    How about this?


    Let a,b,c ∈ A and suppose (a,b),(b,c) ∈ R. Also, let X ⊆ A\{a,c} and assume X∪{a} ∈ F. The proof is now broken into two exhaustive cases:

    Case 1) Suppose b ∉ X. In order for X ⊆ A\{a,b} to be satisfied, it must be true that (∀k)(k ∈ X → k ∈ A\{a,b}). Now, applying the element b introduced above to this statement we have: b ∈ X → b ∈ A\{a,b}, which is logically equivalent to b ∉ X ∨ b ∈ A\{a,b}. This disjunction is clearly true since, by hypothesis, b ∉ X. As a result, we may assume X ⊆ A\{a,b}. Analogous reasoning also provides us with X ⊆ A\{b,c}. Using these conclusions, along with X∪{a} ∈ F above, we may deduce X∪{b} ∈ F (from (a,b) ∈ R) and ultimately X∪{c} ∈ F (from (b,c) ∈ R). Thus, R is transitive.

    Case 2) Suppose b ∈ X. In addition, assume a ∈ X. But this would imply a ∈ A and a ∉ {a,c} (since X ⊆ A\{a,c}) which is a contradiction since, obviously, a ∈ {a,c}. Thus a ∉ X. Now recall that in order for X ⊆ A\{a,b} to be satisfied, it must be true that (∀k)(k ∈ X → k ∈ A\{a,b}). Since any implication is logically equivalent to its contrapositive, we have (∀k)(k ∉ A\{a,b} → k∉ X). Analyzing the logical definition of this statement even more yields: (∀k)((k ∉ A ∨ k ∈ {a,b}) → k∉ X). Further, this implication is equivalent to the following disjunction: (∀k)((k ∈ A ∧ k ∉ {a,b}) ∨ k∉ X). Applying a to this statement, it immediately becomes obvious that it is true because, as demonstrated above, a ∉ X. This shows that X ⊆ A\{a,b}. An analogous argument shows that X ⊆ A\{b,c} is valid. Afterwards, following the reasoning in case 1, it can be seen that R is transitive.



    Q.E.D.
     
    Last edited: Aug 10, 2011
  12. Aug 10, 2011 #11

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, this can't be right. Right at the start, you said that [itex]b \in X[/itex]. But the last sentence (in bold) cannot be true in that case. [itex]b[/itex] is obviously not in [itex]A\setminus \{a,b\}[/itex], so [itex]X[/itex] cannot be a subset of [itex]A\setminus \{a,b\}[/itex].
     
  13. Aug 10, 2011 #12

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This case is correct, but I think you are making it too hard. Why not just say this instead of the bolded text:

    Suppose [itex]b \not \in X[/itex]. Since [itex]X \subseteq A \setminus\{a, c\}[/itex], we also see that [itex]a \not \in X[/itex]. Therefore [itex]X[/itex] is a subset of [itex]A[/itex] which contains neither [itex]a[/itex] nor [itex]b[/itex], and therefore [itex]X \subseteq A \setminus \{a,b\}[/itex].
     
  14. Aug 11, 2011 #13
    Anyone else have any suggestions?
     
  15. Aug 11, 2011 #14
    Yes, this will lead to the solution. When you assume X contained in S \ {a,c} satisfies X u { a }, assuming that b is also in X ( the second case, after assuming b is not in X ), gives rise to X u { a } \ { b } being contained in S \ { b , c }.
     
  16. Aug 11, 2011 #15
    What exactly do you mean by this? X u { a } ∈ F is a premise, so it is assumed to be satisfied/true.
     
  17. Aug 11, 2011 #16
    When you assume b ∈ X... there is no way to deduce X is contained in A/{a,b}. Clearly, the same holds for A/{b,c}. This leads me to believe XU{c} ∈ F must be shown directly (ie. not using Modus Ponens with the givens).

    So far I have, since b ∈ XU{a} and XU{a} ∈ F, b ∈ UF... trying to get through like this
     
    Last edited: Aug 11, 2011
  18. Aug 11, 2011 #17
    Still looking for help.
     
  19. Aug 11, 2011 #18
    yes, that is what I mean. I suggest you read more into that hint you were given, the one I followed up on. It is almost a give-away ( as long as you pay attention to all the notation )
     
  20. Aug 11, 2011 #19
    Maybe you can do more than indicate how "obvious" it is?
     
    Last edited: Aug 11, 2011
  21. Aug 11, 2011 #20
    Suppose [itex] X \subseteq A - \left\{a,c\right\}[/itex] and [itex] X \cup \left\{a\right\} \in F[/itex].

    Assume [itex] b \in X[/itex]. Then [itex] ( X \cup \left\{a\right\}) - \left\{b\right\} \subseteq A - \left\{b,c\right\}[/itex]. Also, [itex] ( X \cup \left\{a\right\}) - \left\{b\right\} \cup \left\{ b\right\} = X \cup \left\{a\right\} \in F[/itex].

    Therefore, since [itex](b,c) \in R[/itex], we know that [itex] (X\cup \left\{a\right\}) - \left\{b\right\} \cup \left\{c\right\} \in F[/itex]. Remember this inclusion.

    Then, take a look at the set [itex] ( X \cup \left\{c\right\}) - \left\{b\right\}[/itex] remembering that [itex] (a,b)\in R[/itex].
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook