- #1
Aziza
- 190
- 1
I am preparing for my Fall bridge to abstract math course and came across following problem:
"Prove that there is no odd integer that can be expressed in the form 4j-1 and 4k+1 for integers j and k."
If you let
P(x) = "x is odd"
Q(x) = ([itex]\exists[/itex]j[itex]\in[/itex][itex]Z[/itex])(x=4j-1)
R(x) = ([itex]\exists[/itex]k[itex]\in[/itex][itex]Z[/itex])(x=4k+1)
Then literally I understand the above statement as:
[itex]\neg[/itex][[itex]\exists[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\Rightarrow[/itex]( Q(x) [itex]\wedge[/itex] R(x) ) ]
But is this the same thing as:
[[itex]\forall[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\Rightarrow[/itex]( Q(x) [itex]\vee[/itex] R(x) ) ]
??
If you logically simplify both of these statements, they turn out to not be logically equivalent, but they both seem to equally fit the meaning of the initial statement. The latter just seems to have a simpler formal proof because it is equivalent to
[[itex]\forall[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\wedge\neg[/itex]Q(x)[itex]\Rightarrow[/itex]R(x) ) ] , so in the proof you can just assume P(x)[itex]\wedge\neg[/itex]Q(x) and use that to get to R(x)..
"Prove that there is no odd integer that can be expressed in the form 4j-1 and 4k+1 for integers j and k."
If you let
P(x) = "x is odd"
Q(x) = ([itex]\exists[/itex]j[itex]\in[/itex][itex]Z[/itex])(x=4j-1)
R(x) = ([itex]\exists[/itex]k[itex]\in[/itex][itex]Z[/itex])(x=4k+1)
Then literally I understand the above statement as:
[itex]\neg[/itex][[itex]\exists[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\Rightarrow[/itex]( Q(x) [itex]\wedge[/itex] R(x) ) ]
But is this the same thing as:
[[itex]\forall[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\Rightarrow[/itex]( Q(x) [itex]\vee[/itex] R(x) ) ]
??
If you logically simplify both of these statements, they turn out to not be logically equivalent, but they both seem to equally fit the meaning of the initial statement. The latter just seems to have a simpler formal proof because it is equivalent to
[[itex]\forall[/itex]x[itex]\in[/itex][itex]Z[/itex]][ P(x)[itex]\wedge\neg[/itex]Q(x)[itex]\Rightarrow[/itex]R(x) ) ] , so in the proof you can just assume P(x)[itex]\wedge\neg[/itex]Q(x) and use that to get to R(x)..