6
$\begingroup$

In our mind we have a naive idea of what a set is, and in nature we can only observe something that behave like a finite set, ZFC (or set theories in general) tries to catch these properties in axioms. Like Peano axioms describe the nature of natural numbers, and all the "things" that behave in that way are "isomorphic to the naturals, that property seems is called categoricity (in my naive understanding is that all models of the naturals are isomorphic).

Well, I think that all agree on how sets behave, in the sense that in our experience of the word, we can see only a kind of finite set, or like a bag full of something (or empty) or as a property (comprension axiom), and all sets are finite.

My question is there is a concept of set (axioms), that have a "unique interpretation" and are exatly the naive concept of set?

$\endgroup$
3
$\begingroup$

If we really want to consider finite sets, we want not only that they will be finite but also that their elements will be finite, and the elements of their elements will be finite, and so on. In short, we want that the transitive closure of the set will be finite. (Where the transitive closure of a set $x$ is the smallest set $y$ such that $x\subseteq y$ and $t\in s\in y\rightarrow t\in y$.)

In a model of $\sf ZFC$ we can define the set of all hereditarily finite sets. This is commonly denoted by $V_\omega$. It is a countable set, and in fact it is exactly the [increasing] union of $\mathcal P^n(\varnothing)$, the iterated power set operation of the empty set.

To add more on this, $V_\omega$ satisfies all the axioms of $\sf ZFC$ except the axiom of infinity, and it does satisfy its negation: there is no inductive sets, and therefore there are no infinite sets either. So does this theory, $\sf ZFC$ with the axiom of infinity replaced by its negation good enough to decide what are finite sets?

Generally, it seems that yes. But as any first-order theory with infinite models, we can produce models of the same theory which are as large as we want, and that's not very good. But much like with the real numbers, or with $\sf PA$, we can move to second-order logic (with full semantics) and have a categorical theory!

We slightly modify our theory, and instead of the schema of replacement for definable sets, we add a full-blown second-order axiom of $\in$-induction:

$$\forall A(\varnothing\in A\land\forall x(\forall y(y\in x\rightarrow y\in A)\rightarrow x\in A)\rightarrow\forall x(x\in A))$$ Every class $A$ such that $\varnothing$ is a member of $A$, and for every $x$, whenever all the members of $x$ are in $y$ then $x$ is itself a member of $A$, then $A$ is the entire universe.

This should be, if I am not mistaken, to a second-order formulation of the replacement schema, although I don't recall the proof at this moment.

Why does this guarantees that there is only one model? Suppose that $M$ was a model of our modified theory, then it has a naturally defined power set operation and an empty set. Construction by recursion $V_\omega$ as the union of the finite iterations of $\mathcal P^n(\varnothing)$, and we have a class satisfying the assumption of this induction axiom. Therefore it must be equal to the whole universe!

Note that the above proof happens outside the model $M$. Very much like how the proof that there is only one model of $\sf PA_2$ occurs outside $\Bbb N$.

It seems to me that this theory is reasonable to capture what is truly finite in the universe of sets.

$\endgroup$
3
$\begingroup$
  1. In what sense can we "see" a finite set? Sure we can see a bag, and see the marbles in the bag. But the bag isn't a set (we don't identify bags by their contents!), and the marbles aren't a set either (for the marbles are many and the set of marbles is one).

  2. If, as you imply, we are allowed to specify a set as the set of things with a certain property (you mention the comprehension axiom), then to be sure there are infinite sets -- e.g. the set of natural numbers, the set of space-time points along some given line, etc.

  3. But agreed, there are indeed problems about the "naive" notion of a set (I don't mean naive set theory, but the pre-theoretic concept of a set). Can we have an empty set on the naive conception of a set as a collection treated as a unity? You might find some of the early chapters of Michael Potter's Set Theory and its Philosophy helpful.

[Added] For an excellent treatmentof the relationship between PA and a canonical theory of finite sets (i.e. ZF with the axiom infinity negated) see this first-rate paper by Kaye and Wong.

$\endgroup$
  • $\begingroup$ I'm talking about a set theory of finite sets. And i wanted to know if this axioms describe the same "wolrd of sets" as peano axioms describe only natural numbers categoricaly. I used "see" in the sense tha we are able to identify the bag as the set of those marbles. $\endgroup$ – MphLee May 20 '13 at 9:48
  • 3
    $\begingroup$ (a) The theory of hereditarily finite sets is translatable into Peano Arithmetic. (b) A bag of marbles is not the same of thing as a set of marbles. $\endgroup$ – Peter Smith May 20 '13 at 12:53
  • $\begingroup$ Thanks, I'll read this papers (already found Potter's one). $\endgroup$ – MphLee May 20 '13 at 14:25
  • 2
    $\begingroup$ Sure we identify a bag with its contents, if you have a bag with all your coins in it, and I stole that bag, and put all the coins in a new bag; wouldn't you say that this new bag is "your bag of coins"? Or when you confront me and demand I return your bag of coins, and I return an empty bag, you'll be satisfied? (If the latter, please arrange for a plane ticket to England, and bag your coins, jewels, and other valuables!) $\endgroup$ – Asaf Karagila May 20 '13 at 14:32
2
$\begingroup$

If the "naive concept of a set" allows you to represent natural numbers (by, say, representing $0$ as the empty set, and $n+1$ as $\{N,\{N\}\}$ where $N$ is the set that represents $n$), and allows you to prove that the peano axioms hold for this representation, then this "naive concept of a set" won't have a unique interpretation.

This is because that concept of a set is then powerfull enough to apply Gödel's incompleteness theorem to it, and from that it follows that there are statements $\phi$ for which neither $\phi$ nor $\lnot\phi$ is provable. That allows you to add either $\phi$ or $\lnot\phi$ as a new axiom without causing inconsistencies, which yields two different models of the original set of axioms.

This only applies if you formalize your naive concept of a set in first-order logic, though.

$\endgroup$
  • $\begingroup$ Let me understand, so the answer to my question is no? (Sorry if my terminology is not correct, I'm tryng to use intuitive meaning of the concepts) There isn't a "weak enough" concept of set that describes a unique "universe" of sets, like for example the Peano axioms describe categorically (with the second-order induction axiom) an uniqe set of natural numbers (all the structures are isomoprhic), because the concept of set is "strong" enough to create something that satisfies the peano axioms? $\endgroup$ – MphLee May 20 '13 at 14:40
  • 1
    $\begingroup$ @MphLee In first-order logic, there is not a unique set of natural numbers. That is the meaning of Gödel's incompleteness theorem : there exists two non elementary equivalent models of Peano's arithmetic. An intuitive way to think about it is that Peano's arithmetic does not characterize the natural numbers, but just something much less restrictive. In second order logic, yes, there is absolute categoricity of Peano's arithmetic, but second order logic isn't a good logic in the sense that it is not compact ($\simeq$ proofs aren't necessarily finite). $\endgroup$ – Pece May 20 '13 at 18:12
  • $\begingroup$ @Peace so if I can find what I'm looking for (axioms that describe an unique universe of set) in some set theory expressed in "2"nd-order logic? Can you tell me where to look? $\endgroup$ – MphLee May 20 '13 at 18:42
  • 1
    $\begingroup$ @MphLee Formalizing set theory in second-order logic is a bit dubious, since second-order predicates (which are what differentiates second-order from first-order logic) are, in some sense, already sets. That makes a set theory formalized in using second-order predicates not terribly convincing... $\endgroup$ – fgp May 20 '13 at 22:32

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.