Set theory: Is my proof valid?

  • Thread starter r0bHadz
  • Start date
  • #1
194
17

Homework Statement


Prove the following for a given universe U

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

Homework Equations




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) ≠ ∅
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,570
1,465
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.
 
  • Like
Likes FactChecker
  • #3
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,874
1,448
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##.
 
  • Like
Likes FactChecker and PeroK
  • #4
600
393
The law of excluded middle is healthy to know. For every subset [itex]A\subseteq U[/itex], where [itex]U[/itex] is some fixed universe and for every [itex]x\in U[/itex] it holds that [itex]x\in A[/itex] or [itex]x\notin A[/itex] (i.e [itex]x\in A^c[/itex]). The result is immediate due to
[tex]
X\lor Y \equiv \neg X\Rightarrow Y .
[/tex]
Alternatively one may prove by contradiction. For instance, prove the forward direction. Assume [itex]A\subseteq B[/itex] holds. Formally
[tex]
\forall x\in U, x\in A\Rightarrow x\in B.
[/tex]
Now, assume for a contradiction [itex]A\cap B^c\neq \emptyset[/itex]. Formally
[tex]
\exists x\in U, x\in A\land x\notin B.
[/tex]
This is impossible since we assumed for every [itex]x\in U[/itex] the implication [itex]x\in A\Rightarrow x\in B[/itex] is true. So we have a contradiction, which we obtained by assuming [itex]A\cap B^c\neq\emptyset[/itex]. This assumption must be false.
 
Last edited:
  • #5
epenguin
Homework Helper
Gold Member
3,825
855

Homework Statement


Prove the following for a given universe U

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

Homework Equations




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.
 

Related Threads on Set theory: Is my proof valid?

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
10
Views
1K
Replies
11
Views
1K
  • Last Post
Replies
4
Views
692
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
10
Views
904
Replies
7
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
5
Views
2K
Top