My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 29th, 2017, 10:04 PM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

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: Non-computable 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 10:33 PM.
AplanisTophet is offline  
 
October 30th, 2017, 05:14 PM   #2
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 315
Thanks: 21

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...m-of-power-set


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 non-computable real numbers, non-computable infinite binary sequences, and non-computable 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: Non-computable Reals.

Also acknowledged was that there is no formula capable of deciding for each well-formed 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)
AplanisTophet is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
axiom, computable, power, set



Thread Tools
Display Modes


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





Copyright © 2017 My Math Forum. All rights reserved.