My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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
Zhai is offline  
 
February 22nd, 2010, 10:36 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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 ?
Zhai is offline  
February 22nd, 2010, 01:49 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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...
Zhai is offline  
February 22nd, 2010, 02:51 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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}".
CRGreathouse is offline  
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 ?
cknapp is offline  
February 22nd, 2010, 06:32 PM   #8
Global Moderator
 
CRGreathouse's Avatar
 
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).
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
logic, predicate, sets



Search tags for this page
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





Copyright © 2019 My Math Forum. All rights reserved.