# Somewhat difficult proof of a transitive relation

1. Aug 10, 2011

### Syrus

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. Aug 10, 2011

### jbunniii

Suppose $(a,b)\in R$ and $(b,c) \in R$. You want to show that $(a,c) \in R$.

Choose any $X \subseteq A \setminus \{a,c\}$. Then neither $a$ nor $c$ is in $X$.

It may or may not be true that $b \in X$.

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

What happens if $b \in X$?

3. Aug 10, 2011

### Syrus

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.

4. Aug 10, 2011

### jbunniii

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

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

If $b \not\in X$, then $X \subseteq A \setminus\{a,b\}$ and $X \subseteq A \setminus\{b,c\}$.

Now suppose that $X \cup\{a\} \in F$.

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

What can you conclude from this?

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

So now you need to come up with an argument that works if $b \in X$.

Last edited: Aug 10, 2011
5. Aug 10, 2011

### Syrus

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?

6. Aug 10, 2011

### jbunniii

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

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

I think you can make a similar argument if $b \in X$, but in that case you can't use $X$ itself to draw the conclusions.

7. Aug 10, 2011

### Syrus

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.

8. Aug 10, 2011

### jbunniii

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

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

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

When I consider the other possibility, $b \in X$, then $X \not \subseteq A \setminus \{a,b\}$ 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 $b \in X$ case, which I haven't worked out myself yet.

9. Aug 10, 2011

### Syrus

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.

10. Aug 10, 2011

### Syrus

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
11. Aug 10, 2011

### jbunniii

No, this can't be right. Right at the start, you said that $b \in X$. But the last sentence (in bold) cannot be true in that case. $b$ is obviously not in $A\setminus \{a,b\}$, so $X$ cannot be a subset of $A\setminus \{a,b\}$.

12. Aug 10, 2011

### jbunniii

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

Suppose $b \not \in X$. Since $X \subseteq A \setminus\{a, c\}$, we also see that $a \not \in X$. Therefore $X$ is a subset of $A$ which contains neither $a$ nor $b$, and therefore $X \subseteq A \setminus \{a,b\}$.

13. Aug 11, 2011

### Syrus

Anyone else have any suggestions?

14. Aug 11, 2011

### wisvuze

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 }.

15. Aug 11, 2011

### Syrus

What exactly do you mean by this? X u { a } ∈ F is a premise, so it is assumed to be satisfied/true.

16. Aug 11, 2011

### Syrus

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
17. Aug 11, 2011

### Syrus

Still looking for help.

18. Aug 11, 2011

### wisvuze

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 )

19. Aug 11, 2011

### Syrus

Maybe you can do more than indicate how "obvious" it is?

Last edited: Aug 11, 2011
20. Aug 11, 2011

### stringy

Suppose $X \subseteq A - \left\{a,c\right\}$ and $X \cup \left\{a\right\} \in F$.

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

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

Then, take a look at the set $( X \cup \left\{c\right\}) - \left\{b\right\}$ remembering that $(a,b)\in R$.