2
$\begingroup$

Update with Direct Question

Based on Asaf's comments, here is a related question:

Prove that the mapping $n \mapsto n \cup \{n\}$ on the set $\Bbb N$ is injective without the axiom of foundation.

The wikipedia $\text{ZF}$ article under axiom 7 contains the text

(It must be established, however, that these members are all different, because if two elements are the same, the sequence will loop around in a finite cycle of sets. The axiom of regularity prevents this from happening.)


ORIGINAL QUESTION

Without the axiom of foundation (axiom 2 in the wikipedia $\text{ZF}$ article)
can any infinite sets be constructed?

By an infinite set we mean a set that is not Kuratowski finite.

I suspect that without it, the axiom of infinity (axiom 7) might be better described as

$\quad$ The formula of finitary frustration.

My work

I saw the axiom of foundation mentioned inside parentheses in the paragraph for axiom 7 allowing us to construct the natural numbers. So apparently, the familiar program of constructing the natural numbers $\Bbb N$ can't be carried out without axiom 2.

$\endgroup$
  • 6
    $\begingroup$ I'm confused. The axiom of infinity is still part of your system, yes? Where is the problem? $\endgroup$ – Asaf Karagila Jul 7 at 11:48
  • 1
    $\begingroup$ If I understand the axioms right, the axiom of inifnity allows us to add an element to a given set as often as we want. But the regularity axiom is necessary to avoid that at some point, we can only add elements that we already have in our set (which would mean that the set would not actually become bigger). Maybe, I miss something, but this sounds as we need the axiom of regularity. $\endgroup$ – Peter Jul 7 at 12:05
  • 1
    $\begingroup$ @Peter: You are missing something. The axiom of infinity simply posits the existence of a set which has the empty set as an element, and is closed under $x\mapsto x\cup\{x\}$. Since $\varnothing$ is not in the range of this map, the set has an injective function which is not surjective, and so it is infinite under any reasonable definition of infinite. Regularity has absolutely nothing to do with it. The only role of regularity is simplifying some of the basic proofs about the least inductive set (i.e. $\omega$). $\endgroup$ – Asaf Karagila Jul 7 at 12:30
6
$\begingroup$

It is true, if $x=\{y\}$ and $y=\{x\}$ and $x\neq y$, then $x\cup\{x\}=\{x,y\}=y\cup\{y\}$. So without assuming the axiom of regularity the map $x\mapsto\{x\}$ is not provably injective.

But just because it is not necessarily injective on the entire universe does not mean that we cannot find a set on which it is injective.

Setting $\omega$ to be the intersection of all the inductive sets, we can now prove that $x\mapsto\{x\}$ is in fact injective on $\omega$. The reason being is that $\omega$ is in fact well-founded, so in particular the above situation does not happen inside $\omega$, it it happens at all.

The quickest, dirtiest, hackiest way to see this is to simply note that $\omega$ belongs to the von Neumann universe which is an inner model of the universe (working in $\sf ZF-Reg$). But this can be shown by hand, through what is tantamount to an ad-hoc proof that $\omega$ is well-founded.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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