Page 2 of 3 FirstFirst 123 LastLast
Results 16 to 30 of 45

Math Help - Logic

  1. #16
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    One last question I hope:

    I have two universes:

    a)

    0 =0
    1 = {0}
    2 = {0,1}

    3 = {0,1,2}
    ....

    and I have to prove that :
    ∀x∀y[(x=y)↔∀z(zEx↔zEy)].

    b)universe {0,{1},2} and I have to prove that the same type ∀x∀y[(x=y)↔∀z(zEx↔zEy)] doesnt apply to this universe.

    The type means that two sets of numbers are equal if and only if they have the same "members".


    For the universe (a) I see that it is logic for the type to apply but I cant write it down. Dont know how to say it.

    For the universe (b) I dont know why it doesnt apply. Something goes wrong with {1} but cant figure out what.

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    (A note on notation: To reduce the number of parentheses, I write \forall x.\,P(x) with a period after x when the scope of \forall x extends as far to the right as possible.)

    Point (a) can be checked directly. There are only ten different pairs (x, y) (if we ignore symmetric pairs because it is clear that the relation x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow x\in y is symmetric). One can check all ten pairs and make sure that the equivalence holds.

    Alternatively, it is obvious that \forall x,y.\,x=y\to \forall z.\,z\in x\leftrightarrow z\in y. We can prove the converse using the contrapositive: \forall x, y.\,x\ne y\to\exists z.\,z\in x\land z\notin y\lor z\notin x\land z\in y. Here for every pair of distinct elements (there are only six of those taking symmetry into account) one has to find an element belonging to one set but not to the other.

    For (b), first write the set {0,{1},2} expanding the definitions of 0, 1, and 2. All three elements are different, so if we evaluated x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y on x,y\in \{0,\{1\},2\} in the universe of all sets, the formula would be true. That is, for different x and y there would be a witness of the difference, i.e., a set z belonging to one but not to the other. However, our universe is very poor, and the witnesses we found above may not be in our universe. That's why the formula may not be true in this small universe.

    In any case, it is easy again to check every pair of distinct elements x and y (now there are only three of them) and see if x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y is true. Remember that z ranges over the same 3-element universe.
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    (A note on notation: To reduce the number of parentheses, I write \forall x.\,P(x) with a period after x when the scope of \forall x extends as far to the right as possible.)

    Point (a) can be checked directly. There are only ten different pairs (x, y) (if we ignore symmetric pairs because it is clear that the relation x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow x\in y is symmetric). One can check all ten pairs and make sure that the equivalence holds.

    Alternatively, it is obvious that \forall x,y.\,x=y\to \forall z.\,z\in x\leftrightarrow z\in y. We can prove the converse using the contrapositive: \forall x, y.\,x\ne y\to\exists z.\,z\in x\land z\notin y\lor z\notin x\land z\in y. Here for every pair of distinct elements (there are only six of those taking symmetry into account) one has to find an element belonging to one set but not to the other.

    For (b), first write the set {0,{1},2} expanding the definitions of 0, 1, and 2. All three elements are different, so if we evaluated x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y on x,y\in \{0,\{1\},2\} in the universe of all sets, the formula would be true. That is, for different x and y there would be a witness of the difference, i.e., a set z belonging to one but not to the other. However, our universe is very poor, and the witnesses we found above may not be in our universe. That's why the formula may not be true in this small universe.

    In any case, it is easy again to check every pair of distinct elements x and y (now there are only three of them) and see if x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y is true. Remember that z ranges over the same 3-element universe.
    Thanks once more.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    (A note on notation: To reduce the number of parentheses, I write \forall x.\,P(x) with a period after x when the scope of \forall x extends as far to the right as possible.)

    Point (a) can be checked directly. There are only ten different pairs (x, y) (if we ignore symmetric pairs because it is clear that the relation x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow x\in y is symmetric). One can check all ten pairs and make sure that the equivalence holds.

    Alternatively, it is obvious that \forall x,y.\,x=y\to \forall z.\,z\in x\leftrightarrow z\in y. We can prove the converse using the contrapositive: \forall x, y.\,x\ne y\to\exists z.\,z\in x\land z\notin y\lor z\notin x\land z\in y. Here for every pair of distinct elements (there are only six of those taking symmetry into account) one has to find an element belonging to one set but not to the other.

    For (b), first write the set {0,{1},2} expanding the definitions of 0, 1, and 2. All three elements are different, so if we evaluated x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y on x,y\in \{0,\{1\},2\} in the universe of all sets, the formula would be true. That is, for different x and y there would be a witness of the difference, i.e., a set z belonging to one but not to the other. However, our universe is very poor, and the witnesses we found above may not be in our universe. That's why the formula may not be true in this small universe.

    In any case, it is easy again to check every pair of distinct elements x and y (now there are only three of them) and see if x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y is true. Remember that z ranges over the same 3-element universe.
    Sorry but I got stuck. Say I have universe {a,{g},c). Where {g}=a,b. If I want two take 2 same sets I will take {a,{g}} and {{g},a} correct? How can I not take two same sets if I want the type to apply ? Hope you understand my question.
    Follow Math Help Forum on Facebook and Google+

  5. #20
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Sorry but I got stuck. Say I have universe {a,{g},c). Where {g}=a,b. If I want two take 2 same sets I will take {a,{g}} and {{g},a} correct? How can I not take two same sets if I want the type to apply ? Hope you understand my question.
    I am not sure I understand completely. First, what is b in "{g}=a,b"? Next, if {g} = a, then the set {a, {g}, c} is {{g}, {g}, c}, which is the same as {{g}, c} -- where is this in the problem statement?

    First, I recommend expanding the definitions of 0, 1, and 2. You can't talk about elements of 2 if all you see is the name "2". Write explicitly what this set is, as well as all other sets.

    Second, let's postulate that two sets are equal, by definition, if they can be written in exactly the same way using only curly braces, comma and \emptyset. Obviously, we cannot invalidate the direction x=y\to\forall z.\,z\in x\leftrightarrow z\in y. Therefore, we need to find a counterexample to the opposite direction: (\forall z.\,z\in x\leftrightarrow z\in y)\to x=y. So, we need to find x and y that cannot be written in the same way, but for which \forall z.\,z\in x\leftrightarrow z\in y is true.

    Once you replace 0, 1 and 2 by their definitions, you'll see that these are three non-equal sets, according to the definition above. So, you need to consider three possible pairs and choose the pair (x, y) for which \forall z.\,z\in x\leftrightarrow z\in y is true, i.e., x and y have the same elements out of the three possible elements that we have.
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Still trying to get it. Well I have the universe:

    {0,{1},2}. The element {1} doesnt it mean that it is equal with 0,1 ? It is a different set in a set correct ?

    Now I have the type ∀x∀y[(x=y)↔∀z(zEx↔zEy)]. This means that two sets are equal if and only if they have the same elements.

    So I must prove that the type doesnt apply to my universe. But where I object is:

    If I take set {0,{1}} and set {{1},0}. Why doesnt it apply ? Dont they have the same elements ??

    Even in an another universe like my first one :
    0 =0
    1 = {0}
    2 = {0,1}

    3 = {0,1,2}

    If I want the type to apply I must take the set {0,1,2} with the set {0,1,2} and compare them? Correct? I cant take the set {0,1} and the set {0,1,2} and say they are the same. Right? Or I got it completely wrong ?

    What I mean is that I have to take twice the same sets. Or not? Would you be so kind to give me an example for both universes so that I get it?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  7. #22
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    First, I am sorry that I did not notice the "..." in the first post, which must mean that the universe in point a) is infinite. So one cannot prove that the type is true by comparing only 0, 1 and 2; one needs a general proof.

    Well I have the universe: {0,{1},2}.
    By expanding the definitions I meant replacing 0 with \emptyset, 1 with \{\emptyset\} and 2 with \{\emptyset,\{\emptyset\}\}, as described in your first post. So, you have the set \{\emptyset,\{\{\emptyset\}\},\{\emptyset,\{\empty  set\}\}\}.

    The element {1} doesnt it mean that it is equal with 0,1 ?
    What is 0, 1? It is not a set because sets are written in curly braces. If you mean whether {1} equals {0,1}, this is not correct: \{1\}=\{\{\emptyset\}\} and \{0,1\}=\{\emptyset,\{\emptyset\}\}.

    If I take set {0,{1}} and set {{1},0}. Why doesnt it apply ?
    I don't understand how you came up with {0,{1}} and {{1},0}. Why are you considering this set?

    Even in an another universe like my first one :
    0 =0
    1 = {0}
    2 = {0,1}

    3 = {0,1,2}

    If I want the type to apply I must take the set {0,1,2} with the set {0,1,2} and compare them?
    Yes, though you need to compare all pairs of elements.

    I cant take the set {0,1} and the set {0,1,2} and say they are the same.
    You can't prove that they are the same; the opposite is true.

    So, for a) we need to prove that the type is true. This is sort of obvious, so it's a little difficult to describe. For example, first one can check that for any pair (x, y), either x=y, or x\in y or y\in x holds. The left-to-right direction is clear; the opposite can be proved by contrapositive. So assume that you have x\ne y. Then x\in y or y\in x; both variants are considered similarly. Suppose x\in y. Since x\notin x (I think this is one of the axioms of set theory), we have x\in y but x\notin x. Therefore, x and y do not have the same elements.

    For b), our universe is a three-element set \{\emptyset,\{\{\emptyset\}\},\{\emptyset,\{\empty  set\}\}\}. We need to find two different elements that have the same elements. Let's compare \{1\}=\{\{\emptyset\}\} and 2=\{\emptyset,\{\emptyset\}\}. For each element of the universe, we have the following results.
    Code:
    
    
    
    
    
    z     |  
    
    
    
    
    z\in\{\{\emptyset\}\}  |  
    
    
    
    
    z\in\{\emptyset,\{\emptyset\}\}
    -----------------------------------------
    
    
    
    
    
    \emptyset     |  False    |     True
    
    
    
    
    
    \{\{\emptyset\}\}  |  False    |     False
    
    
    
    
    
    \{\emptyset, \{\emptyset\}\}|  False    |     False
    So {1} and 2 do not agree on \emptyset. Now compare \emptyset and \{\{\emptyset\}\} and \emptyset and \{\emptyset,\{\emptyset\}\} in the same way.
    Follow Math Help Forum on Facebook and Google+

  8. #23
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Once more thanks for your patience. Let me tell you what I did for the first one and tell me your opinion please:

    I said that if we compare the symmetric pairs e.g. {1,2,3} and {3,2,1} it is obvious that x=y and zEx and zEy. Furthermore for the other distinct pairs I used your method of contrapositive and said : For every distinct pair of elements if the type didnt apply I should have \forall x,y.\,x\ne y\to\exists z.\,z\in x\land z\notin y\lor z\notin x\land z\in y which is impossible since every next element is the succesor of its precending element.

    I hope I dont write nonsenses.
    Follow Math Help Forum on Facebook and Google+

  9. #24
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    For the second universe I did what you wrote. I compared {1} and 2 and I said that even though \emptyset belongs to 2, it doesn't belong to 1 so the type doesnt apply since  z\in x but z\notin y.
    Follow Math Help Forum on Facebook and Google+

  10. #25
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    I want to believe -with your help of course- that my answers are acceptable.
    Follow Math Help Forum on Facebook and Google+

  11. #26
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    For the second universe I did what you wrote. I compared {1} and 2 and I said that even though belongs to 2, it doesn't belong to 1 so the type doesnt apply since but .
    The formula was \forall x,y.\,x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow z\in y. We were checking it for x=\{\{\emptyset\}\} and y=\{\emptyset,\{\emptyset\}\}. The left-hand side x=y is false, since the sets are different. The right-hand side \forall z.\,z\in x\leftrightarrow z\in y is also false: for z=\emptyset, z\notin\{\{\emptyset\}\}, but z\in\{\emptyset,\{\emptyset\}\}. So both sides of the equivalence are false, and therefore this pair (x,y) is not a counterexample to the formula.

    This means that the formula is still false in b), but not for the reason that you wrote.
    Follow Math Help Forum on Facebook and Google+

  12. #27
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Furthermore for the other distinct pairs I used your method of contrapositive and said : For every distinct pair of elements if the type didnt apply I should have which is impossible since every next element is the succesor of its precending element.
    This formula is precisely true in a). It is equivalent to \forall x,y.\,x=y\gets\forall z.\,z\in x\leftrightarrow z\in y, which is one direction of the formula \forall x,y.\,x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow z\in y, and you need to show that this last formula is true in a). Your explanation: "is impossible since every next element is the succesor of its precending element" is not clear and is in fact wrong.
    Follow Math Help Forum on Facebook and Google+

  13. #28
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I said that if we compare the symmetric pairs e.g. {1,2,3} and {3,2,1} it is obvious that x=y and zEx and zEy.
    I think I see what you mean, but formally this sentence makes little sense. By "symmetric pairs" do you mean "equal pairs"? Next, the variables x, y, and z are used without being introduced. It is not clear what they are, whether x=y is supposed to hold for all x, y or for some x, y; what the relation between x, y, and z is and so on.

    It looks like you would benefit from reviewing the language and proofs of first-order logic: what formulas and quantifiers are and how one proves claims and uses assumptions of different forms (conjunction, disjunction, implication, universal and existential quantification).
    Follow Math Help Forum on Facebook and Google+

  14. #29
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    The formula was \forall x,y.\,x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow z\in y. We were checking it for x=\{\{\emptyset\}\} and y=\{\emptyset,\{\emptyset\}\}. The left-hand side x=y is false, since the sets are different. The right-hand side \forall z.\,z\in x\leftrightarrow z\in y is also false: for z=\emptyset, z\notin\{\{\emptyset\}\}, but z\in\{\emptyset,\{\emptyset\}\}. So both sides of the equivalence are false, and therefore this pair (x,y) is not a counterexample to the formula.

    This means that the formula is still false in b), but not for the reason that you wrote.

    Excuse because I am so confused. Ok I'll take the pairs and compare them in b) and that would be an acceptable answer, right? . For 1 and 2 you compared them. Let me compare 0 and 1. I have that x\ne y and for z=\emptyset z\in 0 but z\notin\ 1. Lets compare now 0 and 2. I have x\ne y and for z=\emptyset, z\in 0 & z\in 2. Correct? BUT WHY 0 and 2 are not equal ??

    But in a) if I start comparing is there any chance to make the type become true?
    What I mean is that if I compare 1 and 2 I will have:

    1= \{\emptyset\} and 2= \{\emptyset\{\emptyset\}\}.

    How are they equal ?

    Dont get it. Sorry. If I got you tired forget it. Thanks for your patience so far.
    Last edited by milagros; January 26th 2010 at 10:47 PM.
    Follow Math Help Forum on Facebook and Google+

  15. #30
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Let me compare 0 and 1. I have that and for but .
    First, in b), we don't have 1 in the universe; we have \{1\}, i.e., \{\{\emptyset\}\}. Recall that we are checking whether the formula \forall x,y.\,x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow z\in y is true in our universe. Therefore, x and y range over (i.e., take values from) our universe, which is \{0,\{1\},2\}, or \{\emptyset,\{\{\emptyset\}\},\{\emptyset,\{\empty  set\}\}\}. So you should compare (as one of three pairs) x=\emptyset and y=\{\{\emptyset\}\}.

    Second, why do you write "for "? By definition, 0=\emptyset, i.e., the empty set, so z\in0 is never true for any z. The same goes for the comparison of 0 and 2. That's why it is important to replace 0, 1, and 2 by their definitions.

    BUT WHY 0 and 2 are not equal ?
    It seems to me that this moment is somewhat glossed over in the problem statement. That's why I said earlier:
    let's postulate that two sets are equal, by definition, if they can be written in exactly the same way using only curly braces, comma and .
    Here 0 is \emptyset and 2 is \{\emptyset,\{\emptyset\}\}. You can write 2 differently, such as \{\{\emptyset\},\emptyset,\emptyset\} (since the order and multiplicity of elements is ignored for sets), but there is no way to write 0 and 2 in the same way.

    But in a) if I start comparing is there any chance to make the type become true?
    What I mean is that if I compare 1 and 2 I will have:

    1= and 2=.

    How are they equal ?
    Yes, the whole formula is true. Indeed, x=y is not the whole formula, is it? If you are checking whether some formula A\leftrightarrow B is true and you found that A is false, that's not the end of the story. If B is also false, the whole formula is true. In a), for every non-equal x and y, the right-hand side \forall z.\,z\in x \leftrightarrow z\in y is also false.
    Follow Math Help Forum on Facebook and Google+

Page 2 of 3 FirstFirst 123 LastLast

Similar Math Help Forum Discussions

  1. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 04:30 AM
  2. logic
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: December 1st 2008, 09:49 AM
  3. logic
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 3rd 2008, 11:30 PM
  4. logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 3rd 2008, 12:53 AM
  5. Logic
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 12th 2007, 06:05 PM

Search Tags


/mathhelpforum @mathhelpforum