Prove no odd integer can be expressed as 4k+1 and 4j-1

[Aziza]

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) = ($\exists$j$\in$$Z$)(x=4j-1)
R(x) = ($\exists$k$\in$$Z$)(x=4k+1)

Then literally I understand the above statement as:
$\neg$[$\exists$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\wedge$ R(x) ) ]

But is this the same thing as:
[$\forall$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\vee$ 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
[$\forall$x$\in$$Z$][ P(x)$\wedge\neg$Q(x)$\Rightarrow$R(x) ) ] , so in the proof you can just assume P(x)$\wedge\neg$Q(x) and use that to get to R(x)..

 

[micromass]

Then literally I understand the above statement as:
$\neg$[$\exists$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\wedge$ R(x) ) ]

That is how I understood the statement.

But is this the same thing as:
[$\forall$x$\in$$Z$][ P(x)$\Rightarrow$( Q(x) $\vee$ R(x) ) ]
??

No, they are not the same thing. Can you explain why you think they are the same think??

 

[tt2348]

Suppose not, suppose there IS some n where n=4k+1=4j-1
then it stands to reason that (4j-1)-(4k+1)=0
see what you can conclude from there :-)

 

[Aziza]

That is how I understood the statement.



No, they are not the same thing. Can you explain why you think they are the same think??

I realized that in [∀x∈Z][ P(x)⇒( Q(x) ∨ R(x) ) ] , for the 'or' I meant the exclusive or, so I actually mean:
[∀x∈Z] { [ P(x)∧¬Q(x)]⇒R(x) ] ∧ [ P(x)∧Q(x)]⇒¬R(x) ] }
For the given P,Q and R this can easily be proven true.

So since P is true and P(x)⇒( Q(x) ∨ R(x) ) is true, then ( Q(x) ∨ R(x) ) must be true (again meaning exclusive or).

So we know that exactly one of Q or R is true and exactly one is false, so Q(x) ∧ R(x) must always be false, and so assuming P is true, ¬[∃x∈Z][ P(x)⇒( Q(x) ∧ R(x) ) ] is always true.

So since both statements are always true, they are equivalent...

 

[tiny-tim]

"Prove that there is no odd integer that can be expressed in the form 4j-1 and 4k+1 for integers j and k."

why make it so complicated?

i'm with tt2348's method …

Suppose not, suppose there IS some n where n=4k+1=4j-1
then it stands to reason that (4j-1) - (4k+1)=0
see what you can conclude from there :-)

 

[Aziza]

Suppose not, suppose there IS some n where n=4k+1=4j-1
then it stands to reason that (4j-1)-(4k+1)=0
see what you can conclude from there :-)

Then 2(j-k)=1, so j-k must be 1/2, so j and k cannot both be integers as required :)
My question however was not how to prove, just how the statement to be proved could possibly be restated

 

[Aziza]

why make it so complicated?

i'm with tt2348's method …

haha idk my book likes complications i guess lol. but guys i know how to prove this, I am just more interested in how this statement can be equivalently restated and if i made any errors in my second post in trying to show that the literal logical translation of the initial statement is equivalent to my interpretation

 

[D H]

why make it so complicated?

Because they're pure math people?? Their notion of a good time appears to involve things like self-inflicted use of torture devices straight out of the Inquisition. To have a truly jolly good time they have to go well beyond crude Torquemada-like torture devices. Inverting universal and existential quantifiers, now that's a good time.

i'm with tt2348's method …

But that's not fun!

 

[tt2348]

Using logical restrictions.. you can drop the P(x) requirement.
since regardless, even or odd, there is no integer such that x=4k-1=4j+1
so it boils down to x is an integer=>~(Q(x)&R(x))
=>(~q)v(~r)

 

[tt2348]

or it's converse, Q(x)&R(X)=> x isn't an integer

 

[Aziza]

Using logical restrictions.. you can drop the P(x) requirement.
since regardless, even or odd, there is no integer such that x=4k-1=4j+1
so it boils down to x is an integer=>~(Q(x)&R(x))
=>(~q)v(~r)

Right, but every odd integer is either R or Q, but not both and not neither, am i right? That's what I was trying to prove in my second post.

 

[tt2348]

yes, it is indeed an exclusive or.
But you need to be careful with your formulation
F=>F
is true
also
F=>T
is true
Generally, logical propositions alone are not enough to be mathematically rigorous, and most professors want something using significantly less notation.

 

[vela]

Right, but every odd integer is either R or Q, but not both and not neither, am i right? That's what I was trying to prove in my second post.

That's certainly true, but wouldn't the original statement be true even if neither R nor Q were true? It seems like you're adding an additional condition by saying one of them has to be true.