1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Relations, power sets and the empty/null set.

  1. Sep 5, 2014 #1
    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
    (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. jcsd
  3. Sep 6, 2014 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted