# Thread: Logic & Propositions & Proofs

1. ## Logic & Propositions & Proofs

Hi, can anyone help me show how to prove this. I know it is common sense, but I don't know how to express on paper how to prove it.

A∩∅=∅

Thanks!

2. Originally Posted by dude15129
Hi, can anyone help me show how to prove this. I know it is common sense, but I don't know how to express on paper how to prove it.

A∩∅=∅

Thanks!
Well, if $A=\left\{a_1,a_2,a_3,...\right\}$, and $\emptyset=\left\{~\right\}$, we see that A and $\emptyset$ have no terms in common. Thus, we see that $A\cap\emptyset=\emptyset$.

I don't we need to go through a rigorous proof. I think you should just state that the empty set and a set A have no intersecting terms, which thus results in a null event [ $\emptyset$].

--Chris

3. Here's a way to sound mathy without getting too rigorous.

Assume, to the contrary, that $A \cap \emptyset \ne \emptyset$. Then there is some $x \in A \cap \emptyset$. But this means $x \in A$ and $x \in \emptyset$. Clearly the latter is false, and thus we have a contradiction.

4. Originally Posted by Chris L T521
Well, if $A=\left\{a_1,a_2,a_3,...\right\}$, and $\emptyset=\left\{~\right\}$, we see that A and $\emptyset$ have no terms in common. Thus, we see that $A\cap\emptyset=\emptyset$.

I don't we need to go through a rigorous proof. I think you should just state that the empty set and a set A have no intersecting terms, which thus results in a null event [ $\emptyset$].

--Chris
I guess you can say something like that. but specifying A gets you in trouble. A can be any set in general, including the empty set. so defining it in terms of elements is overstepping our boundaries.

5. Originally Posted by dude15129
Hi, can anyone help me show how to prove this. I know it is common sense, but I don't know how to express on paper how to prove it.

A∩∅=∅

Thanks!
To prove that A∩∅=∅ you must prove that A∩∅ is a subset of ∅ and then that ∅ is a subset of A∩∅ .

But we know that the empty set is a subset of any set hence ∅ is a subset of A∩∅ .

So we are left with the proof that A∩∅ is a subset of ∅ . for that you need to prove :

...........xεA∩∅ ===>xε∅........................................... ..................1

ΟR because 1 seems a Little strange,through contrapositive law that :

.......................~xε∅ ======> ~(xε∅ ^ xεA) <===>~xεA v ~ xε∅.................................2.

For 1 you need the law of logic called addition elimination:

.......................p^q ====> p or p^q ====>q.....................................,3

For 2 you need the laws of logic called De Morgan's and disjunction introduction:

............................~( p^q) is equivalent to ~p v ~q and p===> pvq............................................... ......4

Sometimes in mathematics the simplests proofs need a lot of thinking.

If you put now p=.................

The above is a syntactical proof, as most,if not all, of mathematical proofs are,but it so happens that in here we can also produce a semantical proof as well, using the truthful values of p and q.

To prove that xεA∩∅ ===>xε∅ i.e. that xεA∩∅ logically implies xε∅ we must prove that the conditional (xεA∩∅ ------>xεA∩∅) is an identity i.e. it is always true.

Or we can loosely reason: Since A∩∅ is always false it is equal to the empty set

6. Originally Posted by Jhevon
I guess you can say something like that. but specifying A gets you in trouble. A can be any set in general, including the empty set. so defining it in terms of elements is overstepping our boundaries.
meh...I tried

--Chris

7. Thanks all of this helped!

8. Here is another proof based on the theorem [~x ( A)] A = ,which theorem Jhevon used in his proof by contradiction

$\forall{x}$(~x $\in\emptyset$) $\Longrightarrow$ $\forall{x}$(~x $\in\emptyset$) v $\forall{x}$(~x $\in A$) $\Longrightarrow$ $\forall{x}$(~x $\in \emptyset$ v ~x $\in A$) $\Longleftrightarrow$ $\forall{x}$ [~x $\in$ ( A $\cap\emptyset$)] $\Longleftrightarrow$ A $\cap\emptyset$ = $\emptyset$

9. Quickest solution I can give is:

$A \cap B \subseteq B$ for all sets $A$ and $B$ directly from the Axiom of Specification.

$\varnothing \subseteq A$ for all sets $A$ which is a standard result.

So you have $A \cap \varnothing \subseteq \varnothing$ and $\varnothing \subseteq A \cap \varnothing$ and the result follows.

10. Originally Posted by Matt Westwood
$A \cap B \subseteq B$ for all sets $A$ and $B$ directly from the Axiom of Specification.
very nice, quick proof.

to do it without the axiom (because i've never heard of that one before--it makes sense though):

To show $A \cap B \subseteq B$, we need to show $x \in A \cap B \implies x \in B$. So assume $x \in A \cap B$. this means $x \in A$ and $\bold{x \in B}$. Thus, $A \cap B \subseteq B$.

11. Originally Posted by Matt Westwood
Quickest solution I can give is:

$A \cap B \subseteq B$ for all sets $A$ and $B$ directly from the Axiom of Specification.

.
I am sorry but can you explain,if you wish, in more details what you mean by the above??

12. Axiom schema of specification - Wikipedia, the free encyclopedia

Or, to put it more "simply":

"For every set and every condition, there corresponds a set whose elements are exactly the same as those elements of the original set for which the condition is true."

Otherwise known as the "Axiom of Subsets".

That is, the set $A \cap B$ can be created from taking the set $A$ and making a set from it with the extra "specification" that elements "must also be in set $B$".

Thus the definition of intersection is created from an axiomatic framework for set theory.

13. Originally Posted by Matt Westwood
Axiom schema of specification - Wikipedia, the free encyclopedia

Or, to put it more "simply":

"For every set and every condition, there corresponds a set whose elements are exactly the same as those elements of the original set for which the condition is true."

Otherwise known as the "Axiom of Subsets".

.
how would you define the word condition in the above axiom

14. Originally Posted by triclino
how would you define the word condition in the above axiom
Loosely speaking, a propositional function which returns "true" or "false" on a given element.

For example, let $A$ be the set of all numbers. Let $P(x)$ be the condition " $x$ is even."

Then the set $\{x \in A: P(x)\}$ means "The set of all elements $x$ of $A$ such that $x$ is even."

In the context of defining $A \cap B$, this can be translated into the above language by saying:

$A \cap B = \{x \in A: x \in B\}$ where the "condition" $P(x)$ is " $x \in B$".

Thus $A \cap B$ means "All elements $x$ of $A$ such that $x$ is (also) in $B$.

We can go further and state that $A \cap B = \{x \in B: x \in A\}$ which means the same thing. Thus intersection is commutative.

This subject goes on for ever, and is usually not treated at degree level - I've gleaned all I know about this aspect of set theory from independent research (i.e. reading books).