in Mathematical Logic
1,886 views
2 votes
2 votes

1. Let P(x, y) be a propositional function. Show that∃x ∀y P(x, y) → ∀y ∃x P(x, y) is a tautology.
2. Let P(x) and Q(x) be propositional functions. Showthat ∃x (P(x) → Q(x)) and ∀x P(x) → ∃x Q(x) always
have the same truth value.
3. If ∀y ∃x P(x, y) is true, does it necessarily follow that∃x ∀y P(x, y) is true?
4. If ∀x ∃y P(x, y) is true, does it necessarily follow that ∃x ∀y P(x, y) is true?

in Mathematical Logic
1.9k views

2 Comments

3 and 4 are false.
1
1
3 and 4 are false . 3 can be seen the hexagon of logic. and 4 can be seen taking a example.
1,2,3 = x

y= 4,5,6

(2,4), (2,5) (2,6) . but 1 and 3 do not have any y ,
0
0

1 Answer

2 votes
2 votes
Best answer

1. We need to show that ∃x ∀y P(x, y) → ∀y ∃x P(x, y) is a tautology i.e. whenever ∃x ∀y P(x, y) is true, ∀y ∃x P(x, y) is also true.

If ∃x ∀y P(x, y) is true, it means there exists an x = c (where c is an arbitrary constant), for which P(c,y) is true for all y, which in turn means that for all y, there exists an x (the constant c), for which P(x,y) is true i.e. ∀y ∃x P(x, y) is true. Hence proved.

2. We need to show that ∃x (P(x) → Q(x)) and ∀x P(x) → ∃x Q(x) always have the same truth value.

L.H.S = ∃x (P(x) → Q(x)) ≡ ∃x (¬P(x) v Q(x)) ≡ ∃x (¬P(x)) v ∃x Q(x) ≡ ¬∀x P(x) v ∃x Q(x) ≡ ∀x P(x) → ∃x Q(x) = R.H.S.

3. False. ∀y ∃x P(x, y) being true means for every y, there is an x (possibly different x for different values of y we choose) such that P(x,y) is true. It doesn't mean that there is a single x which makes P(x,y) true for every y.

4. False. Almost same argument as above.

∀x ∃y P(x, y) being true means for every x, there is a  y (possibly different y for every x), which makes P(x,y) to true. This doesn't mean that there is a single x, which makes P(x,y) for every possible y.

selected by

Related questions