1. ## theorem about two sets (enderton)

Hi

Here's a problem from Enderton's set theory book (1977) page 39.

"Assume that A and B are given sets and show that there exists a set C such that
for any y

$y\in C\Leftrightarrow \exists x \in A(y=\{x\}\times B)$

In other words, show that $\{\{x\}\times B\lvert x\in A\}$ is a set "

since this is an existence statement, I am unsure as to how to cook up C.

can anybody give some direction ?

2. ## Re: theorem about two sets (enderton)

Think of ways to cook sets:

The obvious way is to cook "up" to make a set and then cook "down" using separation to get your desired set.

Now, what are some ways to cook "up" sets? Well, pairing, union, power, for example ... Think of using one of those.

3. ## Re: theorem about two sets (enderton)

I was thinking if we can choose

$C=\{\{x\}\times B\;\lvert x \in A\}$

4. ## Re: theorem about two sets (enderton)

That's the set we want to PROVE exists as described.

We have sets A and B, so we want a set S constructed (by already given methods) from A and B such that for each x in A, we have {x} X B is in S. Then we'll use separation to cut S down to ONLY those sets of the form {x} X B for some x in A.

One of our already given methods is Cartesian products. So we have A X B. Now, think about applying one of these - pairing, union, power set - to A X B to get our set S.

5. ## Re: theorem about two sets (enderton)

moeblee

let me put the problem in complete logical langauge.
Assume that A and B are given sets.. show that

$\exists C\forall y[y\in C\Leftrightarrow \exists x \in A(y=\{x\}\times B)]$

in existence theorem, we first claim that let x be such an object and then set out to prove that x satisfies the properties given in the theorem. since the problem i stated is an existence problem , can't we claim that C be equal to

$C=\{\{x\}\times B\;\lvert x\in A\}$

and then set out to prove the property that

$\forall y[y\in C\Leftrightarrow \exists x \in A(y=\{x\}\times B)]$

and another question.... when Enderton says that "show that ..... is a set"
what does it mean ? how does one show that some thing is a set. according to
Set (mathematics) - Wikipedia, the free encyclopedia
set is taken as an "undefined primitive" in axiomatic set theory. so how do we prove something is a set if definition of set is not there.

6. ## Re: theorem about two sets (enderton)

The only set whose existence is explicitly stated by the standard axioms of set theory is $\emptyset$. Several other axioms give rules of creating new sets out of sets whose existence we have already estabilished. For example, the axiom of pairing tells us that if A and B are sets, then also {A,B} is a set. Without knowing that some sets A and B do actually exist, this wouldn't tells us much. But we do know that the empty set exists. So let

$A :=\emptyset$
$B :=\emptyset$

The axiom of pairing now tells us that $\{\emptyset,\emptyset\}$ is a set. By the axiom of extensionality we have $\{\emptyset,\emptyset\}=\{\emptyset\}$.
Thus $\{\emptyset\}$ is a set.

This is how it works.

7. ## Re: theorem about two sets (enderton)

Originally Posted by issacnewton
show that

$\exists C\forall y[y\in C\Leftrightarrow \exists x \in A(y=\{x\}\times B)]$
Right.

Originally Posted by issacnewton
in existence theorem, we first claim that let x be such an object and then set out to prove that x satisfies the properties given in the theorem.
What we need to do in this problem is find a C that satisfies the property:

Ay(y in C <-> Ex(x in A & y = {x} X B))

Originally Posted by issacnewton
can't we claim that C be equal to

$C=\{\{x\}\times B\;\lvert x\in A\}$
As long as you keep in mind that merely wrtiting out something in set abstraction notation doesn't entail (in all this, we're in Z set theory, or in later chapters, ZF or ZFC) that there is an object that has the property described. For example:

We can write

J = {y | y not in y}

but there is no J such that Ay(y in J <-> y not in y).

Originally Posted by issacnewton
$\forall y[y\in C\Leftrightarrow \exists x \in A(y=\{x\}\times B)]$
Okay, but that's not advancing the answer any further than from where you started.

The problem is simpler than you seem to think it is. I gave you a direct hint:

Take A X B. Find a set C that you can build up from A X B so that if x in A we have {x} X B is in C. To build up such a C from A X B, which of these do you think is a good building tool in this case - pairing, union, or power? Answer that question and you've basically solved the problem.

