Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The axiom of replacement is usually used to prove the existence of large sets, to provide a reflection principle, for transfinite recursion… However, I am wondering how it affects finite sets. Let me give two concrete questions (let S be ZF without replacement and without infinity, SF=S+replacement, Z=S+infinity):

  • Are there theorems in SF+“every set is finite” which cannot be proved in S+“every set is finite”? In an alternative formulation: Does S+“every set is finite” imply the axiom of replacement? If not: Is there some instructive construction which fails?
  • Assume we are working in Z or ZF and consider the set $HF$ of all hereditarily finite sets: Are there “natural” statements about $HF$ which can be proved in $ZF$ but not in $Z$? (of course there are such statements, namely in $ZF$ we can prove that $HF$ is a model of some first-order statements expressing that $Z$ plus any given finite fragment of $ZF$ is consistent (and some similar statements), but I am looking for different properties)

“Finite” should be defined using natural numbers, which are Dedekind finite ordinals. Feel free to use strong versions of foundation for the first question. If something interesting happens with the negation of such an axiom, it would be interesting, too.

Regards

share|improve this question
3  
One issue is that when you drop the axiom of infinity, then various ordinarily-equivalent formulations of foundation become inequavalent. For example, asserting that every set has a $\in$-minimal element is weaker than $\in$-induction scheme without infinity. The latter proves that every set has a transitive closure, but the former is consistent with the failure of this, by a theorem of Ali Enayat (mentioned elsewhere here on MO). So your descriptions of the theories may be ambiguous, unless you state exactly which formulations of the axioms you are using. –  Joel David Hamkins Aug 7 '13 at 1:05
    
See mathoverflow.net/a/63918/1946. –  Joel David Hamkins Aug 7 '13 at 1:08
6  
I expect that, with a suitable formulation of finiteness, it should be possible to deduce replacement from "all sets are finite". Specifically, it should be possible to prove by induction on $n$ that replacement holds when the "domain" of the replacing "function" is an $n$-element set. –  Andreas Blass Aug 7 '13 at 1:10
    
Thanks for the comment, I had the “every set has a disjoint element”-formulation in mind. However, I think I will not stick to some formulation. I will add a remark in the question. –  The User Aug 7 '13 at 1:15
    
One issue about notation, $Z$ usually denotes Zermelo's set theory which is $\sf ZF$ without regularity and replacement (but with separation). –  Asaf Karagila Aug 7 '13 at 2:23

1 Answer 1

I claim that replacement is provable in the theory SF+"every set is finite". One proves any instance by induction on the size of the domain of the function. That is, a given instance of replacement says that if $A$ is a set and we have for every $a\in A$ a unique $b$ such that $\varphi(a,b)$, then the set $\{b\mid \exists a\in A\, \varphi(a,b)\}$ is a set. Suppose this is true for all sets smaller than $A$. Now, remove one element from $A$, apply the induction hypothesis, and then add in the missing $b$.

So the answer to your first question is yes.

share|improve this answer
    
Ah, I see upon posting my answer that Andreas made the same point in a comment... –  Joel David Hamkins Aug 7 '13 at 1:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.