Proof Correct: AxB = Φ and A=Φ v B=Φ

[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=Φ.

 

[Hurkyl]

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

 

[farleyknight]

You made a mistake here:

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

 

[adriank]

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.

 

[poutsos.A]

That is correct adriank ,thanx

 

[poutsos.A]

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

 

[poutsos.A]

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

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

 

[adriank]

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.

 

[poutsos.A]

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

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 = Φ

 

[Hurkyl]

and a propositional logic law [( p&q <-----> r&s)<=====> (p---->r)&(q----->s)]

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.

 

[adriank]

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.

 

[poutsos.A]

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.

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

 

[Hurkyl]

There is no theorem to support your argument .

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.

There is no Boolean Logic but Boolean Algebra and 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.

 

[poutsos.A]

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.

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

 

[Hurkyl]

But i never proved that

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

 

[poutsos.A]

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

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

 

[poutsos.A]

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.

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.

 

[adriank]

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

Where are you going with all this?

 

[Hurkyl]

Your original question has been answered, and additional information supplied to help you understand the answer. If you're going to be willfully obtuse and argumentative about it, then I'm going to lock the thread.

Though I have to wonder; why ask a question if you don't intend to listen to the answer?

 

[poutsos.A]

Why you are not interested in learning something you maybe don't know?