My Math Forum Sets and Predicate logic

 Applied Math Applied Math Forum

 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:
 Originally Posted by Zhai 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"
"?B ?C ?D ( B ? D and C ? D)" means "Given two sets, you can find a third that contains both as subsets". This is true. But you don't want something that is always true: you want something that is true for only some choices of B, C, and D. If you have B = {1} and C = D = {} then "D = B ? C" is false but "?B ?C ?D ( B ? D and C ? D)" is true.

 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:
 Originally Posted by Zhai 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...
I think the point of the exercise was to avoid using the ? symbol. If you're allowed to use it, then the best way to write a) would be "D = B ? C".

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:
 Originally Posted by Zhai 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
What is the definition of "largest" and "smallest" in this question? Cardinality? Some sort of subset ordering? Are they sets of numbers, and we are using the natural ordering?

Quote:
 Originally Posted by CRGreathouse b) can be done with just propositional logic
Really? I'm not seeing this. The only ideas that come to mind aren't quite strong enough to get the intersection, if our only relation symbol is ?

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:
Originally Posted by cknapp
Quote:
 Originally Posted by CRGreathouse b) can be done with just propositional logic
Really? I'm not seeing this. The only ideas that come to mind aren't quite strong enough to get the intersection, if our only relation symbol is ?
Yeah, you're probably right. I thought I had it for some reason, but now I can't see how to get anything better than something in the intersection (which is immediate).

 Tags logic, predicate, sets

,

,

,

,

,

,

,

,

,

,

### predicate form of sets

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top