Does For All Imply Exists in Quantifier Logic?

[Terrell]

Homework Statement

All married couples have fights

Homework Equations

let x be a person and y be another person
M(x,y): x is married to y
F(x,y): x have fought y

The Attempt at a Solution

∀x∃y(M(x, y) → F(x, y)): i read my translation as "For all x, there is some y such that if x is married to some y then x and y have fought each other"
but i found the correct translation to be: ∀x∀y(M(x, y) → F(x, y))... I do not understand where my mistake is. Should the interpretation for using ∀y be for all the partners x had and will ever have?

 

[PeroK]

Homework Statement

All married couples have fights

Homework Equations

let x be a person and y be another person
M(x,y): x is married to y
F(x,y): x have fought y

The Attempt at a Solution

∀x∃y(M(x, y) → F(x, y)): i read my translation as "For all x, there is some y such that if x is married to some y then x and y have fought each other"
but i found the correct translation to be: ∀x∀y(M(x, y) → F(x, y))... I do not understand where my mistake is. Should the interpretation for using ∀y be for all the partners x had and will ever have?

I'm not sure what your version really means. It almost means:

Everybody is married to someone and fights with them.

Which inadvertently implies everyone is married. But, it really says something like:

For everyone (x), you can find someone (y) such that if x and y are married, then they fight,

But, this sort of logical construction isn't really valid, since once you've found y you have a single pair who are either married and/or fight. There's not really a sense of implication in these cases.

The correct answer that you quote is simple. It says:

For all people (x and y): if they are married, then they fight.

Or, to look at it another way:

Take any two people: are they married? No - there is nothing more to say. Yes - then they fight.

 

[Terrell]

I'm not sure what your version really means. It almost means:

Everybody is married to someone and fights with them.

Which inadvertently implies everyone is married. But, it really says something like:

For everyone (x), you can find someone (y) such that if x and y are married, then they fight,

But, this sort of logical construction isn't really valid, since once you've found y you have a single pair who are either married and/or fight. There's not really a sense of implication in these cases.

The correct answer that you quote is simple. It says:

For all people (x and y): if they are married, then they fight.

Or, to look at it another way:

Take any two people: are they married? No - there is nothing more to say. Yes - then they fight.

hmm... i don't think that my translation inadvertently means everybody is married since it encloses and "if... then" statement.

 

[PeroK]

hmm... i don't think that my translation inadvertently means everybody is married since it encloses and "if... then" statement.

No, it doesn't. I said it "almost" says that. In general, if you have something about "all couples", then it must start $\forall x \ \forall y$. If you start with $\forall x \ \exists y$, you are automatically heading towards a "for everyone, there is someone else" construction.

Here's an example of why your proposition is not right. Let's assume that $x$ is married to $y_1$ and $y_2$. The question says nothing about bigamy being forbidden. Let's say that $x$ fights with $y_1$ but not with $y_2$.

The original proposition says that all married couples fight. If this holds then $x$ must fight with both $y_1$ and $y_2$. In this case, therefore, the original proposition does not hold.

Your proposition, however, does hold, as for this $x$ you can find $y_1$ who is married to $x$ and they fight.

But, my second point is that your logical construction is not really valid in the first place. Because, you haven't said "they are married and they fight". You have said "if they are married, then they fight", which doesn't work with an existential qualifier.

Your construction involves essentially:

$\exists x: \ P(x) \rightarrow Q(x)$

Which doeesn't really mean much.

 

[Stephen Tashi]

∀x∃y(M(x, y) → F(x, y))

Everyone can find someone they could marry and fight with. (That's why its best to stay unmarried or to marry someone whom you won't fight with.)

 

[PeroK]

Everyone can find someone they could marry and fight with. (That's why its best to stay unmarried or to marry someone whom you won't fight with.)

What's the verdict on the construction in the OP? I couldn't figure out a clear meaning for it. Is your post a valid interpretation of the logic?

 

[dkotschessaa]

Homework Statement

All married couples have fights

Homework Equations

let x be a person and y be another person
M(x,y): x is married to y
F(x,y): x have fought y

The Attempt at a Solution

∀x∃y(M(x, y) → F(x, y)): i read my translation as "For all x, there is some y such that if x is married to some y then x and y have fought each other"
but i found the correct translation to be: ∀x∀y(M(x, y) → F(x, y))... I do not understand where my mistake is. Should the interpretation for using ∀y be for all the partners x had and will ever have?

I would read yours as "for all people x, there exists AT LEAST ONE person y, such that if x is married to y, then x and y have fought."

But what you want to say is that it's true for ALL y. Doesn't matter who the person is.

Note that the solution IMPLIES your statement. If the solution is true, your statement will also be true. This is an example of something in math where sometimes you have a statement (like yours) but which to "strengthen" it. Yes, there exists such a y, but is it true for ALL y? That would be a stronger statement.

-Dave K

 

[Stephen Tashi]

What's the verdict on the construction in the OP? I couldn't figure out a clear meaning for it. Is your post a valid interpretation of the logic?

Do you mean a valid interpretation of the OP's attempted answer ? That can be debated.

I said a person "can find someone they could marry... " instead of "there exists some person y such that if they married y...".

If we take "can find" to mean "can theoretically find" then "can find" could be interpreted as "there exists". If we take "can find" to mean some action that depends on the limitations of person x, then "can find" is a debatable interpretation of "there exists". The limitations would have to be severe. For example, if there is a person x who can truthfully say "I can't find anyone who will marry me", this does not invalidate my interpretation, because my interpretation says "x could marry y", not "x marries y" or "x does marry y". So a possible interpretation of " x could marry y " is "if x hypothetically married y". If there is a person x who "cannot find anyone to marry" his situation presumably makes $M(x,y)$ false, so the implication $M(x,y) \implies F(x,y)$ is true.

 

