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

2. (A note on notation: To reduce the number of parentheses, I write $\displaystyle \forall x.\,P(x)$ with a period after $\displaystyle x$ when the scope of $\displaystyle \forall x$ extends as far to the right as possible.)

Point (a) can be checked directly. There are only ten different pairs $\displaystyle (x, y)$ (if we ignore symmetric pairs because it is clear that the relation $\displaystyle 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 $\displaystyle \forall x,y.\,x=y\to \forall z.\,z\in x\leftrightarrow z\in y$. We can prove the converse using the contrapositive: $\displaystyle \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 $\displaystyle x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y$ on $\displaystyle x,y\in \{0,\{1\},2\}$ in the universe of all sets, the formula would be true. That is, for different $\displaystyle x$ and $\displaystyle y$ there would be a witness of the difference, i.e., a set $\displaystyle 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 $\displaystyle x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y$ is true. Remember that $\displaystyle z$ ranges over the same 3-element universe.

3. Originally Posted by emakarov
(A note on notation: To reduce the number of parentheses, I write $\displaystyle \forall x.\,P(x)$ with a period after $\displaystyle x$ when the scope of $\displaystyle \forall x$ extends as far to the right as possible.)

Point (a) can be checked directly. There are only ten different pairs $\displaystyle (x, y)$ (if we ignore symmetric pairs because it is clear that the relation $\displaystyle 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 $\displaystyle \forall x,y.\,x=y\to \forall z.\,z\in x\leftrightarrow z\in y$. We can prove the converse using the contrapositive: $\displaystyle \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 $\displaystyle x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y$ on $\displaystyle x,y\in \{0,\{1\},2\}$ in the universe of all sets, the formula would be true. That is, for different $\displaystyle x$ and $\displaystyle y$ there would be a witness of the difference, i.e., a set $\displaystyle 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 $\displaystyle x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y$ is true. Remember that $\displaystyle z$ ranges over the same 3-element universe.
Thanks once more.

4. Originally Posted by emakarov
(A note on notation: To reduce the number of parentheses, I write $\displaystyle \forall x.\,P(x)$ with a period after $\displaystyle x$ when the scope of $\displaystyle \forall x$ extends as far to the right as possible.)

Point (a) can be checked directly. There are only ten different pairs $\displaystyle (x, y)$ (if we ignore symmetric pairs because it is clear that the relation $\displaystyle 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 $\displaystyle \forall x,y.\,x=y\to \forall z.\,z\in x\leftrightarrow z\in y$. We can prove the converse using the contrapositive: $\displaystyle \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 $\displaystyle x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y$ on $\displaystyle x,y\in \{0,\{1\},2\}$ in the universe of all sets, the formula would be true. That is, for different $\displaystyle x$ and $\displaystyle y$ there would be a witness of the difference, i.e., a set $\displaystyle 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 $\displaystyle x=y\leftrightarrow \forall z.\,z\in x\leftrightarrow z\in y$ is true. Remember that $\displaystyle 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.

5. 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 $\displaystyle \emptyset$. Obviously, we cannot invalidate the direction $\displaystyle x=y\to\forall z.\,z\in x\leftrightarrow z\in y$. Therefore, we need to find a counterexample to the opposite direction: $\displaystyle (\forall z.\,z\in x\leftrightarrow z\in y)\to x=y$. So, we need to find $\displaystyle x$ and $\displaystyle y$ that cannot be written in the same way, but for which $\displaystyle \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 $\displaystyle (x, y)$ for which $\displaystyle \forall z.\,z\in x\leftrightarrow z\in y$ is true, i.e., $\displaystyle x$ and $\displaystyle y$ have the same elements out of the three possible elements that we have.

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

7. 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 $\displaystyle \emptyset$, 1 with $\displaystyle \{\emptyset\}$ and 2 with $\displaystyle \{\emptyset,\{\emptyset\}\}$, as described in your first post. So, you have the set $\displaystyle \{\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: $\displaystyle \{1\}=\{\{\emptyset\}\}$ and $\displaystyle \{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 $\displaystyle (x, y)$, either $\displaystyle x=y$, or $\displaystyle x\in y$ or $\displaystyle y\in x$ holds. The left-to-right direction is clear; the opposite can be proved by contrapositive. So assume that you have $\displaystyle x\ne y$. Then $\displaystyle x\in y$ or $\displaystyle y\in x$; both variants are considered similarly. Suppose $\displaystyle x\in y$. Since $\displaystyle x\notin x$ (I think this is one of the axioms of set theory), we have $\displaystyle x\in y$ but $\displaystyle x\notin x$. Therefore, $\displaystyle x$ and $\displaystyle y$ do not have the same elements.

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

8. 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 $\displaystyle \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.

9. For the second universe I did what you wrote. I compared {1} and 2 and I said that even though $\displaystyle \emptyset$ belongs to 2, it doesn't belong to 1 so the type doesnt apply since $\displaystyle z\in x$ but $\displaystyle z\notin y$.

10. I want to believe -with your help of course- that my answers are acceptable.

11. 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 $\displaystyle \forall x,y.\,x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow z\in y$. We were checking it for $\displaystyle x=\{\{\emptyset\}\}$ and $\displaystyle y=\{\emptyset,\{\emptyset\}\}$. The left-hand side $\displaystyle x=y$ is false, since the sets are different. The right-hand side $\displaystyle \forall z.\,z\in x\leftrightarrow z\in y$ is also false: for $\displaystyle z=\emptyset$, $\displaystyle z\notin\{\{\emptyset\}\}$, but $\displaystyle z\in\{\emptyset,\{\emptyset\}\}$. So both sides of the equivalence are false, and therefore this pair $\displaystyle (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.

12. 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 $\displaystyle \forall x,y.\,x=y\gets\forall z.\,z\in x\leftrightarrow z\in y$, which is one direction of the formula $\displaystyle \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.

13. 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).

14. Originally Posted by emakarov
The formula was $\displaystyle \forall x,y.\,x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow z\in y$. We were checking it for $\displaystyle x=\{\{\emptyset\}\}$ and $\displaystyle y=\{\emptyset,\{\emptyset\}\}$. The left-hand side $\displaystyle x=y$ is false, since the sets are different. The right-hand side $\displaystyle \forall z.\,z\in x\leftrightarrow z\in y$ is also false: for $\displaystyle z=\emptyset$, $\displaystyle z\notin\{\{\emptyset\}\}$, but $\displaystyle z\in\{\emptyset,\{\emptyset\}\}$. So both sides of the equivalence are false, and therefore this pair $\displaystyle (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 $\displaystyle x\ne y$ and for $\displaystyle z=\emptyset$ $\displaystyle z\in 0$ but $\displaystyle z\notin\ 1$. Lets compare now 0 and 2. I have $\displaystyle x\ne y$ and for $\displaystyle z=\emptyset$,$\displaystyle z\in 0$ & $\displaystyle 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=$\displaystyle \{\emptyset\}$ and 2=$\displaystyle \{\emptyset\{\emptyset\}\}$.

How are they equal ?

Dont get it. Sorry. If I got you tired forget it. Thanks for your patience so far.

15. 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 $\displaystyle \{1\}$, i.e., $\displaystyle \{\{\emptyset\}\}$. Recall that we are checking whether the formula $\displaystyle \forall x,y.\,x=y\leftrightarrow\forall z.\,z\in x\leftrightarrow z\in y$ is true in our universe. Therefore, $\displaystyle x$ and $\displaystyle y$ range over (i.e., take values from) our universe, which is $\displaystyle \{0,\{1\},2\}$, or $\displaystyle \{\emptyset,\{\{\emptyset\}\},\{\emptyset,\{\empty set\}\}\}$. So you should compare (as one of three pairs) $\displaystyle x=\emptyset$ and $\displaystyle y=\{\{\emptyset\}\}$.

Second, why do you write "for "? By definition, $\displaystyle 0=\emptyset$, i.e., the empty set, so $\displaystyle z\in0$ is never true for any $\displaystyle 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 $\displaystyle \emptyset$ and 2 is $\displaystyle \{\emptyset,\{\emptyset\}\}$. You can write 2 differently, such as $\displaystyle \{\{\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, $\displaystyle x=y$ is not the whole formula, is it? If you are checking whether some formula $\displaystyle A\leftrightarrow B$ is true and you found that $\displaystyle A$ is false, that's not the end of the story. If $\displaystyle B$ is also false, the whole formula is true. In a), for every non-equal $\displaystyle x$ and $\displaystyle y$, the right-hand side $\displaystyle \forall z.\,z\in x \leftrightarrow z\in y$ is also false.

Page 2 of 3 First 123 Last