# Relations, power sets and the empty/null set.

1. Sep 5, 2014

### pandaBee

1. The problem statement, all variables and given/known data

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?

2. Relevant equations

P(A) = power set of A
Uppercase letters = sets
Lowercase = element(s) of the sets

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

2. Sep 6, 2014

### Fredrik

Staff Emeritus
A statement like "for all x in E, x has property P" (i.e. $\forall x\in E~P(x)$) is true when $E=\varnothing$, regardless of what P is. To say that it's false is to say that there's an x in E that doesn't have property P. So the statement isn't false, and must therefore be true.

This is probably less confusing if we recall that the statement $\forall x\in E~P(x)$ is actually an abbreviation for
$$\forall x\ \big(x\in E\ \Rightarrow\ P(x)\big)$$ If E is empty, the implication is clearly true for all x.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted