There exists a set of all finite sets?

[jeckt]

Homework Statement

There exists a set of all finite sets? Prove your answer.

Homework Equations

The Attempt at a Solution

1. Assume there is a set A of all finite sets
2. Take the power of set of A

This is where i get stuck...what I'm thinking is that there exists a element in the power set that doesn't belong in A and thus leads to a contradiction.

Thanks for the help guys!

 

[micromass]

Do you know whether the set of all sets exist?
In case you do, you can use that: if A is any set, then {A} is a finite set...

 

[jeckt]

Hi mircomass,

yeah It was shown in lectures that a set of all sets doesn't exist. From your second line I gather that:

1. Let A be the set of all finite sets.
2. Take the power set of A, i.e. P(A)
3. Let B = {A,P(A)}.
4. B is finite

Hence contradiction.

Does that make sense? Thanks for the help micromass!

 

[micromass]

Hi mircomass,

yeah It was shown in lectures that a set of all sets doesn't exist. From your second line I gather that:

1. Let A be the set of all finite sets.
2. Take the power set of A, i.e. P(A)
3. Let B = {A,P(A)}.
4. B is finite

Hence contradiction.

Does that make sense? Thanks for the help micromass!

Yes, that makes sense, but you're not quite finished yet. Why is the finiteness of B a contradiction? B being finite only means that B is in A. Thus $$\{A,P(A)\}\in A$$.
Now, we both know that this is absurd, but it isn't quite a contradiction yet. In fact, it might be very possible that there exists sets such that $$\{x,y\}\in x$$. You'll have to say why this can't be true.

For the record, that was not quite the contradiction I was aiming it. I wanted to create a "surjection" between the set of finite sets and the set of sets by putting A --> {A}. This would also lead to a contradiction...

 

[jeckt]

It seems absurd like you stated but i don't seem to be able to prove that the set $$B$$ doesn't exist - I'm trying to apply the axiom of regularity with little luck.

As for what you were trying to achieve - I'm wondering if that's possible with only using the Zermelo-Frankel Axioms. I was thinking on the lines of using the axiom of choice to create the "surjection".

It would be great if you could give me more hints - thanks for all your help so far.

 

[micromass]

Ah, you've seen set theory. That changes a bit

Take A the set of all finite sets, then {A} is a finite set and $$\{A\}\in A$$. Try applying the regularity on this expression, it's a little easier...

But, like you stated, you don't need the axiom of regularity for this. All you need is the axiom of replacement (aka the axiom of substitution). And of course the axiom of choice to create the surjection.

 

[Hurkyl]

All you need is the axiom of replacement (aka the axiom of substitution). And of course the axiom of choice to create the surjection.

Really, you only need the axiom of unions and the theorem there isn't a set of sets for the argument. I think you're approach is more complicated because your arrow's going the wrong way. (A surjection from the class of sets to the class of finite sets doesn't say anything about whether the class of finite sets is a set...)

 

[jeckt]

Ah, you've seen set theory. That changes a bit

Take A the set of all finite sets, then {A} is a finite set and $$\{A\}\in A$$. Try applying the regularity on this expression, it's a little easier...

...that makes life so much easier! (well that's if my solution works now) I've been stuck on this question for over a week - thinking about it every now and then.

So gather from what you hinted.

1. Let $$A$$ be the set of all finite sets
2. Then $$\{A\}$$ is a finite set and $$\{A\}\in A$$
3. Apply the axiom of regularity on $$\{A\}$$.
4. The only element of $$\{A\}$$ is $$A$$ which must be disjoint from $$\{A\}$$.
5. But $$\{A\}\in A$$
6. Thus leads to a contradiction. Therefore set $$A$$ cannot exist

Thanks so much for all the help guys - and it's really cool to see that there are so many different ways to prove this question.

edit: Just woke up and think this is wrong...

 

[jeckt]

Fixed it up:

Let $$A$$ be the set of all finite sets, by the axiom of pairing there exists sets $$\{ A \}$$, $$\{ \{ A \}, A \}$$. Apply the axiom of regularity to $$\{ \{ A \}, A \}$$. There are two elements in $$\{ \{ A \}, A \}$$, consider the element $$\{ A \}$$. Clearly $$\{ \{ A \}, A \} \cap \{ A \} \neq \emptyset$$. Now Consider the second element $$A$$, but since $$\{ A \}$$ is finite then $$\{ A \}\in A$$. Thus $$\{ \{ A \}, A \} \cap A \neq \emptyset$$. Contradiction. Therefore $$A$$ cannot exist and there isn't a set of all finite sets.

hopefully this is right this time...