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: Proof with sets and elements. Am I going about this right?

  1. Oct 20, 2015 #1
    1. The problem statement, all variables and given/known data
    Give an element-wise proof for the following: If A⊆B and B⊆C', then A ∩ C = ∅

    2. Relevant equations
    A is a subset of B (written A ⊆ B) if every element in the set A is also an element in the set B. Formally, this means that fore every x, if x ∈ A, then x ∈ B.
    A ∩ B = { x ∈ U : x ∈ A and x ∈ B }.
    A set that contains no elements is called an empty set, and is denoted by { } or ∅.
    A is equal to B (simply written A = B) means that A and B have exactly the same members. This is expressed formally by saying, “A ⊆ B and B ⊆ A.”

    3. The attempt at a solution
    Because there is an equal sign in the "then" statement, I know I have to show two case if each side being a subset of the other. So here is what I have so far...

    Let U be the universe that contain the sets A, B, and C. Let A and B be subsets of U such that A ⊆ B and let B and C' be subsets such that B ⊆ C'.

    Case 1:
    We will show that A ∩ C = ∅. Let x ∈ A ∩ C. Then x∈U, x∈A, and x∈C. Since x∈A, it follows that x∈B by our hypothesis. Also by our hypothesis, since x∈B, x∈C'. Since x∈C, and x∈C', ....

    and this is where I'm getting lost. How do I go proving from here its the empty set? At this point isn't this saying that x is every element? Or am I thinking about this totally wrong?
  2. jcsd
  3. Oct 20, 2015 #2
    What you have is [itex]A\subseteq B \land B\subseteq C'[/itex], assuming [itex]X'[/itex] means complement of set [itex]X[/itex]. You have shown that [itex]..x\in C\land x\in C'...[/itex], by definition of complement, such a situation can never occur, therefore ...? You can convert your initial formula to something that only consists of conjuctions. If there is an identically false "sub-conjunction", then the entire conjunction is identically false.
    If you haven't learnt discrete math, yet, disregard what I said about converting things.

    You have the right idea, a matter of analyzing the information you have gathered.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted