Question about proving range(f) is a set by comprehension
Dave L. Renfro
to work his way through Henle's book:
James M. Henle, "An Outline of Set Theory",
Dover Publications, 1986/2007.
This past Saturday we were looking at the following
theorem/problem in Henle's book:
(p. 12) 1.9 Theorem. If f is a function
then the range of f is a set.
In what follows, "U" is "union", "E" is "there exists",
and "<a,b>" is "ordered pair (a,b)".
Henle's solution (p. 99) at one point has the following
for the range of f and then quotes the Comprehension
Axiom:
{x in UU(f) : (Ey)(Ez)(z = <y,x> and z in f)}
My question is why the extra quantifier "(Ez)"?
What logical issue am I missing/overlooking by just
writing the following, which is what we wrote down
before looking at the solution?
{x in UU(f) : (Ey)(<y,x> in f)}
Dave L. Renfro
Ask me about System Design
Without knowing more of the context, I guess that Henle
is making sure that the constructions being used create
sets. I also guess that this is near the beginning of
the book, where many constructions are introduced. Also,
it may be that the axioms needed at this point
(Separation ?) have the form
(E stuff)(Ez) ( P(stuff,z) and z in something)
to define a subset of something that satisfies property P.
Gerhard "Ask Me About System Design" Paseman, 2009.06.18
victor_me...@yahoo.co.uk
> This past Saturday we were looking at the following
> theorem/problem in Henle's book:
>
> (p. 12) 1.9 Theorem. If f is a function
> then the range of f is a set.
>
> In what follows, "U" is "union", "E" is "there exists",
> and "<a,b>" is "ordered pair (a,b)".
A la Kuratowski?
> Henle's solution (p. 99) at one point has the following
> for the range of f and then quotes the Comprehension
> Axiom:
>
> {x in UU(f) : (Ey)(Ez)(z = <y,x> and z in f)}
>
> My question is why the extra quantifier "(Ez)"?
> What logical issue am I missing/overlooking by just
> writing the following, which is what we wrote down
> before looking at the solution?
>
> {x in UU(f) : (Ey)(<y,x> in f)}
The language of set theory involves equality and the sole predicate
symbol "in". Now <x,y> is not a term in the language of
set theory per se. This labguage must be extended by definitions
to incorporate expressions like <x,y>. In first-order logic
an expression like <x,y> should have the form Fxy for
a function symbol F. But the language of set theory lacks function
symbols and so <x,y> can't be expressed as a term in this language.
No matter, since "z = <x,y>" can be so expressed
(as a formula with three free variables). Maybe that's why Henle's
avoiding it? Maybe not? (I don't have the book).
In any case the formula "<x,y> in f" can be expressed as a formula
in the language of set theory just as easily....
MoeBlee
They're logically equivalent. Personally, I'd just chalk it up to
verbosity.
By the way (as you probably know), the thereom can be generalized so
that f doesn't have to be a function or even a relation:
ranges:
E!rAy(yer <-> Ex <x y>ef)
and domains:
E!dAx(xed <-> Ey <x y>ef)
MoeBlee
Dave L. Renfro
>> Henle's solution (p. 99) at one point has the following
>> for the range of f and then quotes the Comprehension
>> Axiom:
>>
>> {x in UU(f) : (Ey)(Ez)(z = <y,x> and z in f)}
>>
>> My question is why the extra quantifier "(Ez)"?
>> What logical issue am I missing/overlooking by just
>> writing the following, which is what we wrote down
>> before looking at the solution?
>>
>> {x in UU(f) : (Ey)(<y,x> in f)}
Victor Meldrew wrote:
> The language of set theory involves equality and the sole
> predicate symbol "in". Now <x,y> is not a term in the
> language of set theory per se. This labguage must be
> extended by definitions to incorporate expressions
> like <x,y>. In first-order logic an expression like <x,y>
> should have the form Fxy for a function symbol F. But
> the language of set theory lacks function symbols and
> so <x,y> can't be expressed as a term in this language.
> No matter, since "z = <x,y>" can be so expressed
> (as a formula with three free variables). Maybe that's
> why Henle's avoiding it? Maybe not? (I don't have the book).
>
> In any case the formula "<x,y> in f" can be expressed as
> a formula in the language of set theory just as easily....
I vaguely know what you're talking about, but a few paragraphs
BEFORE Henle's "1.9 Theorem" is the following:
"Notation: Add <a,b> and A x B to L as abbreviations."
By "L", Henle means "the language of set theory", which
consists of what you would expect. Maybe Henle included
this notation note after writing the exercises that follow
and forgot to modify the solutions, although given the
intended use of the book (working out the details in a
self-study situation or for a Moore-method type of course),
my opinion is that little details like this are pretty
important (because so little is given aside from a list
of theorems to prove).
By the way, Henle defines <x,y> the usual way:
<x,y> = {{x}, {x,y}}.
Dave L. Renfro
David C. Ullrich
I suspect victor is right. Explicitly:
Officially there are no "terms" in the language of set theory
because there are no function symbols. The equation
z = <x,y>
is just an abbreviation for, um, I forget the definition
of ordered pairs. Assuming that <x,y> = {x,y} for
simplicity (although that's wrong, this wil illustrate
the point):
saying
z = {x,y}
is also just an abbreviation for
(*) x in z and y in z and Aw (w in z -> w=x or w=y).
The version in the book allows a straightforward
translation to the offiicial version: substitute (*)
for z = <x,y> and you get
(Ey)(Ez)(x in z and y in z and Aw (w in z -> w=x or w=y) and z in f)
With your "simpler" version you can't convert to the
official version by a literal substitution.
>Dave L. Renfro
MoeBlee
wrote:
> Officially there are no "terms" in the language of set theory
> because there are no function symbols.
A variable standing alone is ordinarliy taken to be a term. But I
agree that there are no function symbols and no closed terms.
MoeBlee
Michael Stemper
>Recently, I've begun working with someone who wants
>to work his way through Henle's book:
>
>James M. Henle, "An Outline of Set Theory",
>Dover Publications, 1986/2007.
>(p. 12) 1.9 Theorem. If f is a function
> then the range of f is a set.
>{x in UU(f) : (Ey)(Ez)(z = <y,x> and z in f)}
>
>My question is why the extra quantifier "(Ez)"?
>What logical issue am I missing/overlooking by just
>writing the following, which is what we wrote down
>before looking at the solution?
>
>{x in UU(f) : (Ey)(<y,x> in f)}
I don't have an answer to your question. I'd just like to comment that
I'm at a very similar point in _Axiomatic Set Theory_ by Suppes, and
am constantly running into stuff like this. It's incredibly detailed
and meticulous, and just drives me nuts. It can take me half an hour
or more to get through such a simple theorem, because I have to answer
to myself, for each such qualification, the question "why does he have
to say *this*?"
I just keep telling myself that it'll pay off in the end.
--
Michael F. Stemper
#include <Standard_Disclaimer>
Always remember that you are unique. Just like everyone else.
Dave L. Renfro
> I don't have an answer to your question. I'd just like to
> comment that I'm at a very similar point in _Axiomatic Set
> Theory_ by Suppes, and am constantly running into stuff like
> this. It's incredibly detailed and meticulous, and just drives
> me nuts. It can take me half an hour or more to get through
> such a simple theorem, because I have to answer to myself,
> for each such qualification, the question "why does he have
> to say *this*?"
>
> I just keep telling myself that it'll pay off in the end.
Your post doesn't really need a reply but I appreciated your
comments enough that I wanted to reply anyway. The delay
in my replying is because I took some vacation time from
work, I don't presently have internet access at home, and
I didn't bother to get on the internet at the university
library I spent much of the last few days at.
There always seems to be a fine line between saying too
much (which bugs the more knowledgeable people and possibly
overwhelms those not knowledgeable enough to separate
the forest from the trees) and saying too little (which
can leave the non-expert in the dark, or worse, can leave
the non-expert with a false sense of understanding when
certain omitted details are overlooked by the non-expert).
This "damned if you do and damned if you don't" situation
is one of the reasons I've always liked seeing lots of
different books/papers on whatever topic I happen to be
looking into, and this goes back at least as far as my
middle school years (ages 12-14, early 1970s). However,
other people prefer sticking with a single source (and
they have reasonable sounding explanations for doing so),
such as some of the posters in the following recent sci.math
thread:
General topology books (17-18 June 2009)
http://groups.google.com/group/sci.math/browse_thread/thread/284d0d2daf81ab4f
Dave L. Renfro