I've been given a task that reads:

Prove that given formulae is correct with the use of set theory axioms: $(\forall a)(\exists b)(\forall c)((c \in b) \iff (\exists d \in a)(c \subset d))$

Now, how I interpret it: For every set a there exists a set b, which is a power set of some element from set a. Some friends have suggested another possible interpretation, that would expect b to be a set of power sets of all emelements from a.

I want to ask what's the correct interpretation here, why is the other one wrong and if there are some rules according to which I'd be able to decide what interpretation is right if I'm presented with similar task in the future.

The rest of the task is fairly straightforward, I use axiom of power sets to prove the existence of the power set and then something like axiom of existence which proves that every set has at least one element in it. The main problem lies in the interpretation.

  • $\begingroup$ What does $d>\in a$ mean? $\endgroup$ – Asaf Karagila Feb 7 '16 at 21:16
  • $\begingroup$ Oh, just a misclick, sorry for that. Corrected. $\endgroup$ – Eugleo Feb 7 '16 at 21:19

It appears that the set $b$ is the set of subsets of elements of $a,$ i.e.: the union of the set of all power sets of the elements of $a.$

Notationally, $$b=\bigcup\bigl\{\mathcal P(d):d\in a\bigr\}.$$

Your interpretation turns out to be correct precisely when $a$ has exactly one element. Your friends' interpretation is close, but off by a level.

The biconditional says that (1) every element of $b$ is a subset of some element of $a,$ and that (2) if $c$ is a subset of an element of $a,$ then $c$ is an element of $b.$

This needn't be a power set, nor a set of power sets! For example, suppose we have distinct sets $s_1,s_2,s_3$ and consider $$a=\bigl\{\{s_1\},\{s_2,s_3\}\bigr\}.$$ Then $b$ has $2^1+2^2-1=5$ elements, so isn't a power set. On the other hand, by choosing the sets $s_j$ appropriately, we can likewise ensure that none of the elements of $b$ is a power set.

As a side note, I've never heard of the "axiom of existence" to which you refer, since it seems, as a ready consequence of that "axiom," that the empty set doesn't exist. The usual Axiom of Set Existence simply asserts that there is a set $x$, without telling us anything else about it. Applying the Axiom of Comprehension Schema to this set $x,$ we have that $$\{w\in x:w\ne w\}$$ is a set, which necesarily has no elements.

  • $\begingroup$ Wait, why $\varnothing$ does not exist? $\endgroup$ – Asaf Karagila Feb 7 '16 at 22:37
  • $\begingroup$ To quote the OP: "every set has at least one element in it." Of course, it's probable that that's a mistake on the OP's part. $\endgroup$ – Cameron Buie Feb 7 '16 at 22:44
  • $\begingroup$ Oh, I didn't notice that part. :-) $\endgroup$ – Asaf Karagila Feb 7 '16 at 22:52
  • $\begingroup$ Also, one thing doesn't seem clear to me - in the 1st paragraph you say that b is "the union of the set of all power sets of the elements of a". Then, few paragraphs later "This needn't be a power set, nor a set of power sets" and "none of the elements of b is a power set". So, is b set of all power sets or not? $\endgroup$ – Eugleo Feb 8 '16 at 4:33
  • $\begingroup$ @Sh4rPEYE: It is not the set of all power sets of elements of $a.$ Rather, it is the union of said set of all power sets. Consider the example $a$ from my post. The set of all power sets of elements of $a$ is $$\Bigl\{\bigl\{\emptyset,\{s_1\}\bigr\},\bigl\{\emptyset,\{s_2\},\{s_3\},\{s_2,s_3\}\bigr\}\Bigr\},$$ but $$b=\bigl\{\emptyset,\{s_1\},\{s_2\},\{s_3\},\{s_2,s_3\}\bigr\}.$$ This is what I mean when I say your friends were "off by a level". $\endgroup$ – Cameron Buie Feb 8 '16 at 12:33

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.