Math 470 Spring ’05

HW #6 Solutions

Section 2.4

6. Assume that A satisfies the LHS. Then either A does not satisfy Y or it satisfies $x j(x). If the latter, there is an a in A such that A satisfies j(a). In either case, A satisfies Y v j(a). So A satisfies $x(Y -> j(x)), which is the RHS.

Assume that A satisfies the RHS $x(Y -> j(x)). Then for some a in A, A satisfies Y v j(a). Then A does not satisfy Y or it satisfies j(a). If the latter, A satisfies $x j(x). So in either case it satisfies Y -> $x j(x), which is the LHS.

If x is free in Y, the LHS still implies the RHS but not conversely. Take A to be the set of natural numbers, Y to be x is even and j(x) to be x > x.

Then A satisfies the RHS, since 3 is even => 3 > 3. But A does not satisfy the LHS, which, universally quantified, says that is x is even there is a number y such that y > y.

7. Assume that A satisfies the LHS. Then either A does not satisfy $x j(x) or it satisfies Y. If the former then, no a in A satisfies j(a). In either case, every a in A satisfies j(a) ->Y. So A satisfies "x(j(x) -> Y), which is the RHS.

Assume that A satisfies the RHS "x(j(x) ->Y). Then every a in A satisfies j(a) ->Y. Then A does not satisfy j(a) or it satisfies Y. If, A satisfies j(a) for any a, it satisfies Y. So A satisfies $x j(x) -> Y, which is the LHS.

If x is free in Y, the LHS still implies the RHS but not conversely. Take A as above, Y to be x is even and j(x) to be x is a multiple of 4.

Then A satisfies the RHS, since if x is a multiple of 4, it is even. But A does not satisfy the LHS, which, universally quantified, says that is if there is any multiple of 4, then every number is even.

Section 2.6

1. F (($x(j(x) v y(x)) <-> ($xj(x) v $xy(x))

/ \

T $x(j(x) v y(x)) F($x(j(x) v y(x))

F ($xj(x) v $xy(x)) T ($xj(x) v $xy(x))

T j(c) v y(c) / \

F ($xj(x)) T($xj(x)) T$xy(x))

F $x y(x) T y(d) Ty(e)

F j(c) F(j(d) v y(d)) F(j(e) v y(e))

F y(c) F(j(d)) F(j(e)

/ \ F(y(d)) F(y(e))

Tj(c) Ty(c) X X

X X

2. . F (("x(j(x) ^ y(x)) <-> ("xj(x) ^ "xy(x))

/ \

T "x(j(x) ^ y(x)) F("x(j(x) ^ y(x))

F ("xj(x) ^ "xy(x)) T ("xj(x) ^ "xy(x))

/ \ T "xj(x)

F"xj(x) F"xy(x) T "x y(x)

Fj(c) Fy(d) F (j(e) ^ y(e))

T(j(c)^y(c) Tj(d)^y(d) / \

T(j(c) ) Tj(d) F(j(e) Fy(e)

Ty(c) Ty(d) Tj(e) Ty(e)

X X X X

4. F(j ^ $x(y(x) ) -> $x(j ^ y(x)

T (j ^ $x(y(x) )

F $x(j ^ y(x)

Tj

T $x(y(x) )

T y(c)

F(j ^ y(c) (x not free in j)

/ \

Fj F y(c)

X X

7. F( Ø$xj(x) -> "xØj(x))

T Ø$xj(x)

F "xØj(x)

F Øj(c)

T j(c)

F $xj(x)

Fj(c)

X

8. F("xØj(x) -> Ø$xj(x))

T("xØj(x))

F(Ø$xj(x))

T $xj(x)

Tj(c)

T("xØj(x))

TØj(c)

Fj(c)

X

9. . F($xØj(x) -> Ø"xj(x))

T($xØj(x))

F(Ø"xj(x))

T "xj(x)

TØj(c)

Fj(c)

T("xj(x))

Tj(c)

X

10. F($x(j(x) -> y) -> ("xj(x) ->y)

T($x(j(x) -> y)

F("xj(x) ->y)

T j(c) -> y ( x not free in y)

T"xj(x)

F y

/ \

F j(c) Ty

T"xj(x) X

T j(c)

X