Set Theory Questions: Equivalence Rules and Tautology Proof

In summary: Ex)(Ay)p(x,y) <=> (Ay)(Ex)p(x,y)Do i need to prove/disprove that it is a tautology or a theorem?You can't prove that something is a tautology, since "tautology" is a term that refers to a semantic relation between well-formed formulas, not a theorem of any particular system. You can only prove that something is a theorem, and in this case, I think the idea is that you're not supposed to prove or disprove anything. You're just supposed to note that the statement is an equivalence, and that one of those equivalences is a theorem while the other is not. So just find
  • #1
MathematicalPhysicist
Gold Member
4,699
373
i searched in the homework section and there isn't a section for logic an set theory so i ask my questions here (begging for replies):
1)expand the proposition (by the equivalence rules):
[~(pvq)v((~p)^q)]
i got to this: [(~pv~p)^(~pv~q)]^[(qv~p)^(qv~q)]
is it correct?
2) prove/disprove:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
which means to prove that the double implication is tautology.
so i have assumed that:
T-(Ex)(Ay)p(x,y)
T-(Ay)p(a,y)
T-p(a,y)
T-(Ea)p(a,y)
T-(Ay)(Ex)P(x,y)
is this correct or where i am wrong?

your replies is much appreciated.
 
Physics news on Phys.org
  • #2
loop quantum gravity said:
1)expand the proposition (by the equivalence rules):
[~(pvq)v((~p)^q)]
i got to this: [(~pv~p)^(~pv~q)]^[(qv~p)^(qv~q)]
is it correct?
I'm not sure what "expand" means. Do you want to distribute them, using

(P v (Q & R)) <=> ((P v Q) & (P v R))
(P & (Q v R) <=> ((P & Q) v (P & R))

??
2) prove/disprove:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
which means to prove that the double implication is tautology.
so i have assumed that:
T-(Ex)(Ay)p(x,y)
T-(Ay)p(a,y)
T-p(a,y)
T-(Ea)p(a,y)
T-(Ay)(Ex)P(x,y)
is this correct or where i am wrong?
your replies is much appreciated.
Consider this example.

(1) [tex]\forall x \exists y (x = y)[/tex]

This says that for every x that I choose, I can find at least one y that is equal to that x.

(2) [tex]\exists y \forall x (x = y)[/tex]

This says that I can find at least one y that is equal to every x.

Can you think of a case where (1) is true and (2) is false?
 
  • #3
I don't know if "tautology" is the right word to be using there. Perhaps you mean to show that it is a theorem? As for your proof, you probably shouldn't instatiate y with y, but at any rate, when you instatiate x, you have to do so as an assumption. Within the scope of that assumption, you have to derive some existentially quantified sentence that does not contain the constant by which you instantiated x. From that you can conclude that your derived sentence is true even beyond the scope of your assumption, and then you can make the desired conclusion that you have. So your proof, although sketchy, is the right idea behind proving that (Ex)(Ay)p(x,y) -> (Ay)(Ex)p(x,y). However, this proof does not give you the converse because the converse is, in fact, not true, as honestrosewater's example demonstrates.

For #1, by "expand" it appears you mean that you wish to express your sentence in conjunctive normal form, that is, in the form:

[A v B] & [C v D] & ... & [Y v Z]

where I believe A, B, ..., Y, Z have to be either atomic sentences or negations of atomic sentences. I looked it up, and CNFs take the above form, but inside the brackets you can have any number of disjuncts (even just 1), not only 2. I don't know whether you did the work right, but one way to check that you've done it right is to look at what the CNF shows you. Since the CNF of your sentence is equivalent to your sentence, your sentence is true iff the CNF is true. The CNF is true iff all its conjuncts are true. All the conjuncts are true iff:

(~pv~p) is true, (~pv~q) is true, (qv~p) is true, and (qv~q) is true

iff

* ~p is true, (~pv~q) is true, (qv~p) is true, and (qv~q) is true

iff

~p is true. Why? Because clearly if all the sentences following * are true, then the first one is, and the first one is just ~p. On the other hand, if ~p is true, then certainly ~p is true, and the second and third sentences are also true (by the rule of disjunction introduction, i.e. the fact that a implies (a v b)), and the last sentence is a tautology so it's always true.

Now, check that your sentence is true iff ~p is true. I would rewrite your sentence as:

[~(pvq)v((~p)^q)]
[((~p)^(~q))v((~p)^q)] by DeMorgan's
[(~p)^((~q)vq)] by distribution
~p since ((~q)vq) is tautologous

From here, it's more than obvious that your sentence is true iff ~p is true.
 
  • #4
honestrosewater said:
I'm not sure what "expand" means. Do you want to distribute them, using

