- #1
pandaBee
- 23
- 0
Homework Statement
Suppose R is a relation on A, and define a relation S on P (A) as follows:
S = {(X, Y ) ∈ P (A) × P (A) | ∀x ∈ X∃y ∈ Y (xRy)}.
For each part, give either a proof or a counterexample to justify your
answer.
(a) If R is reflexive, must S be reflexive?
(b) If R is symmetric, must S be symmetric?
(c) if R is transitive, must S be transitive?
Homework Equations
P(A) = power set of A
Uppercase letters = sets
Lowercase = element(s) of the sets
The Attempt at a Solution
For parts a and b, and possibly c, the relation S is undefined when I take one of the X, Y to be the empty set, since there are no x,y in X,Y when X or Y are the empty set xRy is undefined.
a)Assume R is reflexive.
Want to prove ∀X∈P(A)((X,X)∈S)
Let x be an arbitrary element of P(A)
then x is an arbitrary subset of A;
take A to be the empty set, but then the empty set has no elements therefore the requirement ∀x ∈ X∃y ∈ Y (xRy) for (X,X) to be an element of S is invalid, that is undefined.
I get the same result for part b, and I'm assuming it's the same way for c) as well. Did this question mean to exclude the empty set as a possibility for the domain of S? Or am I possibly under some misconception.