
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
October 29th, 2017, 09:04 PM  #1 
Senior Member Joined: Jun 2014 From: USA Posts: 402 Thanks: 26  Axiom of Computable Power Set
I'm guessing something like this already exists or has been proposed and I'm simply not aware, but I am wondering what the consequences would be and am inclined to spark general discussion. Most are familiar with the power set axiom, as it is one of the basic axioms of ZFC set theory: https://en.wikipedia.org/wiki/Zermel...kel_set_theory I choose the word 'computable' because of its traditional use when describing real numbers, which I wish to adhere to within the context of ZFC. My initial goal is therefore to attempt to define what I mean by a 'computable set' within the context of ZFC. I correlate the computable elements of the power set of natural numbers with exactly those elements of the set of infinite binary sequences that are computable using a turing machine. Just as a "computable number [is] one for which there is a Turing machine which, given n on its initial tape, terminates with the nth digit of that number [encoded on its tape]," a computable element $p$ of $P$($\mathbb{N}$) will be one where a function exists to determine whether any given integer $x$ is in $p$ and, similarly, a computable infinite binary sequence is one where a function exists that can determine whether the nth bit of the sequence is a '0' or a '1'. https://en.wikipedia.org/wiki/Computable_number It occurred to me that when taking the power set P(S) of a finite set S, all of the elements of P(S) are themselves sets that could be defined using the axiom schema of specification. When combined with the axioms of pairing and union, it seems like the power set axiom is redundant in these cases, unless of course I am missing something. E.g.: Let S = { 1, 2 } (note that S might exist based on the axioms of pairing and empty set, if not by some other construction) Then, by the axiom schema of specification, we can assert the existence of the elements of P(S): {}, {1}, and {2} (noting of course that {1,2} already exists as given) With the axiom of pairing and axiom schema of specification, we can assert the existence of the sets: { {}, {1} } and { {2}, {1, 2} } And finally, with the axiom of union, we can assert the existence of P(S): P(S) = { {}, {1} } $\cup$ { {2}, {1, 2} } In returning to the notion of a computable element of $P$($\mathbb{N}$), I note that all finite elements of $P$($\mathbb{N}$), which are computable just as any infinite binary sequence containing only a finite number of 1's is computable, could be proven to exist simply via the axioms of pairing, union, and schema of specification. The same cannot be said of all the infinitely large elements of $P$($\mathbb{N}$), however. The traditional power set axiom will assert the existence of all elements of $P$($\mathbb{N}$) regardless of whether or not they are computable. With that in mind, I define the axiom of computable power set to assert the existence of only those elements of $P$($\mathbb{N}$) that are computable. If considering ZFC as implementing the axiom of computable power set as opposed to the traditional power set axiom, I wonder whether an uncountable set could exist. There is no formula $\phi$ to determine which elements of $P$($\mathbb{N}$) are computable (which is, I believe, a result of the halting problem, as such a formula $\phi$ would be more complex than merely determining all formulas that halt  see here: Noncomputable Reals). Therefore, I consider the axiom of computable power set to be one that is 'necessary' because the axiom schema of specification could not produce a set containing only those elements of $P$($\mathbb{N}$) that are computable (there would be no specifying formula $\phi$). However, maybe I am mistaken... If each computable element of $P$($\mathbb{N}$) can be proven to exist via the axiom schema of specification given the axiom of infinity (and perhaps only the computable elements), then would it be possible for the axioms of union and pairing to then ensure that a set containing only those computable elements of $P$($\mathbb{N}$) exists? If so, then does $\phi$ actually exist (per the above link, $\phi$ apparently cannot exist because it contradicts Cantor's diagonal argument given the natural bijective relation between the infinitely large elements of the power set of integers and the set of infinite binary sequences)? Last edited by AplanisTophet; October 29th, 2017 at 09:33 PM. 
October 30th, 2017, 04:14 PM  #2 
Senior Member Joined: Jun 2014 From: USA Posts: 402 Thanks: 26 
I realize my presentation isn't always the best. I think of my tax clients that talk about everything under the sun not relevant to their tax returns... Anyways, I posted this too on stackexchange and perhaps did a little better in terms of asking my questions: https://math.stackexchange.com/quest...mofpowerset PS  When I wrote "[t]here is no formula $\phi$ to determine which elements of $P$($\mathbb{N}$) are computable" above, I should clarify that there are uncountably many noncomputable real numbers, noncomputable infinite binary sequences, and noncomputable elements of $P$($\mathbb{N}$) that all encode what would be a listing of the computable reals, computable binary sequences, and computable elements of $P$($\mathbb{N}$). That too was acknowledged here: Noncomputable Reals. Also acknowledged was that there is no formula capable of deciding for each wellformed formula in a formal language capable of expressing the computable reals whether or not it is a formula for a computable real number (or computable infinite binary sequence / element of $P$($\mathbb{N}$)). Again, this was generally because we don't have a way of solving the halting problem. To quote Maschke in the above thread, "I've been trying to understand the fundamental reason that an enumeration of computable reals must itself be noncomputable. It's because a computable enumeration would violate the noncomputability of the halting problem." (post 9) 

Tags 
axiom, computable, power, set 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Noncomputable Reals  AplanisTophet  Number Theory  30  June 21st, 2017 09:25 AM 
axiom  Bhuvaneshnick  Probability and Statistics  1  January 7th, 2015 05:06 AM 
Axiom or theorem?  Theta  Number Theory  6  June 14th, 2014 12:35 PM 
Is That An Axiom?  mathmaniac  Algebra  18  February 4th, 2013 04:33 PM 
Computable completion  iclestu  Applied Math  2  October 26th, 2011 11:40 AM 