(P v (Q & R)) <=> ((P v Q) & (P v R))
(P & (Q v R) <=> ((P & Q) v (P & R))
these are the equivalence rules i used, so yes. :rolleyes:
??
Consider this example.

(1) [tex]\forall x \exists y (x = y)[/tex]

This says that for every x that I choose, I can find at least one y that is equal to that x.

(2) [tex]\exists y \forall x (x = y)[/tex]

This says that I can find at least one y that is equal to every x.

Can you think of a case where (1) is true and (2) is false?
yes i can see your point, but how do i translate it in mathematical sense?
i mean we start with assuming the antecedant is T and we should be getting that the consequent is F, and thus it will not be "<=>".
how do i write it?
thanks in advance. (you guys are superb!).
 
  • #5
So what exactly do you have to do when they ask you to "expand"? And for the second problem, how are you supposed to go about proving/disproving? Do you need to prove/disprove that it is a tautology (I think you would mean "valid", not "tautology") or prove/disprove that it is a theorem? Or if you're not sure, what is it that you know so far, and what kind of methods are you expected to use?
 
  • #6
it's my mistake, it should be "simplify". (it has gone wrong in my interpratation from hebrew to english).
ok, so i get the first question, but what about the second one how do i formulate it?
 
  • #7
you know,i still need the help about question two, and how to formulate the proof?
:zzz:
 
  • #8
2) prove/disprove:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
which means to prove that the double implication is tautology.
Do we agree, first of all, that the sentence isn't always true, so we'll be proving it's not a "tautology?" So you're either asked to prove that it is not a theorem, or that it is not valid. I'm not sure how, in general, to prove something is not a theorem unless you prove that it's not valid and use the Soundness Theorem (which states that if something is a theorem, then it is valid, i.e. if it's not valid it's not a theorem). If you're not allowed to do that, then I don't know what to do. On the other hand if you're just asked to show that it is not valid, then you simply have to construct an interpretation on which the sentence is false. You've been given a good hint from honestrosewater, all you have to do is formalize what he said into a proof. But that's your homework, not ours.
 
  • #9
so let see if i figured it out:
(Ex)(Ay)p(x,y)<=> (Ay)(Ex)p(x,y)
i need to prove/disprove the sentence.
lets assume:
ExAyp(x,y) is true.
then there's a specific x=a
so
EaAyp(a,y) is true.
the sentence "AyExp(x,y)" is actually "~Ey~Axp(x,y)"
and by the contrapositive we can see that is only one way material implication and not double material implication.

therefore the sentence isn't correct.

should i say q.e.d or it's not formalise as it should? :confused: :zzz: :smile:
 
  • #10
loop quantum gravity said:
the sentence "AyExp(x,y)" is actually "~Ey~Axp(x,y)"
No it's not.
and by the contrapositive we can see that is only one way material implication and not double material implication.
The contrapositive of what? Also, looking at something and seeing that a certain implication holds doesn't count as proof that a different implication doesn't hold. By the way, "double material implication" is simply called "material equivalence."

Anyways, the only way I can think to do this is to come up with a counterexample. There is a formal way to come up with a counterexample (it involves producing a structure which does not model the sentence), but the informal way should be fine if you haven't learned anything about models. I believe honestrosewater has already given you a counterexample.
 
  • #11
so counterexample, is what called a formal proof in maths.
blamy, i didn't know that.
thank you, very much.
have a nice day/evening/midday.
|-:
 

FAQ: Set Theory Questions: Equivalence Rules and Tautology Proof

What is a tautology in set theory?

A tautology in set theory is a statement that is always true, regardless of the truth values of the individual elements within the set. It is a logical consequence of the definition of sets and their operations.

How are equivalence rules used in set theory problems?

Equivalence rules in set theory are used to prove the equality of two sets by showing that they contain the same elements or that one set is a subset of the other. These rules include the reflexive, symmetric, and transitive properties of equality.

What is the process for proving a tautology in set theory?

The process for proving a tautology in set theory involves using logical reasoning and the definitions of sets and their operations to show that a statement is true for all possible combinations of elements within the sets. This can be done by using equivalence rules and constructing logical arguments.

Can you give an example of a set theory problem involving equivalence rules and tautology proof?

One example of a set theory problem involving equivalence rules and tautology proof is proving that the union of two sets is commutative, meaning that the order of the sets in the union does not affect the result. This can be proven by using the definition of the union operation and the symmetric property of equality.

How can understanding equivalence rules and tautologies benefit a scientist?

Understanding equivalence rules and tautologies in set theory can benefit a scientist by providing a framework for logical reasoning and problem-solving. These concepts can help in analyzing data, constructing arguments, and making accurate conclusions in various scientific fields such as mathematics, computer science, and statistics.

Similar threads

Back
Top