Elementary Set Theory Proof

[WisheDeom]

Hello,

I am teaching myself Set Theory, and in doing some exercises I came across the problem:

Given sets A and B, prove that $A \subseteq B$ if and only if $A \cap B = A$.

My proof, in natural language, is in two parts:

1) Prove that if $A \subseteq B$, $A \cap B = A$.

By the definition of subsets, all elements $x \in A$ are also $x \in B$. By definition, $A \cap B = \left\{x: x \in A \wedge x \in B \right\}$. Since all elements of A are also elements of B, but not all elements of B are necessarily elements of A, the intersection fo the two is A.

2) Prove that if $A \cap B \neq A$, it is not true that $A \subseteq B$.

If the intersection of A and B is not A, then there are necessarily elements of A that are not elements of B, therefore A is not a subset of B.

Therefore, $A \subseteq B$ if and only if $A \cap B = A$. Q.E.D.

Is this a sufficient proof?

If it is, could someone help me translate it into the language of formal language?

Edit: Fixed wrong logical connective, set notation.

 

[micromass]

Hi WisheDeom!

Hello,

I am teaching myself Set Theory, and in doing some exercises I came across the problem:

Given sets A and B, prove that $A \subset B$ if and only if $A \cap B = A$.

My proof, in natural language, is in two parts:

1) Prove that if $A \subset B$, $A \cap B = A$.

By the definition of subsets, all elements $x \in A$ are also $x \in B$. By definition, $A \cap B = {x: x \in A \vee x \in B}$.

Here you probably mean $\wedge$ and not $\vee$.

Since all elements of A are also elements of B, but not all elements of B are necessarily elements of A, the intersection fo the two is A.

This only proves that $A\subseteq A\cap B$? What about the other inclusion?

2) Prove that if $A \cap B \neq A$, it is not true that $A \subset B$. If the intersection of A and B is not A, then there are necessarily elements of A that are not elements of B, therefore A is not a subset of B.

You again use that $A\cap B\subseteq A$, you may want to prove this.

Therefore, $A \subset B$ if and only if $A \cap B = A$. Q.E.D.

Is this a sufficient proof?

The proof looks good except for the remarks I posted.

If it is, could someone help me translate it into the language of formal language?

I like the style of the proof. What do you mean with "formal language"? You mean with symbols like $\Rightarrow,~\forall,~\wedge$ and stuff?

 

[pmsrw3]

Given sets A and B, prove that $A \subset B$ if and only if $A \cap B = A$.

Unless I'm missing something, this theorem isn't true. It's almost true, but consider the case where A = B.

 

[evagelos]

Unless I'm missing something, this theorem isn't true. It's almost true, but consider the case where A = B.

The theorem is true even in the case where A=B

 

[WisheDeom]

Thank you for the responses.

Here you probably mean $\wedge$ and not $\vee$.

Yes, of course.

This only proves that $A\subseteq A\cap B$? What about the other inclusion?

This is what I was trying to do in the second part, but see below.

You again use that $A\cap B\subseteq A$, you may want to prove this.

Would you be able to go into a little more detail? I know this is very basic, but I am just starting.

I like the style of the proof. What do you mean with "formal language"? You mean with symbols like $\Rightarrow,~\forall,~\wedge$ and stuff?

Yeah, that's what I meant. I guess my approach in learning the subject is a bit of a mix of "naive" and "axiomatic" set theory.

Unless I'm missing something, this theorem isn't true. It's almost true, but consider the case where A = B.

The theorem is true even in the case where A=B

Yes, of course, I should have written "a subset of or equal to". I fixed the notation in the OP.

 

[micromass]

Would you be able to go into a little more detail? I know this is very basic, but I am just starting.

You say

If the intersection of A and B is not A, then there are necessarily elements of A that are not elements of B,

But the only thing I can infer from the statement "If the intersection of A and B is not A" is that there either is an element in A but not in $A\cap B$ or there is an element in $A\cap B$, but not in A. One of these possibilities cannot happen, namely that there is an element in $A\cap B$ but not in A. But for that you need to show first that $A\cap B\subseteq A$

 

