PhilosophyGround >> Logic Question
12/15/05 1:05 AM  
winnidon
Edited: 15Dec05 Member Since: 11/30/2002 Posts: 123 
Does anyone know how to go about answering this?
Let P be the set of total functions from the set of positive integers to the set {0}, and let Q be the set of total and partial functions from the set of positive integers to the set {0}. Argue that P is enumerable and Q isn't.

12/16/05 6:02 AM  
FudoMyoo
Edited: 16Dec05 Member Since: 01/01/2001 Posts: 12730 
too advanced for me. I think you need to have studied set theory in order to solve this, if you only have studied propositional and predicate logic (with identy and relations), it wont be enough to deal with your question. Maybe Dogbert knows how to solve it? btw, with {0}, do you mean the empty set? 
12/16/05 9:38 AM  
Dogbert
Edited: 16Dec05 Member Since: 01/01/2001 Posts: 15073 
Since all total functions map all positive integers to 0, there is only one such funtion. A oneelemnt set is denumerable (depending on the definition). You can identify a partial function on the set of positive Integers with a unique subset of the set of positive integers, the domain of that function. So the set of all such partial functions is isomorphic to the powerset of the set of positive integers, which is uncountable by Cantor's theorem. 
12/16/05 12:09 PM  
winnidon
Edited: 16Dec05 Member Since: 11/30/2002 Posts: 126 
Hey thanks Dogbert! (and Fudo for acknowledging the question) Dogbert...I believe I understand what you are saying, however, I'm not sure how to 'argue' for the results. Is it enough just to show that P is enumerable by giving a function i.e., f(i)=i? And for Q: The set Q total & partial functions from the set of positive integers is not enumerable. Suppose Q is enumerable So there is a list of all positive integers Q1, Q2,... Form Q* such the n is a member Q* iff n is not a member of Qn So Q* is Qn for some n; So n is a member of Q* iff n is a member if Qn; So n is a member of Qn iff n is not a member of Qn. QEA 
12/16/05 1:49 PM  
Dogbert
Edited: 16Dec05 Member Since: 01/01/2001 Posts: 15074 
"Is it enough just to show that P is enumerable by giving a function i.e., f(i)=i?" There is only one total function that maps all positive integers to a element of {0}, namely the function f(n)=0. So, what matters is unqueness of that function. Your argument about Q is basically correct. But "So there is a list of all positive integers Q1, Q2,..." These are not integers but sets or partial functions. You also have to show their equivalence first. 
12/16/05 2:10 PM  
winnidon
Edited: 16Dec05 Member Since: 11/30/2002 Posts: 127 
"So, what matters is unqueness of that function." How does one go about showing this? "You also have to show their equivalence first." So, am I right to think that I need to define an onto and onetoone function 'f' from the set Q to the set of total and partial functions of all positive integers? Thanks SO MUCH for the help! 
12/16/05 3:11 PM  
Dogbert
Edited: 16Dec05 Member Since: 01/01/2001 Posts: 15075 
Yes. And since the range of the function is fixed with only one element, you can identify the functions with their domain. Feels good to help. 
12/16/05 4:33 PM  
winnidon
Edited: 16Dec05 Member Since: 11/30/2002 Posts: 128 
Got it  Thanks again Dogbert. I have a metalogic final on monday so the help is much appreciated! 
12/17/05 8:29 AM  
Dogbert
Edited: 17Dec05 Member Since: 01/01/2001 Posts: 15076 
Good luck! (don´t ask me what wishing that means analytically...) 
Reply Post
You must log in to post a reply. Click here to login.