• Support PF! Buy your school textbooks, materials and every day products Here!

Proof on Family of sets - Looking for Help OR Feedback

  • Thread starter Kolmin
  • Start date
  • #1
66
0

Homework Statement



Given that [itex]F[/itex] is a family of sets, that [itex] \bigcup F[/itex] is the union of the sets members of the family [itex]F[/itex], that [itex]A[/itex] is a set, assume that

(1) [itex] \hspace{1cm} \forall F (\bigcup F = A \rightarrow A \in F) [/itex]

then prove that

(G) [itex] \hspace{1cm} \exists x (A= \left\{ x \right\} ) [/itex]

Homework Equations



Given that [itex]P \rightarrow Q[/itex] is the same as [itex]\neg P \vee Q[/itex], we can rephrase the assumption as

(2) [itex] \hspace{1cm} \forall F (\bigcup F \neq A \vee A \in F) [/itex]

The Attempt at a Solution



That's the biggest problem: I have no idea how to get the solution.
Just to remember, I am fighting with the software Proof Designer: I love and hate it. I love it when it tells me I got the proof, I hate it when it doesn't... so right now I am hating it (or maybe I am hating myself!).

Btw, a nice part of the program is that it gives you the possibility to proceed in the proof even if you have no idea what - in this specific case - [itex]F[/itex] and [itex]x[/itex] are... which is exactly my situation! The program does it in order to mimic the way in which proofs actually work. You go around, you assume, and then you define... and everything goes right. Usually, but not this time.

First of all, just a confirmation of my general thought about the theorem: for whatever [itex]F[/itex] you pick up, you can always find an [itex]A[/itex] that has some characteristics (which have to be really specific).
So, basically we can vary [itex]F[/itex] and we will always find a corresponding [itex]x[/itex] that respect (1) or (2).
Right?

About the solution. I focused a lot on (2), and then I tried to work out a proof by cases. It didn't really work, maybe cause I chose the wrong values for [itex]F[/itex] and [itex]x[/itex]. In particular I put [itex]A= \left\{ ∅ \right\} [/itex] and then [itex]F= \left\{ \left\{ ∅ \right\} \right\} [/itex]. With these choices, the second case is easily covered, while the second simply cannot be solved. This is related to the fact that the assumption is now [itex] \bigcup F \neq A [/itex], a negative statment that is not easy manageable (at least for me).

