Talk:Axiom of infinity

Capitalization and second order logic

Q: aren't capital names and variables reserved for second-order logic? $\exists x\lbrack \emptyset \in x\land \forall y(y\in x\rightarrow \cup \lbrace y,\lbrace y\rbrace \rbrace \in x)\rbrack$ --Alterego 01:54, Apr 25, 2005 (UTC)

If you want to quantify both over first-order and second-order things you might want to make that convention or another which makes the distonction clear. Since we are working entirely in first-order here we don't need to restrict ourselves as to the variables which we use. Using a variable name which has the right associations can help people a lot in understanding a formula. MarSch 12:13, 27 Apr 2005 (UTC)

I don't want to, but the article does. I guess it is a convention of set builder notation? --Alterego 15:11, Apr 27, 2005 (UTC)

Specification to remove unwanted elements?

What specification are you using to remove unwanted elements?

I am not sure exactly what you mean by using the axiom schema of specification to remove unwanted elements. The schema allows one to remove elements from a set which do not satisfy a particular predicate. However as far as I can see, there is no such predicate applicable in this case.

In fact, the "standard" way to do this is to just take all inductive subsets of some inductive set and find their intersection, but even this I believe to be fundamentally flawed (I'll not go into this here, though). Kidburla2002 9 July 2005 12:45 (UTC)

I'm not sure I fully understand what you're getting at. That said, it's clear that you're basing your discussion on intuitive set theory, which is not what this article is about. This article is about axiomatic set theory, which starts with first principles defined abstractly, regardless of pre-theoretic intuitions. The most common version is Zermelo-Fraenkel set theory (ZF), which is a simple axiomatic theory, expressed in predicate logic, of what the symbol $\in$ means. ZF is a single-sorted theory, i.e., it makes no distinction between set-variables and objects and non-set variables and objects. ZF simply says that certain sets exist (e.g. the empty set) and how to form sets from existing sets (e.g. pairing). It turns out that for finite, well-founded sets, ZF matches everyone's intuitions about sets quite nicely. But it's precisely the various kinds of infinite sets that it's hard to have pre-theoretic intuitions about: everybody has encountered finite collections of physical objects, but nobody has encountered infinite collections, so it's a bit hard to have intuitions about how they should behave. The axiomatic approach is useful because it makes precise how all sets must behave, without having to rely on intuitions which people can disagree about. Most of the axioms say trivial things (e.g., "there is an empty set", which, by the way, does not mean the same as "there is no set" as you suggest) which are necessary for an approach based on logic where you want to be able to prove everything from first principles. The present axiom of infinity simply says that there exists a set with a certain recursive property. (It doesn't actually say that the set whose existence is postulated is infinite or is related in any way to the natural numbers. These notions require additional definitions and conventions.) The recursive property is explained in the article: the infinite set is such that if it contains a set x, then it also contains what you might call the successor of x (which is the set $x\cup \{x\}$). Note that the existence of sets which contain the empty set and finitely many successors follows from the other axioms of ZF. But it is not possible to prove the existence of a set which contains the empty set and all of its successors from the remaining axioms of ZF, hence the need for the present axiom which explicitly asserts that such a set exists. --MarkSweep (call me collect) 08:04, 29 April 2006 (UTC)

You might be missing the point here. The article says

This set S may contain more than just the natural numbers, forming a subset of it, but we may apply the axiom schema of specification to remove unwanted elements, leaving the set N of all natural numbers.

To paraphrase: "Infinity asserts the existence of a superset of omega, separation can be used to get exactly omega." What predicate can be used to do this separation? -Dan 17:18, 24 May 2006 (UTC)

ω is the set of natural numbers. n is a natural number iff $\lbrack n=0\lor \exists y(n=y\prime )\rbrack \land \forall x\in n\lbrack x=0\lor \exists y\in n(x=y\prime )\rbrack \!$. That is, n is a natural number iff it is either zero or a successor and each of its elements is either zero or a successor of another of its elements. This uses the axiom of regularity. JRSpriggs 06:34, 26 June 2006 (UTC)

There is more about this at Talk:Natural number#Set theoretic definition. JRSpriggs 04:55, 1 July 2006 (UTC)

JRSpriggs - In what sense does the "intersection" formulation not ensure the limitation of the natural numbers? Given weak induction and ZFC we can basically prove all the second-order properties of natural numbers, since the power set axiom allows us to quantify over all subsets of $\omega$. I'm not sure I understand your reasoning here. Is it an issue of nonstandard models? Also, I thank you for your edits on the "Alternate" section, although I think it still needs work, since any reference to the actual axiom of infinity has been removed. Jayferd (talk) 17:27, 23 April 2009 (UTC)

I was not thinking of any specific abnormal "natural numbers". Rather, I was thinking about how I would prove that the natural numbers have the kind of structure which they do have. You are correct, that I had forgotten a kind of argument which works for most properties. Although I think there is still some difficulty proving that the natural numbers under ∈ are trichotomous. JRSpriggs (talk) 10:21, 24 April 2009 (UTC)

What I meant by the ZFC remark before was that any system which can prove the second-order Peano axioms completely determines $\omega$ - in the sense that any two systems which both satisfy the following three axioms (where 'Sx' means 'the successor of x', in our case $x\cup \{x\}$) will be isomorphic:

• $\forall x(Sx\neq 0)$
• $\forall x\forall y(Sx=Sy\to x=y)$
• $\forall A\subseteq \omega (0\in A\wedge \forall x(x\in A\to Sx\in A)\to A=\omega ).$

Both constructions prove all three of these claims. To get trichotomy, what Enderton does in Elements of Set Theory is first he proves two straightforward lemmas: that $\forall m\forall n(m\in n\leftrightarrow m^{+}\in n^{+})$, and that $\forall n(n\notin n)$. It follows easily that at most one of the three trichotomy conditions holds. To show that at least one holds, he does the following:

We claim that $T=\{n\in \omega :(\forall m\in \omega )(m\in n\vee m=n\vee n\in m)\}$ is inductive. First, we claim $0\in T$; that is, $\forall x(x=0\vee 0\in x)$. But clearly $0=0$ and if $x=0\vee 0\in x$ then in either case $0\in x^{+}$. Now assume that $x\in T$. For any $m\in \omega$, we have two cases by inductive assumption. If $m\in x$ or $m=x$, then $m\in x^{+}$. If $x\in m$ then by the lemma $x^{+}\in m^{+}$, so either $x^{+}\in m$ or $x^{+}=m$; in either case we are done. Jayferd (talk) 03:08, 6 May 2009 (UTC)

Could you expand and clarify that last part a little? Where does x appear after your assumption that x∈T? JRSpriggs (talk) 19:03, 6 May 2009 (UTC)

To Jayferd: You must revert your reversion of my change to your section. Proper classes are do not exist in ZFC; you cannot legitimately use them in any proof. JRSpriggs (talk) 19:03, 6 May 2009 (UTC)

To JRSpriggs - My bad on both counts. Changed $k$ to $x$ in the last part of the above proof. Also, I think I can restructure my argument to say: There exists a unique set whose members are exactly those which are in every inductive set, i.e. the axiom of infinity + specification proves $\exists !\omega \forall x(x\in \omega \leftrightarrow \forall I(\Phi (I)\to x\in I))$. My bad for revising without checking first. Jayferd (talk) 00:35, 8 May 2009 (UTC)

(unindent) OK, I see how it is done now. The inductive hypotheses, on n, which one might want to use include: $n=0\lor \exists m\in \omega (n=m^{+}),$ $\forall m\in n(m\in \omega ),$ $\forall m\in n\forall k\in m(k\in n),$ $n\notin n,$ $\forall m\in n(m^{+}\in n^{+}),$ $\forall m\in \omega (m\in n\lor m=n\lor n\in m).$ JRSpriggs (talk) 23:47, 11 May 2009 (UTC)

what does this symbol mean?

What does $\forall k\in n(\bot )$ mean? What is the $\bot$ symbol? -lethe ^{talk +} 16:55, 8 March 2007 (UTC)

$\bot$ is a logical symbol that means "false". It is often taken as an atomic formula that is identically false. So $\forall k\in n(\bot )$ means $n=\varnothing$. In a theory with equality, $\bot$ can be simulated by not equals: $n=\varnothing \Leftrightarrow \forall k\in n(\bot )\Leftrightarrow \forall k\in n(k\not =k)$.

This article, like many of the "axiom of ..." articles, could use a good cleaning. CMummert · talk 17:25, 8 March 2007 (UTC)

If ZFC is consistent ...

(See [1]) I believe my change is correct. Consider: it could be that ZFC-INFINITY is consistent, but ZFC is not. Then the axiom of infinity could not be derived from the other axioms, even though ZFC would be inconsistent, as claimed. Now the sentence could read "If ZFC without the axiom of infinity is consistent, then..." and this would also be correct, but I think that this weaker condition ought to be omitted. I don't know offhand what exactly it is, but the proof-theoretic strength of ZFC-INFINITY must be quite modest. --99.245.206.188 (talk) 08:04, 28 February 2009 (UTC)

As Independence (mathematical logic) correctly says, "a sentence σ is called independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that σ is false". That is, for the axiom of infinity to be independent of the other axioms of ZFC means that neither it nor its negation can be deduced from them. If ZFC is inconsistent, then $ZFC\vdash \bot \,$ which is the same as $(ZFC-Infinity)+Infinity\vdash \bot \,$ which (by the deduction metatheorem) implies $(ZFC-Infinity)\vdash \lnot Infinity\,$ and thus that the axiom of infinity is not independent.

Furthermore, the sentence "The axiom of infinity cannot be derived from the other axioms." means $(ZFC-Infinity)\not \vdash Infinity\,.$ However, ZFC minus the axiom of infinity already implies the Peano axioms which, as you know, are subject to Gödel's incompleteness theorems. Thus we cannot be said to know with certainty that ZFC minus the axiom of infinity is consistent. If it turns out to be inconsistent, then it also implies the axiom of infinity which would contradict the sentence in your shortened form. Thus I will again revert you. JRSpriggs (talk) 14:00, 28 February 2009 (UTC)

If so, then your reversion is still wrong! You either mean "If ZFC is consistent, then the axiom of infinity cannot be refuted from the other axioms" or "If ZFC without the axiom of infinity is consistent, then the axiom of infinity cannot be derived from the other axioms"

If you still don't see it, then let's abstract. Let T be a theory and A an axiom, and suppose that T+A proves the consistency of T. Then:

• T is inconsistent iff A can be derived from T.
• T+A is inconsistent iff A can be refuted from T.

Correct? Now A is the axiom of infinity, and T is the rest of ZFC.

I will include it for now, but I still maintain that "if ZFC-Infinity is consistent" ought to be dropped. I seem to remember, but am not sure, that ZFC-Infinity is actually equiconsistent with PA. Yes, if PA is consistent, then it can't prove it's own consistency, but so what. There are some rare circumstances where we would bother to say "If PA is consistent" (like the previous sentence). But generally not, especially in the context of set theory. I mean, are we going to "fix" the ordinal articles with a bunch of caveats about "if epsilon-naught is well-founded" ? --99.245.206.188 (talk) 16:29, 28 February 2009 (UTC)

Consistency of all ZFC implies consistency of ZFC minus the axiom of infinity. Thus the consistency of ZFC does imply both the non-provability of Infinity and the non-provability of it negation from ZFC minus infinity. While it is true that your new formulation is slightly stronger while still being correct, the usual assumption people make when addressing independence questions in set theory is that all ZFC is consistent. I was just trying to make the simplest statement, to wit, consistency implies independence. I will leave your new version alone, if you do not change it further. JRSpriggs (talk) 17:57, 28 February 2009 (UTC)

Things we all probably know: the axiom of infinity cannot be derived from ZFC without infinity because the hereditarily finite sets are a model of all of ZFC except the axiom of infinity. Thus, in particular, ZFC without the axiom of infinity is consistent and strictly weaker than ZFC with the axiom of infinity. Moreover, if one gets the details right, ZFC minus the axiom of infinity plus its negation is equiconsistent with Peano arithmetic.

My take on the article text: I think it is better not to state an assumption of the consistency of ZFC when talking about the consistency of ZFC minus the axiom of infinity, since the latter is so much weaker. We do not say "if Peano arithmetic is consistent" very often, after all, as the IP editor has pointed out. — Carl (CBM · talk) 19:59, 6 May 2009 (UTC)

Alternative Extraction of Natural Numbers

Can't we define the naturals this way?

$\mathbb {N} :=\{T\in {\mathcal {P}}(I):\varnothing =T\vee (\varnothing \in T\wedge \forall x\in T\exists y\in T[y\cup \{y\}=x])\}$ — Preceding unsigned comment added by 96.29.111.3 (talk • contribs)

Not quite. If T contains the empty set, then it cannot have all of its members being successors. JRSpriggs (talk) 14:49, 22 May 2013 (UTC)

A valid alternative would be

$\mathbb {N} :=\bigcap \{Z\in {\mathcal {P}}(I):\varnothing \in Z\wedge \forall x\in Z(x\cup \{x\}\in Z)\}$

as the arbitrary intersection of transitive sets is again transitive. Thus the natural numbers could be called the unique smallest transitive set. This is from Halmos. Naive Set Theory. 1960.— Preceding unsigned comment added by 96.29.111.3 (talk) 04:50, 25 May 2013 (UTC)

“I ⊃ ℕ”

The article says that I is a superset of the naturals. Could someone prove to me that this is? I mean, correct me if I am wrong, but ℕ is such that 0 ∈ ℕ, and ∀x ∈ ℕ, successor(x) ∈ ℕ. This seems to match very much with the definition of I, only that ø is used instead of 0, and x ∪ {x} is in place of successor(x). PicoMath (talk) 21:17, 17 November 2023 (UTC)

It does NOT say that I ≠ N; is that your problem?

So what? Is that not what you expect? JRSpriggs (talk) 23:29, 18 November 2023 (UTC)