# Homework Help: Prove no odd integer can be expressed as 4k+1 and 4j-1

1. Jul 6, 2012

### 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)..

2. Jul 6, 2012

### micromass

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??

3. Jul 6, 2012

### 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 :-)

Last edited: Jul 6, 2012
4. Jul 6, 2012

### Aziza

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...

5. Jul 6, 2012

### tiny-tim

why make it so complicated?

i'm with tt2348's method …

6. Jul 6, 2012

### Aziza

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

7. Jul 6, 2012

### Aziza

haha idk my book likes complications i guess lol. but guys i know how to prove this, im 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

Last edited: Jul 6, 2012
8. Jul 6, 2012

### D H

Staff Emeritus
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.

But that's not fun!

9. Jul 6, 2012

### 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)

10. Jul 6, 2012

### tt2348

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

11. Jul 6, 2012

### Aziza

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.

12. Jul 6, 2012

### 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.

13. Jul 6, 2012

### vela

Staff Emeritus
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.