Now, the problem I found is that, even if I choose a different value for [itex]F[/itex] (let's say [itex]P(A)[/itex], defined as the Power Set of A) and wait to find the value for [itex]x[/itex], still I go nowhere. For example, [itex]P(A)[/itex] has some nice properties and it can be used (1) instead of (2), because it can be easily proven that [itex] \bigcup P(A) =A [/itex], giving the possibility to use MP to get [itex]A \in P(A) [/itex]. However, in this case I have no idea what [itex]x[/itex] should be. It's like there is a huge gap between what I am assuming and what I have to prove and I cannot fill it... :confused:

Sorry for the long post, but this problem is really absorbing me.
I would really appreciate any kind of feedback. :smile:
 
Last edited:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
955
I am a bit confused by your "Given that F is a family of sets" and "[itex]\forall F[/itex]". Ther first implies that we are talking about a specific family of sets but the second talks about "all families of sets". I will assume you mean the second: for all possible families of sets, if set A is equal to the Union of all sets in the family implies that A is in the family, then A is a singleton set.

I don't know what you mean by "I chose the wrong values for F and x"- we cannot "choose" F and x, we must prove this for any F and any set A satisfying the hypotheses. I also am not clear whether you intend "∅" to indicate the empty set or the number "0" because you talk about "{∅}" which would make sense either way.

Are you asked to prove this or determine whether it is true or false? Because it appears to me to be false and then we can choose a specific "F" to give a counter-example. If [itex]F= \{\phi\}[/itex]- that is, if F is the family containing only the empty set- its union is the empty set so "[itex]A= \cup F[/itex]" is true only if A is the empty set. But then [itex]A= \phi\in F[/itex] is true so the hypothesis is satisfied. But there is NO x such that "[itex]x\in A[/itex]" because A is empty.
 
  • #3
66
0
First of all, thanks (really) a lot! :smile:

I am a bit confused by your "Given that F is a family of sets" and "[itex]\forall F[/itex]". Ther first implies that we are talking about a specific family of sets but the second talks about "all families of sets". I will assume you mean the second: for all possible families of sets, if set A is equal to the Union of all sets in the family implies that A is in the family, then A is a singleton set.
Indeed, definitely the second. Trying to be precise, I ended up being sloppy. With the expression "Given that F is a family of sets" I wanted to say something like "Defining F as a family of sets".
[Hopefully this formulation should be right.]

I don't know what you mean by "I chose the wrong values for F and x"- we cannot "choose" F and x, we must prove this for any F and any set A satisfying the hypotheses.
Ok, right. I expressed myself in the wrong way, but still I am not sure about the real goal of this proof. Can we say that the all game is about finding an x that works given a certain F (like F varies everytime x varies)? Or the goal is to find a x that is like THE JOLLY, that fixes the problem whatever F we choose to put in the hypothesis?
I am inclined towards the second, but I am not really sure.

I also am not clear whether you intend "∅" to indicate the empty set or the number "0" because you talk about "{∅}" which would make sense either way.
Well, in my formulation ∅ is the empty set, while {∅} is the set containing the empty set (so this set contains one element, the empty set).

Are you asked to prove this or determine whether it is true or false?
Considering that this is a selected problem that should be solved with Proof Designer, I assume I have to prove it. Or - well- , I really hope so... :smile:
It would be sadistic from Professor Velleman to put on his site a problem that cannot be proved! :devil:

Because it appears to me to be false and then we can choose a specific "F" to give a counter-example. If [itex]F= \{\phi\}[/itex]- that is, if F is the family containing only the empty set- its union is the empty set so "[itex]A= \cup F[/itex]" is true only if A is the empty set. But then [itex]A= \phi\in F[/itex] is true so the hypothesis is satisfied. But there is NO x such that "[itex]x\in A[/itex]" because A is empty.
Now, this is interesting. I kinda had a sudden enlightment. After your counterexample I realized that it shouldn't work cause maybe I gave you a wrong info. As a matter of fact, I kinda guess that the formulation of (G) implies that A is a family of set itself. I think so because it's part of the game with Proof Designer that you cannot insert whatever you want if it has not been previously defined. So, for example, I cannot build up A with some random elements (following the structure of the software, I cannot insert for x a random object if it has not been defined like A={a,b,c,d}). On the contrary I can insert ∅. So, we can have A={∅}, which is a family of set, and having F={{∅}} the counterexample shouldn't work.
 
  • #4
66
0
On the contrary I can insert ∅. So, we can have A={∅}, which is a family of set, and having F={{∅}} the counterexample shouldn't work.
Wait a second, if A is a family of set as it should be (as I realized too late), are you telling me that what I wrote in the quoted part is a sketch of a proof of the statement? Cause if it is so, I really don't see why. However in this case we have that if U{{∅}}=A then A is a member of {{∅}}, which is the case as far as we pick A={∅}. So it's ok.

But... is it really a proof? Actually I don't see why, and definitely the software doesn't help me to see that it is.

This should also be a sort of answer to my major doubt: how I have to set those kind of problems. It seems there are two possibilities:
1) If this is a proof, it means that first we pick a value for A, and then we prove that it works picking a value for F.
2) However, to be honest, I think the way in which all those kinda problems should be faced is more about: giving a value of A (which is the PERFECT value), whatever F we take, the situation stands. So, in this case we would have that, letting A={∅}, whatever F we choose (it can be F={{∅}}, but F=P(A) as well), that value of A={∅} works.
Now, if case 2 is the right one (and I really think so), I have no idea how this can be proved and I would say that the statement is generally false.
[Sorry HallsOfIvy, I am kinda slow, but considering all the confused ideas I have, it's not that clear cut to me if it's false or not, so maybe you will forgive me... :smile:]

Sorry, I really don't wanna bother with this problem, but it's not cause I have exams or assignaments or whatever. I am studying this stuff by myself so... it's simply cause I wanna sleep without dreaming about it (as it happened yday)! :smile:
 
  • #5
66
0
Just wondering, is the proof of this statement obvious or there is something problematic and I am not the only one who is having problems?

By the way, if you are wondering on how I found it, that's the site (Problem no.44):
http://www.cs.amherst.edu/~djv/pd/help/Problems.html

Last question, can somebody tell me what is the right way in which statements of this form (existence proof embedded in conditional statements, where the premis has a universal quantifier) have to be approached?

Thanks as always! :smile:

PS: Obviously, if the moderators have the feeling that this problem is not particolarly relevant for this part of the forum, no problem if they move it somewhere else. As far as I go somewhere with this proof, I am happy!
 
Last edited:

Related Threads on Proof on Family of sets - Looking for Help OR Feedback

  • Last Post
Replies
6
Views
2K
Replies
3
Views
1K
Replies
7
Views
9K
Replies
8
Views
2K
Replies
20
Views
2K
  • Last Post
Replies
10
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
6
Views
6K
  • Last Post
Replies
13
Views
4K
  • Last Post
Replies
3
Views
509
Top