From: vibama@cs.hw.ac.uk (Scott Doan)
Newsgroups: soc.culture.vietnamese
Subject: Re: [MISC] Logic puzzles solutions and respond to the self-claimed logicain, LONG NGUYEN
Date: 31 Jul 92 18:27:34 GMT
Organization: Edinburgh, Scotland


Dear anh Chris,

Eventually I reach you on this trivial problem. I am sorry for having replied
you any sooner. Anyway, your solution below has proved your impressive 
expressive power in explaining and representing the problem. It has indeed
indicated your very logical mind and and highly scientific approach
in thinking and problem solving. I wonder why shouldn't you go into
research and enter the academic world ... You will make yourself
a very good teacher anh Chris ...

Back to the empty set problem, you were right ... I didn't look at
the problem from different perpectives ... I did presume all the readers
have possessed certain knowledge of basic logic and elementary set theory
and it was my mistake. Please accept my apologies !!! Anh Chris, without
your highly clarified interpretation my solution would be meaningless
and a bit dogged. With your representation, the empty set problem
becomes apprehensible to all levels of readers. What a wonderful job. !!!
Thank you very much !!!

Anyway, I would try to make a few comments as below:

   
In article <18764@drutx.ATT.COM> nguyen@drutx.ATT.COM (Christopher Chu) writes:
>
> Dear SCV readers,
>
> I would like to contribute some of my understanding about logic in  this
> post by providing a solution to the elementary set problem stated by anh
> DDK, a Computer Science  Ph.D.  candidate  at  University  of  Edinburg,

Don't call me a Doctor-to-be YET .... I might not be one forever ...:-((((
BTW, did I post a joke on the net not too long ago about those
Phd qualifications ??? Phd is not much better than a P(ile)hD(un) if
you cannot find a job. So does BS(Bag of sh**) or MS(More sh**)....
Just kidding !!!
 

> England,  as  a challenge to anh Long Nguyen, a netter who has seemed to
> possess high interest in logic (?) and who has  already  self-designated
> as a logician on the net.
>
> I realize that the given problem is a  classical  grade-school  exercise
> since,  like DDK and possibly many other people who have been acquainted
> with set theory, I learned this problem right after being introduced  to
> first-order-predicate  calculus  in  a  vietnamese  high  school at 11th
> grade. Also, since no other netter has volunteered to post the solution,
> I would like to take this opportunity to do so. I would appreciate it if
> interested netters would give me comments on my rather clumsy statements
> below.
>
> ----------------------------------------------------------------------
> Problem: prove that any empty set is a subset of a non-empty set.
> ----------------------------------------------------------------------
>
> In mathematics, a "set" is a collection of distinct objects;  an  "empty
> set"  is  *the*  set that contains no object; and a "non-empty set" is a
> set that is not the empty set.
>
> In set theory, to prove that the set A is a subset of set B, we need  to
> show that each and every member of set A is a member of set B.
>
> The statement that is to be proven can be restated as follows.
>
> (a) For all x, if x is a member of the empty set, then x is a member  of
>     a non-empty set.
>
> By  mathematical  logic,  the  above  statement  is  equivalent  to  the
> following:
>
> (b) For all x, either x is not a member of the  empty  set  or  x  is  a
>     member of a non-empty set.
>
> Since (b) is obviously true by definition  of  the  empty  set  and  the
> property of disjunction (e.g., the logical "or" operation), the original
> problem statement "an empty set is a subset of a non-empty set" is  also
> true.
>                                                                    QED
> ----------------------------------------------------------------------
>
> The equivalence between (a) and (b) that I have just stated is one among
> the fundamentals of mathematical logic. By definition, validity of those
> two statements  are  determined  based  on  the  following  truth  table
> (assuming readers have some knowledge about logic).
>
> +---+---+--------+--------+
> | A | B | A -> B | ~A v B |   A is True or False, exclusively
> +---+---+--------+--------+   B is True or False, exclusively
> | F | F |   T    |    T   |
> | F | T |   T    |    T   |   ~A     reads "not A"
> | T | F |   F    |    F   |   A->B   reads "if A then B"
> | T | T |   T    |    T   |   A v B  reads "A or B"
> +---+---+--------+--------+
>
> Basically, the realization that the the empty set is  a  subset  of  any
> non-empty ones in set theory is partially analogous to the understanding
> that adding 0 and a non-zero integer N produces N  in  elementary-school
> arithmetic.  What  more  in  solving  the  empty  set  exercise  is  the
> understanding as why logic should be the way it is.  This  understanding
> is  just one among the very beginning steps of any kind of logic in this
> world.
>
> I  sincerely  believe  that  most  undergraduate  students   who   study
> philosophy and who have some training in techniques of formal reasoning,
> engineering students who have some introduction to boolean algebra in  a
> logic  design  course and students who major in mathematics have already
> grasped the basic concepts of the mathematical logic that underlies  the
> elementary set problem given by anh DDK.
>
> I also realize that a formal understanding of more serious topic such as
> NP-completeness  in  the  complexity  theory  (intuitively,  this  study
> investigates whether there exist problems  that  cannot  be  universally
> solved  by any polynomial time/space algorithms and vice versa) requires
> advanced understanding of much higher level of logic that ought to cover
> most theories of computation and related formal language studies in this

My research is nothing to do with theoretical Computer Science though
I was interested in Computability and Complexity for sometime when I was
an undergraduate. I am sure there are a lot of people on the net who
are doing research in ALGORITHM and COMPLEXITY THEORY will soon respond
to your interest of dicussing the NP completeness. Personally, I have known
a Vietnamese Phd candidate at University College London who has solved
the Assignment Problem and the Traveling saleman Problem in polynomial time.
This is certainly a revolutionary invention in the evolution history
of Complexity theory as it disproves the conjecture P >= NP.
However, his proof is still in the defending stage since he submitted
it nearly a year ago. Though There is no flaw found YET but it hasn't
been approved and published in any theoretical Computer Science Journal...
I will keep all you inform once this revolutionary idea come into teaching
at the University. By then this invention will ruin 
the current famous Cook's theorem validity together with hundred others
and The Complexity Theory is moving into a new era under his Vietnamese name.


> century. I want to indicate that the information in this article is very
> elementary  to  people who have advanced knowledge about logic and by no
> means represents a test to anyone.

It wasn't designated to test anyone anh Chris. Please accept my apologies !!

> Sincerely Yours,
>
> Chris Chu, nguyen@drutx.ATT.COM (Internet), att!drutx!nguyen (UUCP)

Sincerely,`

DDK
Newsgroups: soc.culture.vietnamese