Proving $(A\cap B)\cup(B\cap X')=0$ Equivalence

[solakis1]

Prove that:
$(A\cap B)\cup(B\cap X')=0$ is equιvalent with

$B\subseteq A'$ and $B\subseteq X\subseteq A'$

0 is for the emty set and $X'$ is for the complement of $X$

 

[solakis1]

Sorry there is a typo
write $A\cap X$ in the place of $A\cap B$

 

[HOI]

First, the UNION of two sets is empty if and only if both sets are empty. So you have immediately that [math]A\cap X= 0[/math] and [math]B\cap X'= 0[/math]. Saying that [math]B\cap X'= 0[/math] means that [math]B\subseteq X[/math]. And saying that [math]A\cap X= 0[/math] means that [math]X\subset A'[/math]. Together those give [math]B \subseteq X \subseteq A'[/math] which immediately implies [math]B\subset A'[/math].

 

[solakis1]

How do you prove that: $B\cap X'=0$ implies $B\subseteq X$ and then the opposite

Also how do you prove: $(A\cap X)=0\Leftrightarrow X\subseteq A'$

 

[HOI]

The standard method to prove [math]P\subseteq Q[/math] is to start "if [math]p\in P[/math]" and then use the definitions and properties of P and Q to conclude that "[math]p\in Q[/math]".

Here, if [math]p\in B[/math] then, since [math]B\cap X'= 0[/math] p is not in X' so is in X. I don't know what you mean by "the opposite".

For the last, to prove [math]X\subseteq A'[/math], start with [math]x\in X[/math]. Then, since [math]A\cap X= 0[/math], x is not in A so [math]x\in A'[/math].

 

[solakis1]

The standard method to prove [math]P\subseteq Q[/math] is to start "if [math]p\in P[/math]" and then use the definitions and properties of P and Q to conclude that "[math]p\in Q[/math]".

Here, if [math]p\in B[/math] then, since [math]B\cap X'= 0[/math] p is not in X' so is in X. I don't know what you mean by "the opposite".

For the last, to prove [math]X\subseteq A'[/math], start with [math]x\in X[/math]. Then, since [math]A\cap X= 0[/math], x is not in A so [math]x\in A'[/math].

if [math]p\in B[/math] then, since [math]B\cap X'= 0[/math]$\Rightarrow ((p\in B\wedge p\in X')\Rightarrow x\in 0)$
And not just p does not belong to X' hence p belongs to X
This totally wrong

 

[Evgeny.Makarov]

That's not totally wrong. Writing $p\notin X'$ does follow from $p\in B$ and just skips a few trivial proof steps.

 

[solakis1]

That's not totally wrong. Writing $p\notin X'$ does follow from $p\in B$ and just skips a few trivial proof steps.

Did i say that??

 

[Evgeny.Makarov]

This totally wrong

Did i say that??

Yes, you did concerning Country Boy's reasoning in post #5.

 

[solakis1]

Sorry for the misundertanding ,i did not look properly at your post.
Anyway when i said "this is totally wrong" i ment that it is totally wrong to come to a conclusion without showing the steps that led you to such a conclusion.

When we say in mathematics prove something we mean show the steps that lead you to that "something"
"Trivial" and "obvious" sometime in mathematics can be extremely difficult
Anyway which are the trivial steps

 

[Evgeny.Makarov]

Here, if $\displaystyle p\in B$ then, since $\displaystyle B\cap X'= 0$, $p$ is not in $X'$ so is in $X$.

I think that this reasoning would indeed be considered trivial in almost any context, and only in mathematical logic it would make sense to ask about axioms or inference rules that justify it.

if [math]p\in B[/math] then, since [math]B\cap X'= 0[/math]$\Rightarrow ((p\in B\wedge p\in X')\Rightarrow x\in 0)$

You are right. If we denote $p\in B$ by $P$ and $p\in X$ by $Q$, then, since $x\in\emptyset$ is false by definition of $\emptyset$, concluding $p\in X$ from the formulas above amounts to showing that $P\land (P\land \neg Q\to\bot)\to Q$ is derivable (or is a tautology). How this is shown depends on the logical calculus. But this is a trivial conclusion in the sense that it does not require anything (any facts about mathematical concepts like sets or functions) other than propositional logic. I believe that even most proof assistants can discharge such proof goals automatically.

 

[solakis1]

I think that this reasoning would indeed be considered trivial in almost any context, and only in mathematical logic it would make sense to ask about axioms or inference rules that justify it.

