# Is that proof correct?

1. Dec 19, 2008

### poutsos.A

a) AxB =Φ <====> [ (a,b)εAxB <-----> (a,b)εΦ] <=====>[(aεA & bεB)<------>(aεΦ & bεΦ)] <====>[(aεA----->aεΦ) & (bεB------>bεΦ)] ======>(aεA----->aεΦ)====> A= Φ ====> A=Φ v B=Φ.

2. Dec 19, 2008

### Hurkyl

Staff Emeritus
What are the individual steps?

Incidentally, it's clear that you've made a mistake: along the way, you asserted that

AxB = Φ ====> A = Φ

but it's easy to construct counterexamples....

3. Dec 19, 2008

### farleyknight

(aεA & bεB) <------> (aεΦ & bεΦ)

If A x B = Φ then a cannot be included in Φ, because Φ is a set of ordered pairs.

What's the original problem?

4. Dec 19, 2008

It looks like the original problem is to prove $$A \times B = \varnothing \Longleftrightarrow A = \varnothing \vee B = \varnothing$$. He is writing Φ to mean the empty set.

Last edited: Dec 20, 2008
5. Dec 19, 2008

### poutsos.A

6. Dec 19, 2008

### poutsos.A

Also <====> means double implications or equivalent

7. Dec 20, 2008

### poutsos.A

Actually to be 100% correct the above is a proof of:

$$AxB = \varnothing \rightarrow A = \varnothing \vee B = \varnothing$$

it is also an answer to your posts concerning neighborhoods e.t.c e.t.c

8. Dec 20, 2008

The most obvious way to me to prove that would be to prove the contrapositive: if A and B are both nonempty, then A × B is nonempty.

9. Dec 20, 2008

### poutsos.A

I never asserted that ,but i proved that:

I started by assuming AxB = Φ and then by using double implications supported by definitions and a propositional logic law [( p&q <-----> r&s)<=====> (p---->r)&(q----->s)] i ended up with [(aεA----->aεΦ)& ( bεB------->bεΦ)] .From here i used addition elimination ( a law of propositional logic ) to conclude (aεA----->aεΦ) ,which implies that A IS A subset of Φ ,and since Φ is a subset of A then A= Φ. Now from here i used disjunction introduction ( a law in propositional logic :p====>p v q ) to conclude : A = Φ v B = Φ

10. Dec 20, 2008

### Hurkyl

Staff Emeritus
That isn't valid rule of inference. Here is a truth assignment v that invalidates it:

(I'm abbreviating true and false as T and F, respectively)

v(p) = T, v(q) = F, v(r) = F, v(s) = T

v(p&q <---> r&s) = (T&F <---> F&T) = (F <---> F) = T

v((p-->r)&(q-->s)) = (T-->F)&(F-->T) = F&T = F

Because these formulas have different truth values under the given truth assignment,
[( p&q <-----> r&s)<=====> (p---->r)&(q----->s)] is not valid in Boolean logic.

11. Dec 20, 2008

You claim you proved that $$A \times B = \varnothing \Longrightarrow A = \varnothing$$, but that is clearly false (so the proof is invalid somewhere): take A to be any nonempty set and B to be the empty set, and you have a counterexample. What Hurkyl posted above explains where your proof went wrong.

12. Dec 20, 2008

### poutsos.A

There is no Boolean Logic but Boolean Algebra and propositional logic.

There is no theorem to support your argument .

Besides all proofs in mathematics are syntactical in character and not semantical .

Your argument is semantical ,because it uses true and false values and thus non valid

13. Dec 20, 2008

### Hurkyl

Staff Emeritus
Ah, but there is: propositional logic is sound: the rules of inference in propositional logic cannot prove a result that is semantically invalid.

More generally, given a set H of hypotheses and a conclusion C, we have the following theorem:
Theorem: H syntactically implies C if and only if H semantically implies C​
One direction of this theorem is soundness, the other completeness. This is also a theorem of (Boolean) first-order logic in general, not merely of (Boolean) propositional logic.

Intuitionistic logic (and other logics) use different rules of inference for propositional logic and for first-order logic. When referring to classical propositional and first-order logic, I attach the adjective 'Boolean' for added specificity. I'm pretty sure this is an established convention.

Incidentally, the above is irrelevant to the hole in your derivation -- the inference you tried to use is simply not one of the basic rules of inference of propositional logic. The semantic proof I gave was meant to make that fact more obvious.

Last edited: Dec 20, 2008
14. Dec 21, 2008

### poutsos.A

The theorem in concern is:

.......$$\vdash \forall A\forall B( A\times B =\varnothing \rightarrow A=\varnothing \vee B=\varnothing)$$

Now what you actually did is that in the line of my proof where $$A=\varnothing$$ you discharged the hypothesis $$A\times B = \varnothing$$ which is necessary to start the deduction theorem ,and you took the conclusion $$A\times B =\varnothing\rightarrow A = \varnothing$$ and generalized it resulting in the formula:

$$\forall A\forall B(A\times B =\varnothing\rightarrow A = \varnothing)$$

Then in this formula one is allowed to use values of A and B ,and that is what you exactly did by letting A=A And B=Φ .

But i never proved that

15. Dec 21, 2008

### Hurkyl

Staff Emeritus
What the heck are you talking about? That your argument asserts AxB =Φ ====> A= Φ is as plain as day.

16. Dec 21, 2008

### poutsos.A

Do you know what a deduction theorem is?

Do you know how is that theorem used in a proof ??

Do you know what generalization is and under what rules is applied in a proof ??

Do you know what is the meaning of "discharging the hypothesis" ???

My argument asserts that AxB = Φ ====> Α=Φ ,But not that A CAN be a non empty set and B the empty set

17. Dec 21, 2008

### poutsos.A

So the only theorem that can support your argument is the above theorem.

But the above theorem is a metathoerem in the metalanguage and not a theorem in the object language.

who is to check the validity of that theorem.By what means??

If you want to use an adjective for added specificity as you claim ,the proper name is Aristotelean logic and not Boolean, because the founder of the two values logic is Aristotle and not Boole.

On the other hand if you contend and i quote: " Incidentally, the above is irrelevant to the hole in your derivation -- the inference you tried to use is simply not one of the basic rules of inference of propositional logic"................................Give me a catalog of all the rules of inference and then i will accept your claim.

18. Dec 21, 2008

Are you trying to argue that your proof is correct? Do you claim that it is correct?

Where are you going with all this?

19. Dec 21, 2008

### Hurkyl

Staff Emeritus