4
$\begingroup$

I have been working on this problem from Velleman's How to prove book:

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

Now, I have been solving the proof like this:

Let $a, b, c$ be arbitrary elements of A such that $(a,b) \in R$ and $(b,c) \in R$. Suppose $F \subseteq P(A)$. Let $X$ be arbitrary set. Suppose $X \subseteq A \setminus \{a,c\}$ and $X \cup \{a\} \in F$, we have to prove that $X \cup \{c\} \in F$. From $X \subseteq A \setminus \{a,c\}$, it follows that $a,c \notin X$. We can consider two cases:

1) $b \notin X$. This is straightforward to prove.

2) $b \in X$

Now the second part confuses me. How to proceed the second part ?

$\endgroup$

3 Answers 3

1
$\begingroup$

Frankly,your proof confuses ME. To prove R is transitive, you have to show if $(a,b) \in R$ and $(b,c)\in R$, then $(a,c)\in R$. Consider what it means for $(a,b),(b,c)\in R$. If $(a,b) \in R$, then for every $X\subseteq$ $A\backslash{\{a,b\}}$ then $A\cup{\{a\}}$ $\in F\subset P(A)$ $\rightarrow$ $A\cup {\{b\}}\in F\subset P(A)$. Similarly, if $(b,c) \in R$, then for every $Y\subseteq$ $A\backslash {\{b,c\}}$, then $A\cup {\{b\}}\in F$ $\subset P(A)$ $\rightarrow$ $A\cup {\{c\}}\in F\subset P(A)$. Therefore, considering $X \cup Y$ $\subseteq$ $A\backslash{\{a,b\}}$ $\cup$ $A\backslash{\{b,c\}}$ = $A\backslash {\{a},{b},{c}\}$. This implies $A\cup{\{a\}}$ $\in F\subset P(A)$ $\rightarrow$ $A\cup {\{b\}}\in F\subset P(A)$ $\rightarrow A\cup {\{c\}}\in F$ $\subset$ P(A).But that means $(a,c)\in R$ and thus R is transitive. Q.E.D.

Comment: This looks ok to me,but I'm not 100 percent convinced,frankly. I'm going to look it over a few more times. Feel free to comment. Something looks off about it, but I can't see what it is.

$\endgroup$
0
$\begingroup$

Hint: Consider $Y=X\backslash{\{b\}}$.

$\endgroup$
0
$\begingroup$

The definition of $R$ can be reworded slightly. Let $$R = \big\{(a,b)\in A\times A \big|\forall X\in F, a\in X \implies(X\backslash\{a\})\cup\{b\}\in F\big\}$$ Show that this is equivalent to your original definition of $R$.

$\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.