February 22nd, 2010, 08:42 AM  #1 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Sets and Predicate logic
Hi, I have two tasks here about sets and predicate logic. The problem here is that I really don't understand the connection between predicate logic and sets. These are the problems I am facing: 1) Find a statement in predicate logic, where you can use the symbols ? and ? to express that a) D = B ? C b) E = B ? C 2) Show how you can express with predicate logic that there is a "largest" element and a "smallest" element in a set, by using predicates of the form C ? D I would really appreciate if someone who knows about this kind of math can help me out here. I will be more than happy even if you only can help me with one of the tasks 
February 22nd, 2010, 10:36 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Sets and Predicate logic
On my first reading I thought you had "propositional logic" rather than "predicate logic" and I was concerned: I don't know how to show a) without quantifiers. But with, it can be done. Informally: "C is a subset of D; B is a subset of D; for all subsets U of D, there exists a subset V of U with V in B or V in C." Alternately: "C is a subset of D; B is a subset of D; for all S, if B is a subset of S and C is a subset of S, D is a subset of S." b) can be done with just propositional logic, or you can do it like the above. I'll leave formalizing my statements to you (especially since I don't know the formal language you're working with). I don't understand what is meant by the quoted words in 2. 
February 22nd, 2010, 01:33 PM  #3 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Re: Sets and Predicate logic
Thanks for the answer, So If I understand right.... I can write task 1a) with the language that I am using like this, right? ?B ?C ?D ( B ? D and C ? D) In words this will be something like: "For all B and all C, there exists a D, where B is a subset of D and C is a subset of D" If I am not wrong, the symbols ? and ? should be used everywhere in the world, but I dont know, maybe you use other symbols to formalize it. As for task 1b), can you formalize it for me? Because I can't do it exactly like in a) because now we are talking about ? and not ? 
February 22nd, 2010, 01:49 PM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Sets and Predicate logic Quote:
 
February 22nd, 2010, 02:23 PM  #5 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Re: Sets and Predicate logic
Hmm.... so how do I formalize it then? Maybe it can be formalized as easy as: ?B ?C ?D ( (B ? C) ? D) This looks really weird though... 
February 22nd, 2010, 02:51 PM  #6  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Sets and Predicate logic Quote:
When you write "?B ... foo(b)", this is exactly the same as "?X ... foo(X)" (provided you change all the Bs in ... to X and that you don't use X elsewhere). In particular, "?B ..." says nothing about the value of B outside that expression. This isn't what you want. You want the variables B, C, and D to appear unbound, because you want the particular values that they may have ({1}, {}, and {} in my example), rather than making statements about *any* sets (even though you confusingly name those "any sets" B, C, and D). Suppose A = {1, 2, 3, 4, 5, 6, 7}. Then "A = {2}" is false, but "?A  A = {2}" is true since there does exist such a set, namely {2}. "?A  A = {2}" is exactly the same as "?B  B = {2}" or "?Y  Y = {2}".  
February 22nd, 2010, 05:00 PM  #7  
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: Sets and Predicate logic
For 1, what you want is a statement about subsets of B, C and D Something like "?X(X?B=>X?D)" (This says that if X is a subset of B then X is a subset of D... which really just means B is a subset of D). Look at the statement I made right there. It can be modified in a pretty "immediate" way to get both intersections and unions. Quote:
Quote:
 
February 22nd, 2010, 06:32 PM  #8  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Sets and Predicate logic Quote:
 

Tags 
logic, predicate, sets 
Search tags for this page 
sets predicate form,the predicate form of a set,writing sets in predicate form,what is the predicate form for a set,predicate form sets,predicate form and enumerated form sets,write down a predicate to formalize the statement,predicated form of set,how to write predicate form in set,predicate calculus definitions of sets,predicate form of sets
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
predicate logic  skaur  Applied Math  1  January 6th, 2014 05:51 PM 
Predicate Logic  mohitpd  Applied Math  0  October 26th, 2013 07:45 PM 
Predicate Logic  pavankumar.thati  Applied Math  0  April 16th, 2013 09:26 AM 
Resolution in Predicate logic  Leila  Applied Math  9  January 4th, 2011 05:54 AM 
Predicate Logic translation. >_<  pinkcheese  Applied Math  0  November 22nd, 2010 08:40 PM 