Is This Natural Language Proof of a Set Theory Proposition Correct?

[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.