[WisheDeom]

But the only thing I can infer from the statement "If the intersection of A and B is not A" is that there either is an element in A but not in $A\cap B$ or there is an element in $A\cap B$, but not in A. One of these possibilities cannot happen, namely that there is an element in $A\cap B$ but not in A. But for that you need to show first that $A\cap B\subseteq A$

Ah! I understand now.

So by definition $A \cap B = \left\{x:x \in A \wedge x \in B }$ and $C \subseteq A \leftrightarrow \forall x (x \in C \rightarrow x \in A)$. Since the intersection of A and B contains elements from A but no elements not in A, $(A \cap B) \subseteq A$.

Is this valid? Does it complete the proof?

Thanks for your patience, by the way.

 

[micromass]

Ah! I understand now.

So by definition $A \cap B = \left\{x:x \in A \wedge x \in B }$ and $C \subseteq A \leftrightarrow \forall x (x \in C \rightarrow x \in A)$. Since the intersection of A and B contains elements from A but no elements not in A, $(A \cap B) \subseteq A$.

Is this valid? Does it complete the proof?

Thanks for your patience, by the way.

Yes, this is ok

 

[praeclarum]

Hello,

I am teaching myself Set Theory, and in doing some exercises I came across the problem:

Given sets A and B, prove that $A \subseteq B$ if and only if $A \cap B = A$.

My proof, in natural language, is in two parts:

1) Prove that if $A \subseteq B$, $A \cap B = A$.

By the definition of subsets, all elements $x \in A$ are also $x \in B$. By definition, $A \cap B = \left\{x: x \in A \wedge x \in B \right\}$. Since all elements of A are also elements of B, but not all elements of B are necessarily elements of A, the intersection fo the two is A.

2) Prove that if $A \cap B \neq A$, it is not true that $A \subseteq B$.

If the intersection of A and B is not A, then there are necessarily elements of A that are not elements of B, therefore A is not a subset of B.

Therefore, $A \subseteq B$ if and only if $A \cap B = A$. Q.E.D.

Is this a sufficient proof?

If it is, could someone help me translate it into the language of formal language?

Edit: Fixed wrong logical connective, set notation.

Here is the formalization (ignoring tex):
Key:
A. for $\forall$
-> for $\rightarrow$
e. for $\in$
i^i for $\cap$
C_ for $\subseteq$

1 A C_ B <-> A. x ( x e. A -> x e. B )
2 ( A i^i B ) = A <-> A. x ( ( x e. A /\ x e. B ) <-> x e. A )
3 ( A C_ B <-> ( A i^i B ) = A ) <-> ( A. x ( x e. A -> x e. B ) <-> A. x ( ( x e. A /\ x e. B ) <-> x e. A ) ) ) (By 1 and 2)
4 ( ( x e. A /\ x e. B ) -> x e. A ) [case of a and b -> a]
5 ( x e. A -> x e. B ) -> ( x e. A -> ( x e. A /\ x e. B ) )
6 ( x e. A -> x e. B ) -> ( ( x e. A /\ x e. B ) <-> x e. A ) (By 4 and 5)
7 ( ( x e. A /\ x e. B ) <-> x e. A ) -> ( x e. A -> ( x e. A /\ x e. B ) )
8 ( x e. A -> ( x e. A /\ x e. B ) ) -> ( x e. A -> x e. B )
9 ( ( x e. A /\ x e. B ) <-> x e. A ) -> ( x e. A -> x e. B ) ( by 7 and 8)
10 ( x e. A -> x e. B ) <-> ( ( x e. A /\ x e. B ) <-> x e. A ) ( by 6 and 9)
11 A. x ( x e. A -> x e. B ) <-> A. x ( ( x e. A /\ x e. B ) <-> x e. A ) (by 10)
12 A C_ B <-> ( A i^i B ) = A (by 11 and 3)

Too much detail, but it is very spelled out.