Results 1 to 14 of 14

Math Help - Logic & Propositions & Proofs

  1. #1
    Junior Member
    Joined
    Aug 2008
    Posts
    33

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Santa Cruz, CA
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by dude15129 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Chris L T521 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by dude15129 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Santa Cruz, CA
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by Jhevon View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2008
    Posts
    33
    Thanks all of this helped!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Aug 2008
    Posts
    42
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Matt Westwood View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by Matt Westwood View Post
    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??
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by Matt Westwood View Post
    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
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    Quote Originally Posted by triclino View Post
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Logic proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 21st 2011, 04:39 PM
  2. Replies: 3
    Last Post: September 17th 2010, 09:46 AM
  3. propositions and logic help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 22nd 2009, 04:57 PM
  4. Logic Proofs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 21st 2008, 09:02 AM
  5. Proving logic propositions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 3rd 2008, 08:22 PM

Search Tags


/mathhelpforum @mathhelpforum