You are right. If we denote $p\in B$ by $P$ and $p\in X$ by $Q$, then, since $x\in\emptyset$ is false by definition of $\emptyset$, concluding $p\in X$ from the formulas above amounts to showing that $P\land (P\land \neg Q\to\bot)\to Q$ is derivable (or is a tautology). How this is shown depends on the logical calculus. But this is a trivial conclusion in the sense that it does not require anything (any facts about mathematical concepts like sets or functions) other than propositional logic. I believe that even most proof assistants can discharge such proof goals automatically.

OK Let me prove:
$(B\cap X')=0\Leftrightarrow B\subseteq X$

First for the $\Rightarrow$

Proof:
1) Let $(B\cap X')=0$

2) But $(B\cap X')=0\Leftrightarrow \forall p(\neg (p\in(B\cap X'))$.....A theorem in set theory

3) Hence $\forall p(\neg (p\in(B\cap X'))$

4) Thus $\neg (p\in (B\cap X'))$

5) But $p\in (B\cap X') \Leftrightarrow p\in B\wedge \neg p\in X$.....A theorem in set theory

6) Hence $\neg (p\in (B\cap X')) \Leftrightarrow \neg p\in B\vee p\in X$

7) Thus from 4 and 6 and using Modus Ponens we have: $\neg p\in B\vee p\in X$

8) And finally using material implication we have: $p\in B\Rightarrow p\in X$

And that's part of the proof leaving out the $\Leftarrow$ proof

Also i did not mention explicitly all the laws of logic taking place

Now do you think that all the above proof can be concetrated in one sentence:

"from $p\in B$ and from $B\cap X'=0 $ since p does not belong to $X'$ ,p belongs to $X$??"

 

[Evgeny.Makarov]

Now do you think that all the above proof can be concetrated in one sentence:

"from $p\in B$ and from $B\cap X'=0 $ since p does not belong to $X'$ ,p belongs to $X$??"

Unfortunately, yes. One simply has to imagine $X$ as a circle. Then $B\cap X'=0$ means that $B$ has no elements outside of that circle; therefore, $B$ is located inside it.

In my opinion, most mathematicians are not interested in discussing whether a proof of some fact should take 1 or 5 pages, or whether it can be written using 1000 or 5000 logical inferences. The difference between 1 and 5 pages can be significant (and there are many published papers that simplify proofs of already known facts), but only if the writing style is similar. If one paper uses a heavy result such as Fermat's last theorem and another offers a purely arithmetic proof, this is noteworthy. But if somebody argues that the proof style is too dense and it has to be expanded five times without introducing any new ideas, I believe few people would be interested. Mathematicians rely a lot on intuition, which is able to correctly determine whether certain statements are true or false. This intuition develops with training and is able to handle more and more complicated claims.

This is not to say that studying formal proofs is meaningless. I heard a story about one professor who wanted to be a pilot as a child, so he tried reading books about aerodynamics. He realized that he needed to know differential equations, for which in turn he had to know calculus. Then he encountered axioms of real numbers, had some questions about them and decided to study them in depth. He has been doing mathematical logic ever since. Some people find meaning in applying aerodynamics to creating better planes while others study the foundations of things.

Here is a quote from Bertrand Russell's book "Introduction to Mathematical Philosophy".

Mathematics is a study which, when we start from its most familiar portions, may be pursued in either of two opposite directions. The more familiar direction is constructive, towards gradually increasing complexity: from integers to fractions, real numbers, complex numbers; from addition and multiplication to differentiation and integration, and on to higher mathematics. The other direction, which is less familiar, proceeds, by analysing, to greater and greater abstractness and logical simplicity...

We may state the same distinction in another way. The most obvious and easy things in mathematics are not those that come logically at the beginning; they are things that, from the point of view of logical deduction, come somewhere in the middle. Just as the easiest bodies to see are those that are neither very near nor very far, neither very small nor very great, so the easiest conceptions to grasp are those that are neither very complex nor very simple (using “simple” in a logical sense). And as we need two sorts of instruments, the telescope and the microscope, for the enlargement of our visual powers, so we need two sorts of instruments for the enlargement of our logical powers, one to take us forward to the higher mathematics, the other to take us backward to the logical foundations of the things that we are inclined to take for granted in mathematics.

So constructing formal inferences is OK, but it should preferably lead to something more advanced rather than being simply a hobby. For example, the existing logical calculi (natural deduction, sequent calculus, Hlbert's system and so on) are proved to be sound and complete, i.e., every proof can be expressed in them, albeit sometimes awkwardly. For this reason many people are not interested in optimizing them or creating calculus that better resembles human reasoning. But your example above shows that people don't think in terms of modus ponens; perhaps they have some visual intuition that provides a much shorter explanation. Can this intuition be formalized and taught to computers? Another option is to study proof assistants such as Coq or Isabelle. You may like working with them because it raises questions that are usually skipped in informal proofs.