Article View: sci.logic
Article #284Re: Impredicativity - was: Russell's Paradox
From: Torkel Franzen
Date: Thu, 05 Nov 1992 09:31
Date: Thu, 05 Nov 1992 09:31
24 lines
1899 bytes
1899 bytes
In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz
(Bill Taylor) writes:
>A = { 1 , { 2 , { 3 , { 4 , {.....}}}}}
>B = { 1 , { 1 , { 1 , { 1 , {.....}}}}}
>Can B above, be obtained from A above, by ZF methods.
The question is vague in several respects, but the most likely
answer is no. A, to put this into formal ZF terms, is, let us say, the
range of a function f defined on the natural numbers, where
f(n)={n,f(n+1)} for all n. Assuming the existence of such a function
in ZF (without foundation) does not in any obvious way (and hence not
at all, by the argument from experience) imply the existence of a set
x such that x={1,x}. In particular, Replacement by itself is no help
since to get x using replacement, we need to define a function h by
h(n)=G(f(n)), where G({a,b})={1,G(b)}, and there is no way of defining
G in ZF (without foundation) so that this is provable. In other words:
Replacement allows us to make infinite "substitutions" in sets, but to
make infinite substitutions in non-well-founded sets we need a
corresponding non-well-founded recursion principle.
Of course, even if this is correct it doesn't follow that accepting
A and rejecting B makes any sense. Or in other words: it doesn't help
explain what mathematical objects, if any, you have in mind.
Technical Details
Message-ID:
<TORKEL.92Nov5103134@isis.sics.se>Path:
arc1-ca.pugleaf.net!sparky!uunet!olivea!spool.mu.edu!yale.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!sics.se!torkelReferences:
<Bx81Ho.9HL@cantua.canterbury.ac.nz>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!olivea!spool.mu.edu!yale.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!sics.se!torkel From: torkel@sics.se (Torkel Franzen) Newsgroups: sci.logic Subject: Re: Impredicativity - was: Russell's Paradox Message-ID: <TORKEL.92Nov5103134@isis.sics.se> Date: 5 Nov 92 09:31:34 GMT References: <Bx81Ho.9HL@cantua.canterbury.ac.nz> Sender: news@sics.se Organization: Swedish Institute of Computer Science, Kista Lines: 24 In-Reply-To: wft@math.canterbury.ac.nz's message of Thu, 5 Nov 1992 02:27:23 GMT