UnderGround Forums
 

PhilosophyGround >> Logic Question


12/15/05 1:05 AM
Ignore | Quote | Vote Down | Vote Up
winnidon
Send Private Message Add Comment To Profile

Edited: 15-Dec-05
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
Ignore | Quote | Vote Down | Vote Up
FudoMyoo
Send Private Message Add Comment To Profile

Edited: 16-Dec-05
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
Ignore | Quote | Vote Down | Vote Up
Dogbert
Send Private Message Add Comment To Profile

Edited: 16-Dec-05
Member Since: 01/01/2001
Posts: 15073
Since all total functions map all positive integers to 0, there is only one such funtion. A one-elemnt 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
Ignore | Quote | Vote Down | Vote Up
winnidon
Send Private Message Add Comment To Profile

Edited: 16-Dec-05
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
Ignore | Quote | Vote Down | Vote Up
Dogbert
Send Private Message Add Comment To Profile

Edited: 16-Dec-05
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
Ignore | Quote | Vote Down | Vote Up
winnidon
Send Private Message Add Comment To Profile

Edited: 16-Dec-05
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 one-to-one 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
Ignore | Quote | Vote Down | Vote Up
Dogbert
Send Private Message Add Comment To Profile

Edited: 16-Dec-05
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
Ignore | Quote | Vote Down | Vote Up
winnidon
Send Private Message Add Comment To Profile

Edited: 16-Dec-05
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
Ignore | Quote | Vote Down | Vote Up
Dogbert
Send Private Message Add Comment To Profile

Edited: 17-Dec-05
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.