[PeroK]

I would read yours as "for all people x, there exists AT LEAST ONE person y, such that if x is married to y, then x and y have fought."

-Dave K

As implied above, unless $x$ is married to everyone, then this is vacuously true for every $y$ to whom $x$ is not married.

 

[PeroK]

Do you mean a valid interpretation of the OP's attempted answer ? That can be debated.

I said a person "can find someone they could marry... " instead of "there exists some person y such that if they married y...".

If we take "can find" to mean "can theoretically find" then "can find" could be interpreted as "there exists". If we take "can find" to mean some action that depends on the limitations of person x, then "can find" is a debatable interpretation of "there exists". The limitations would have to be severe. For example, if there is a person x who can truthfully say "I can't find anyone who will marry me", this does not invalidate my interpretation, because my interpretation says "x could marry y", not "x marries y" or "x does marry y". So a possible interpretation of " x could marry y " is "if x hypothetically married y". If there is a person x who "cannot find anyone to marry" his situation presumably makes $M(x,y)$ false, so the implication $M(x,y) \implies F(x,y)$ is true.

I meant, in general, does:

$\exists x (P(x) \rightarrow Q(x))$

makes sense, or is it invalid?

Similarly:

$\forall x \exists y (P(x,y) \rightarrow Q(x,y))$

Or, perhaps, it is largely a vacuous proposition?

 

[dkotschessaa]

As implied above, unless $x$ is married to everyone, then this is vacuously true for every $y$ to whom $x$ is not married.

Not sure what you mean, but maybe it's getting difficult to parse these in English.

 

[PeroK]

Not sure what you mean, but maybe it's getting difficult to parse these in English.

If $x$ and $y$ are not married, then the following is vacuously true: if $x$ and $y$ are married, then they fight.

 

[Stephen Tashi]

I meant, in general, does:

$\exists x (P(x) \rightarrow Q(x))$

makes sense, or is it invalid?

Similarly:

$\forall x \exists y (P(x,y) \rightarrow Q(x,y))$

Or, perhaps, it is largely a vacuous proposition?

Both are valid logical expressions, but I can't think of any practical use for them in mathematics. On the other hand, there are expressions in common language that, if taken literally, do match those patterns.

For example: "There are some people that would have been ashamed if they took a bribe" - meaning literally that there exists a person x such that if x took a bribe then x was ashamed".

 

[Terrell]

No, it doesn't. I said it "almost" says that. In general, if you have something about "all couples", then it must start $\forall x \ \forall y$. If you start with $\forall x \ \exists y$, you are automatically heading towards a "for everyone, there is someone else" construction.

Here's an example of why your proposition is not right. Let's assume that $x$ is married to $y_1$ and $y_2$. The question says nothing about bigamy being forbidden. Let's say that $x$ fights with $y_1$ but not with $y_2$.

The original proposition says that all married couples fight. If this holds then $x$ must fight with both $y_1$ and $y_2$. In this case, therefore, the original proposition does not hold.

Your proposition, however, does hold, as for this $x$ you can find $y_1$ who is married to $x$ and they fight.

But, my second point is that your logical construction is not really valid in the first place. Because, you haven't said "they are married and they fight". You have said "if they are married, then they fight", which doesn't work with an existential qualifier.

Your construction involves essentially:

$\exists x: \ P(x) \rightarrow Q(x)$

Which doeesn't really mean much.

yeah. i thought about the bigamy thing too that i forgot to consider after i posted this question.

 

[Terrell]

If you start with ∀x ∃y∀x ∃y\forall x \ \exists y, you are automatically heading towards a "for everyone, there is someone else" construction.

Do you mean a valid interpretation of the OP's attempted answer ? That can be debated.

I said a person "can find someone they could marry... " instead of "there exists some person y such that if they married y...".

did you use "can find" to interpret my interpretation because in order for a person to be ABLE(can) to find a partner, there is no necessity that everybody that exists is a potential partner, but there only needs to be AT LEAST ONE potential partner?

 

[Terrell]

Not sure what you mean, but maybe it's getting difficult to parse these in English.

As implied above, unless $x$ is married to everyone, then this is vacuously true for every $y$ to whom $x$ is not married.

i think you nailed it here. that is exactly what i meant. it is vacuously true for every y to whom x is not married to! also I'm bringing this up in class.

 

[Terrell]

I would read yours as "for all people x, there exists AT LEAST ONE person y, such that if x is married to y, then x and y have fought."

But what you want to say is that it's true for ALL y. Doesn't matter who the person is.

Note that the solution IMPLIES your statement. If the solution is true, your statement will also be true. This is an example of something in math where sometimes you have a statement (like yours) but which to "strengthen" it. Yes, there exists such a y, but is it true for ALL y? That would be a stronger statement.

-Dave K

yeah i completely agree with what you said here, but i think that my interpretation, though it does not explicitly say all the y that x is married to, implies IT due to the conditional if y is married to x...?

 

[Stephen Tashi]

but i think that my interpretation, though it does not explicitly say all the y that x is married to, implies IT due to the conditional if y is married to x...?

I'm not sure what you are saying.

$\forall x \exists y (M(x,y) \implies F(x,y))$ is not equivalent to $\forall x \exists y (M(x,y) \land F(x,y))$
$\forall x \exists y (M(x,y) \implies F(x,y))$ is not equivalent to $\forall x \forall y ( M(x,y) \implies F(x,y))$