Originally Posted by issacnewton
[when Enderton says that "show that ..... is a set"
You already stated it okay. For example, in this case, to say show "{y | Ex(x in A & y = {x} X B} is a set" means: Using first order logic (whether formal or informal) applied to the axioms of set theory show ECAy(y in C <-> Ex(x in A & y = {x} X B)). In other words, show that the set abstraction notation "{{x} X B | x in A}" PROPERLY refers, i.e. that there is a set C having the property Ay(y in C <-> Ex(x in A & y = {x} X B)).

Originally Posted by issacnewton
Set (mathematics) - Wikipedia, the free encyclopedia
set is taken as an "undefined primitive" in axiomatic set theory. so how do we prove something is a set if definition of set is not there.
(1) Enderton is not using 'set' in such a formal sense, as an actual predicate (whether primitive or defined). He's using it in the informal sense just discussed. Indeed, in the context of Z set theories (including, e.g., Z , ZF, ZFC), we don't have to mention the word 'set' at all. When Enderton uses the word 'set' in such a context we can couch whatever he says without using the word 'set'. For example, in the problem you quoted, you could just as well state it:

Show that there exists a C such that for all y, we have y in C <-> Ex(x in A & y = {x} X B).

That's all there is to it in Z set theories. Mentioning the word 'set' in that context is not necessary.

(2) As to the more technical point, if we're very precise about the matter (and not just speaking somewhat loosely as some set theory intro chapters are wont to do) it is NOT the case that 'set' is a primitive of Z set theories. Yes, in CLASS theories such as NBG, the predicate 'is a set' is primitive. But it is NOT primitive in Z set theories. As a mere formality we could DEFINE 'is a set' in Z set theory, but it would be trivial since, in Z set theory, our definition would provide the thereom "Ax x is set". (In NBG it is NOT the case that "Ax x is set" is a theorem.)

8. ## Re: theorem about two sets (enderton)

Originally Posted by ymar
The only set whose existence is explicitly stated by the standard axioms of set theory is $\emptyset$.
Actually, the existence of a unique empty set is provable from the axiom schema of separation.

9. ## Re: theorem about two sets (enderton)

Originally Posted by MoeBlee
Actually, the existence of a unique empty set is provable from the axiom schema of separation.
That's true, but the axiom is usually included nevertheless, at least in my country.

10. ## Re: theorem about two sets (enderton)

naively, i would think it helpful to note that {x} x B ought to be a subset of A x B given that {x} is a subset of A....so i would be inclined to obtain all subsets of A x B to have at my disposal...

11. ## Re: theorem about two sets (enderton)

moeblee, I think I sort of get what you are saying. Maybe I read too much in that problem. I have downloaded another book by J. Donald Monk, which is about Morse-Kelley set theory. In that book, he says set is something which belongs to something other. If some object is not member of some bigger stuff, then that object is not a set. Thats how he eliminates Russell's paradox. So there is this sharp distinction between sets and classes. I find that a better approach. There is more clarity. I don't know why ZFC is follwed more widely. I know only basic logic, so lot of things which are discussed about the differences between these theories is beyond me. That's why I decided to learn set theory from Enderton, which follows ZFC.
Originally Posted by MoeBlee
Take A X B. Find a set C that you can build up from A X B so that if x in A we have {x} X B is in C. To build up such a C from A X B, which of these do you think is a good building tool in this case - pairing, union, or power? Answer that question and you've basically solved the problem.
I played with some example sets A and B. I think we will first need to take $\mathcal{P}(A\times B)$. C can be extracted from there, right ?
But which axioms then we use to extract the required C ?

12. ## Re: theorem about two sets (enderton)

perhaps the separation schema could then be invoked to specify the element of P(AxB) which has the properties you seek? just a random guess....

13. ## Re: theorem about two sets (enderton)

is separation schema same as subset axioms ? enderton talks about subset axioms but there is no mention of separation schema.......

14. ## Re: theorem about two sets (enderton)

Originally Posted by issacnewton
[a] set is something which belongs to something other.
A set is a class that belongs to a class. Urelements (if they are any) also belong to a class, but are not sets.

Usually, we have a certain distinguished object, that I'll call 'the empty class', and the empty class has no members. Then for any object x there are six possiblities:

(1) x is the empty class and x is a member.
(1a) x is the empty class and x is not a member.
(2) x is not the empty class and x has no members and x is a member.
(2a) x is not the empty class and x has no members and x is not a member.
(3) x has members and x is a member.
(4) x has members and x is not a member.

With (1) we call x 'the empty set' or '0'.
Usually, (1a) does not occur.
With (2), we say x is an urelement.
Usually, (2a) does not occur.
With (3) we say x is a non-empty set.
With (4) we say x is a proper class.

Then also:

x is a set iff (x is the empty set of x is a non-empty set)
x is a class iff (x is a set or x is a proper class)

Originally Posted by issacnewton
I don't know why ZFC is follwed more widely.
Possible reasons (1) We don't need proper classes to do the mathematics that set theory is called on to do, so it is easier to not have to qualify whether something is a set or a proper class. (2) Z set theories require only one primitive non-logical symbol, viz. 'e', but class theories require two primitive non-logical symbols, viz. 'e' and 'is a set'. (3) Z set theory historically came before class theory and so it got more use through habit among mathematicians.

There are advantages to using class theories though. For example, sometimes we do want to talk about certain classes that are "too big" in set theory and to do that with set theory we end up going to the meta-language to talk about formulas in place of classes. For example, with Z set theories, instead of talking about the class of ordinals, we have to instead, in the meta-language, talk about the FORMULA 'x is an ordinal' and formulate theorems as schemata.

Originally Posted by issacnewton
take $\mathcal{P}(A\times B)$. C can be extracted from there, right ?
Right.

Originally Posted by issacnewton
But which axioms then we use to extract the required C ?
As is typical for such problems, we take an instance of the axiom schema of separation.

15. ## Re: theorem about two sets (enderton)

Originally Posted by issacnewton
is separation schema same as subset axioms ?
With Z set theories, we often refer to the axiom schema of separation as "subset axioms", but in class theories, such as NBG, the subset axiom is a somewhat different thing.

Originally Posted by issacnewton
enderton talks about subset axioms but there is no mention of separation schema
I don't have the book with me, but are you sure Enderton doesn't call it the 'axiom schema of separation'?

Anyway, in Z set theories, the basic concept of the axiom schema of separation is that when we have a set S, we also have any subset of S defined by a formula. The axiom schema of separation is what provides us subsets of sets as those subsets are defined by some condition.

So in the case, let S = P(A X B) and the condition is "Ex(x in A & y = {x} X B)". Then the axiom schema of separation gives us the subset of S that is {y | Ex(x in A & y = {x} X B)}.