It is my understanding that the axiom of infinity, or axioms that depend on the axiom of infinity, are the only axioms that are not representable in finite First-Order Predicate Logic. Is this correct? If so, how can the axiom of infinity be justified? Furthermore, it is my understanding that the axiom of infinity requires infinite induction, which requires the axiom of infinity. How is this circular definition resolved? Is there a way for the axiom of infinity to be defined so that it does not require infinite induction?
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ Why would the axiom of infinity require infinite induction? The axiom of infinity is simply the statement that "There is a sex $x$ with $\emptyset \in x$ and whenever $y \in x$ then $y \cup \{y\} \in x$", i.e. that $\exists x\,:\,(\emptyset\in x ) \land (\forall y\,:\,y \in x \rightarrow y \cup \{y\} \in x)$ $\endgroup$– fgpCommented May 18, 2013 at 10:46
-
$\begingroup$ In the case you mention you have an inductive set $x$ which requires infinite induction, does it not? $\endgroup$– John JenkinsCommented May 18, 2013 at 10:55
-
3$\begingroup$ No: it is the existence of the inductive set that permits infinite induction. $\endgroup$– Brian M. ScottCommented May 18, 2013 at 18:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
While it is correct that generally it is impossible to write a sentence in first-order logic whose content is "there are infinitely many objects in the universe", we can still - under some circumstances - write a sentence which can prove that there are infinitely many objects.
For example, in a language which has a binary relation symbol $<$ we can write the following axioms (and take their conjunction, which is one sentence):
- $\forall x(x\nless x)$ ($<$ is irreflexive).
- $\forall x\forall y\forall z(x<y\land y<z\rightarrow x<z)$ ($<$ is transitive).
- $\forall x\forall y(x<y\rightarrow\exists z(x<z\land z<y)$ ($<$ is dense).
From the conjunction of the three sentences we have one axiom whose implications are, amongst other things, that there are infinitely many elements in the universe. Formally, of course, we don't prove just one sentence, we prove a whole schema. We prove that for every $n\in\Bbb N$, these three prove that $\forall x_1,\ldots,\forall x_n\exists y(\bigwedge_{i=1}^n x_i\neq y)$. So no matter what $n$ elements we take, there is one more. Therefore there can't be finitely many elements in the universe.
Similarly, the axiom of infinity is a first-order axiom which states that there exists a set with certain properties. From the existence of that set we can prove that the universe contains a set which is not finite.
Also see Set Notation (Axiom of Infinity).
answered May 18, 2013 at 12:41
$\begingroup$
$\endgroup$
5
The axiom of infinity can be represented perfectly well in first-order logic, for example by asserting the existence of an inductive set (a nonempty set closed under the successor relation, like $\omega$). This does not require "infinite induction": it's just an ordinary statement in the language of set theory stating that something satisfying a certain condition exists. There is no circularity in the definition or the axiom.
The question of justifying the axiom is a different matter. One approach would be to say simply that lots of mathematics we want to do requires this axiom, so we assume it. Most mathematicians are happy enough with this pragmatic position, although it leaves unanswered the question of whether the axiom of infinity, like the other axioms of set theory, is just an assumption under which we carry out mathematical reasoning or whether we believe that there really are an infinity of sets.
answered May 18, 2013 at 10:48
-
$\begingroup$ Can you expand upon the description you give of inductive set? I was already aware that an inductive set is used, but my issue here is fairly subtle since an inductive set does indeed require induction in order to be defined. I did not have an issue with the statement itself, but rather with the definition of the statement. Maybe I am confused about the underlying formal language, but it is my understanding that the statement does not require an induction to be stated, but it does require infinite induction to be defined. $\endgroup$ Commented May 18, 2013 at 11:10
-
$\begingroup$ Put another way, the assertion of the axiom of infinity states that at least one inductive set exists and therefore can be instantiated, unless the axiom is false. However, the instantiation of one inductive set requires infinite induction, which requires the axiom of infinity to be true. However, since one inductive set has not been instantiated the axiom of infinity has not been establish to be true. Thus, the axiom of infinity must be assumed. However, this leads to a circular definition. $\endgroup$ Commented May 18, 2013 at 12:35
-
$\begingroup$ "...unless the axiom is false". I don't this this is correct. I think you want inconsistent instead of false. Then, as Asaf notes, we have that it is permissible for some such set to exist, and then we can prove that non-finite sets exist. $\endgroup$– user452Commented May 18, 2013 at 12:53
-
1$\begingroup$ Also, I would suggest you read Exercises 1.2-1.9 of Jech's Set Theory (2002) if you have access. Far from using induction to prove an inductive set exist, induction is proved to exist in 1.9 from the existence of an inductive set. No circularity is indicated, best I can see. $\endgroup$– user452Commented May 18, 2013 at 13:07
-
1$\begingroup$ Perhaps my use of the term "inductive set" confused matters rather than clarifying them. But essentially you have it the wrong way round: an inductive set is one which one can perform induction on, not one which is defined using induction. Think about proofs about all natural numbers: we show that some property holds for $0$, then assuming holds for some $n$, show that it holds for $n + 1$. An inductive set—closed under successors—is one which we can carry out inductive proofs about the members of. $\endgroup$ Commented May 18, 2013 at 13:58