# Set theory: Is my proof valid?

## Homework Statement

Prove the following for a given universe U

A⊆B if and only if A∩(B compliment) = ∅

## The Attempt at a Solution

Assume A,B, (B compliment) are not ∅
if A∩(B compliment) = ∅, x∈A ∨ x∈ (B compliment), but not both

If x∈A ∧ x∉(B compliment), then x∈B , because if they are in the same U and A∩(B compliment) = ∅ then A∩B must have a common element.

Also A⊆B because if A was outside of B, then A∩(B compliment) ≠ ∅

Stephen Tashi
Your proof is not valid by the standards of a typical course in set theory. For example, you are using intuitive language such as "if A was outside of B" that has no formal definition.

You are not being specific about quantifiers. For example:

if A∩(B compliment) = ∅, x∈A ∨ x∈ (B compliment), but not both

You fail to quantify the variable "x". What you apparently mean is:

If ##A \cap B^c = \emptyset## then ##\forall x ( ( x \in A \lor x \in B^c) \land \lnot( x \in A \land x \in B^c))##.

You also fail to give a reason why that statement should be true. Apparently, you are relying on an intuitive picture of the situation. In elementary courses an intuitive argument may be acceptable.

FactChecker
vela
Staff Emeritus
Homework Helper
You mean "complement," not "compliment."

Assume A,B, (B compliment) are not ∅
I'm not sure why you need this assumption.

if A∩(B compliment) = ∅, x∈A ∨ x∈ (B compliment), but not both
That's not necessarily true. x could be in neither A nor ##B^c##.

You need to prove two things.
1. If ##A \subset B##, then ##A \cap B^c = \emptyset##.
2. If ##A \cap B^c = \emptyset##, then ##A \subset B##.
For #2, for example, you would assume ##A \cap B^c = \emptyset##, then start with ##x \in A## and show that it logically leads to ##x \in B##.

FactChecker and PeroK
The law of excluded middle is healthy to know. For every subset $A\subseteq U$, where $U$ is some fixed universe and for every $x\in U$ it holds that $x\in A$ or $x\notin A$ (i.e $x\in A^c$). The result is immediate due to
$$X\lor Y \equiv \neg X\Rightarrow Y .$$
Alternatively one may prove by contradiction. For instance, prove the forward direction. Assume $A\subseteq B$ holds. Formally
$$\forall x\in U, x\in A\Rightarrow x\in B.$$
Now, assume for a contradiction $A\cap B^c\neq \emptyset$. Formally
$$\exists x\in U, x\in A\land x\notin B.$$
This is impossible since we assumed for every $x\in U$ the implication $x\in A\Rightarrow x\in B$ is true. So we have a contradiction, which we obtained by assuming $A\cap B^c\neq\emptyset$. This assumption must be false.

Last edited:
epenguin
Homework Helper
Gold Member

## Homework Statement

Prove the following for a given universe U

A⊆B if and only if A∩(B compliment) = ∅

## The Attempt at a Solution

Assume A,B, (B compliment) are not ∅
if A∩(B compliment) = ∅, x∈A ∨ x∈ (B compliment), but not both

If x∈A ∧ x∉(B compliment), then x∈B , because if they are in the same U and A∩(B compliment) = ∅ then A∩B must have a common element.

Also A⊆B because if A was outside of B, then A∩(B compliment) ≠ ∅

Learn on this occasion that the word is "complement".
It is related to the word complete.
Or think of a ship's complement - the number that needs to be made up to create a properly working crew.

Compliment is "a polite expression of praise or admiration".
Nothing logical – they both have the exact same Latin root, and originally even the same spelling in English - idea is a plain statement, answer, greeting, etc will often be regarded as by itself insufficient, needing to be complemented by a compliment.