Thread: Mathematical reasoning and proof: Sets vs Induction?

Hi

I'm reading a book on mathematical reasoning (P J Eccles) and I have a question about proof.

On this subject the book gives and example on the proof by induction that n </= 2^n
(</= is supposed to mean 'less than or equal to')

If you try to prove it numerically you get the series (n) 1,2,3,4,5,6... (2^n) 2,4,8,16,32,64...

But clearly this doesn't constitute proof because you can go on indefinately and not matter how far you calculate there still *could* be some value of n for which the statement does not hold true.

In other words, common sense or intuition does not constitute mathematical proof. This I understand.

However, I found it difficult to continue to read the proof by induction, because I was distracted by a possible alternative that to me was intuitive, using Set theory.

Could you not prove n </= 2^n with the use of sets?

EG if Set A is the set of all positive integers then given the statement n </= 2^n, you have Set B=[2^n] that is a Sub-Set of A. Then for any given limit for n the sum of Set B is always greater than the difference between A and B.

This at least captures the intuition that the series for n^2 increaes much more rapidly than n+1, n2+1, n3+1 etc. and puts into some mathematical context. But it doesn't say anything about any given value of n, n </= 2^n, at least that I can see.


Is there are way to more rigorously prove n </= 2^n using Sets?

Originally Posted by gruff

EG if Set A is the set of all positive integers then given the statement n </= 2^n, you have Set B=[2^n] that is a Sub-Set of A. Then for any given limit for n the sum of Set B is always greater than the difference between A and B.

say the limit is to infinity; doesn't that mean you have to prove that the sum of set B is always greater than the difference between A and B for every value of n?

Originally Posted by wallaby

Originally Posted by gruff

EG if Set A is the set of all positive integers then given the statement n </= 2^n, you have Set B=[2^n] that is a Sub-Set of A. Then for any given limit for n the sum of Set B is always greater than the difference between A and B.

say the limit is to infinity; doesn't that mean you have to prove that the sum of set B is always greater than the difference between A and B for every value of n?

If you set the limit to infinity yes. That is what is implied by the statement anyway and is the reason why you can't prove it numerically. Question I'm asking is that if you set the limit to any real value less than infinity then it clearly is true that the sum of B is greater than the sums of A-B. Logically then for any real value limit you can have the limit+1 where the partial statement (B>(A-B) is still true. Which is a start at least, despite that it is not any kind of proof of the whole statement (and possible not a proof of the partial statement either!).

What I want to know is if a complete proof using sets is possible?

Sorry Wallaby, I may have not got what you meant - do you mean, that it's no kind of proof at all because it doesn't address the issue of whether the statement is true for *each and every* value of n?

consider the function: f(n)=n-2^n
f is continuous in R(the set of real numbers)
It is also differentiable so that f'(n)=1-(ln2)*(2^n)
''(the * symbol is used for multiplication)(ln:the natural logarithm)''
the roots of f'(n) are found:
f'(n)=0 => n=-ln(ln2)/ln2 => n~0,5
so f is monotone increasing in (-00 , 0,5]and monotone decreasing in [0,5 , +00) ''(00:infinity)''
By considering the facts that f is continuous and monotone, the values of
f(n) are (lim[f(n)],n goes to -00 , f(0,5)] for (-00 , 0.5] and [f(0,5) , lim[f(n),n goes to +00) for [0.5 , +00) => (-00 , -0,94] for both of them.
Let's notice that 0 (zero) is not included in the values field for f(n).
This means that f(n) has no roots in R.
As a consequence of Bolzano's theorem:Every continuous function which has no roots in a set of numbers (this set is R for our proof) can be only positive,only negative or just a constant function.
This function is not constant.
It is negative for every n in R.
(we can see it from the set of values (-00 , -0.94])
So f(n)</=0 for every n in R.
Then: n-2^n</=0 => n</=2^n for every n in R.


***I am not familiar with the scientific terms in english because I live in Greece.If you want any further explanation just ask for it.***

Originally Posted by gruff

Sorry Wallaby, I may have not got what you meant - do you mean, that it's no kind of proof at all because it doesn't address the issue of whether the statement is true for *each and every* value of n?

yea thats pretty much it.

my set theory is a little rusty but to me it seems like you would still have to go manually proving it numerically.

if you wanted to prove it for the positive integers and proved it for say all positive integers between 1 and 1000. that doesn't put you any closer to proving it for the positive integers because the positive integers are an infinite set.

Originally Posted by wallaby

Originally Posted by gruff

Sorry Wallaby, I may have not got what you meant - do you mean, that it's no kind of proof at all because it doesn't address the issue of whether the statement is true for *each and every* value of n?

yea thats pretty much it.

my set theory is a little rusty but to me it seems like you would still have to go manually proving it numerically.

if you wanted to prove it for the positive integers and proved it for say all positive integers between 1 and 1000. that doesn't put you any closer to proving it for the positive integers because the positive integers are an infinite set.

Yeah, I see. I can't help feeling instinctively that there is a solution using sets (possibly in combination with something else). Either way I'm stuck because I need it clarified - that it definitely CAN'T be done with sets.

Is there something inherent in the axioms of set theory that means you can't use sets to prove this?

Anyone?

Well, OK I just read that Set Theory is THE MOST fundamental concept in mathematics and is used to define all other mathematical concepts.

So it would seem that my intuition that set theory could be used to prove this has at least something going for it, as it's getting at the very core of mathematical reasoning.

Just because Set Theory is at the heart or all mathematical concepts though does it mean you can prove the statement n</= 2^n just using Set theory?

someone help, I'm going mad otherwise!

Originally Posted by gruff

Well, OK I just read that Set Theory is THE MOST fundamental concept in mathematics and is used to define all other mathematical concepts.

So it would seem that my intuition that set theory could be used to prove this has at least something going for it, as it's getting at the very core of mathematical reasoning.

Just because Set Theory is at the heart or all mathematical concepts though does it mean you can prove the statement n</= 2^n just using Set theory?

someone help, I'm going mad otherwise!

well there you have it.
any method of proof will be built from sets.

Originally Posted by gruff

Just because Set Theory is at the heart or all mathematical concepts
though does it mean you can prove the statement n</= 2^n just using
Set theory?
someone help, I'm going mad otherwise!

No, because sets are not in general ordered, so you can't really ask if one element of a set is greater than another.

But why not just use induction? Let m be in R such that 2^m = m

Note first that, for m, p in R, 2^{m + p} = (2^m)(2^p) Note also that 2¹ = 2.

Let p = 1, then 2^{m + 1} = 2m > m, and in general, for any non-negative p, 2^{n + p} ≥ n for all n in R.

Let p = 0. 2⁰ = 1, so 2^{n + 0} = 2ⁿ ≥ n by the above.

Originally Posted by Guitarist

But why not just use induction?

Because I'm trying to understand mathematics, not prove the statement. Knowing something is not the same as understanding it!

I *know* the statement can be proved by induction, because I'm reading a book about it and it has the proof as an example of mathematical reasoning, but that is not the point of my post.

I want to understand *why*. If you ask why then you end up at sets. Which is good, because as I've found out set theory is at the heart of mathematics, so at least I know that I am asking the right questions!

Perhaps the question should be rephrased:

Can you explain proof by induction in the language of Set Theory?

So what about this then:

Given a set of posivitve real numbers with a limit=n (call it [A']), the set of positive real numbers given by 2^n (call it [B']) is NOT a subset of it.

In fact the only case where [B'] is a subset of [A'] is when n=infinity.

I think to get to the part about each and every case for n you need another bit of the puzzle:

For every set [A'] with a given value of the limit n, there is another set with the limit n+1. Given that for the single case of the set of n=1, the set 2^1 is not a subset of it. If you take that 1+1=2 to be true and that N^n >/= N (for positive reals only) you can do this for each and every value of n and still not have 2^n be a subset of [A'].

Originally Posted by wallaby

Originally Posted by gruff

Well, OK I just read that Set Theory is THE MOST fundamental concept in mathematics and is used to define all other mathematical concepts.

So it would seem that my intuition that set theory could be used to prove this has at least something going for it, as it's getting at the very core of mathematical reasoning.

Just because Set Theory is at the heart or all mathematical concepts though does it mean you can prove the statement n</= 2^n just using Set theory?

someone help, I'm going mad otherwise!

well there you have it.
any method of proof will be built from sets.

Indeed. But I don't feel the connection between the concept of sets to induction. This is the limit of my understanding that I'm trying to fix!

Originally Posted by gruff

Can you explain proof by induction in the language of Set Theory?

Im not sure if this is what you want, but here is how induction is framed in terms of set-theory.

For starters you need to understand the idea of a well ordered set. To start off you need to know what a well ordering is.

A partial ordering < on a set X is a relation on that set (formally a subset of X²) which is transitive (a<b & b<c => a<c) , anti-symmetric (a<b & b<a => a=b) and reflexive (a<a forall a in X). An easy example is the ordering on the Naturals we are dealing with here, "smaller then or equal to" is a partial order on the set of naturals (in fact the definition of a partial ordering is based on the normal ordering on the naturals).

A set is called totally ordered if you can compare any two elements of that set (i.e. forall x, y in X either x<y or y<x). Obviously the set of naturals is totally ordered, however the power set of the naturals with set containment as the partial ordering is not totally ordered as it is not the case that given two subsets of the naturals A and B that either A is contained in B or B is contained in A.

Finally a set is called well-ordered if it is totally ordered and every (EDIT: nonempty) subset of that set has a minimum element. The naturals once again are well ordered, but the set of integers is not (what is the minimal element of the set of negative integers?)

Now it is the well ordering of the naturals that allows induction to work. The standard proof is this, lets suppose that for some property P(n) on the naturals we have that the truth of P(k) implies the truth of P(k+1) and that P(0) is true. Now consider the set A consisting of all the natural numbers for which P(n) is not true i.e. A = {n in N : P(n) is false}. Now as the natural numbers are well-ordered this set has a least element, m which is strictly greater then zero. But that implies that P(m-1) is true, and thus P(m) is true - which is a contradiction. So the set A must be empty and thus P(n) is true for all naturals.

Ah man, the more I read about set theory the more beutiful it seems to me. Thanks it's cleared things up a lot. I think if I can really absorb set theory I will have a sound grounding for the rest of mathematics (which I don't feel I have now).

You know, I've had to unlearn years or standard maths education so that I can understand things properly.

Why the hell do we start with numbers in elementary mathematics, it's implied they are fundamental when they're not. Its crazy, it's f***ed up my whole understanding of maths!

Most probably (and i dont want to burst your bubble here) since naive set theory also does not work and you have to work in ZF (with or without Choice, depending on your flavour of mathematics). But Zermelo-Frankel Set theory is quite scary if you are not used to mathematical abstraction and formalism - numbers seem more concrete and understandable.

Originally Posted by river_rat

A partial ordering < on a set X is a relation on that set (formally a subset of X²)

Eek! The use of X² for the Cartesian product I do not like, although I am aware it is common notation for, say, R x R, E x E x E, etc. Maybe just a personal foible, though.

Anyway, as long as we are doing order theory, let me throw in my two pennie's worth.

river_rat succinctly explained 3 out of the 4 order relations I know of. The fourth is similar to the partial order, but without the requirement for anti-symmetry. It's called a pre-order, which I like best like this:

Let x, y and z be in N. If x|z (x divides z), then x ≤ z in some order on N. We may also have y|z, y ≤ z, but x not divide y. That's a preorder. That is, both x and y are comparable to z but not to each other.

Note the difference that river_rat gave between a total order and a well-order: if for all x, y in N there exists a relation x ≤ y (total order) and if there is some z in N s. t. x ≤ z and y ≤ z then N is well ordered; this is latter is also referred to as the "directedness" property (is that a word?).

But, a pre-ordered set can also be directed. For, suppose lcm{x,y} is the lowest common multiple of x and y. Obviously, x|lcm{x,y} and y|lcm{x,y}, thus x≤ lcm{x,y} and y ≤ lcm{x,y}. So this set is directed. But it need not be the case that x|y (or v.v.), so we have a directed pre-order.

Directed pre-orders are nice, for a number of reasons. Consider the "sequence" x ≤ y ≤ z in some pre-order. Let's call it a chain, like everone else. In N, ordered but with no sense of direction, there may be an infinity of such chains all going in different directions. In a directed set this can never happen: there will always be some element of N less than each element of each chain.

This translates nicely to topology, but there's the phone.

Originally Posted by river_rat

Most probably (and i dont want to burst your bubble here) since naive set theory also does not work and you have to work in ZF (with or without Choice, depending on your flavour of mathematics). But Zermelo-Frankel Set theory is quite scary if you are not used to mathematical abstraction and formalism - numbers seem more concrete and understandable.

Numbers are abstractions in the most specific sense after all, and to me do not represent much that is concrete, unless you can accept them in their fundamental abstraction without worry. I haven't studied ZF (or ZFC, inc. choice) only skimed over it. I realise that it is totally necessary for me to understand set theory if I am to have any luck with mathematics at all - I am not interested in learning rules, I want to understand things. I'm not afraid of complex concepts, in fact on the contrary!

I'm studying naive set theory to aclimateize myself, but already I came across limitations.

There's Russell's paradox: Let M be the set of all sets tha do not contain themselves as a member. If M doesn't contain itself then its a member of the set, which is a contradiction!

Also I notice that the empty set is a member of every set, but then the empty set must also be a member of itself, which is contradictory in the same sense as the above (or someone correct me if my understanding is wrong?)

So NST is not perfect, but I can accept its limitations for the moment because in principal its teachning me something fundamentally useful so I can move forward (which I was having difficulty doing with numbers because it was always clear to me that my understanding was incomplete).

Hey guitarist.

It was either X² or X x X - i think i picked the lessor of two evil notations for a forum (why cant we have a latex interpreter?)

I see we are on the way to nets. I prefer filters (but then again they are ubiquitous in my work)

Originally Posted by river_rat

Hey guitarist.

It was either X² or X x X - i think i picked the lessor of two evil notations for a forum (why cant we have a latex interpreter?)

yes, it is weird that a "science forum" does not enable LaTex. Ho hum.

I see we are on the way to nets. I prefer filters (but then again they are ubiquitous in my work)

Yes I was thinking of nets. I know less about filters (but not nothing), obviously you know a great deal.

But let's not forget our purpose here. Our gruff needs a steer.

Indeed :)

So what are nets and filters? You've got me interested.

Guitarist, I can sort of see the connection with what you mentioned with topology (somthing I know a little about because of my work, but not the maths of it).

--
PS
I've just been going over some basics of ZF, it's looks bloody great! I am very excitied and I think I have something that I can now sink my teeth into and move forward with.

I'm plotting a large mind map of the basics of ZF now...

Can you reccomend a few books, all I have at the moment is Wikipedia! There's one book on naive Set Theory on Amazon, but I'd like some other options.

Hang on, does ZF say that every set contains the empty set? The axiom of the Power Set seems to say it does. But then doesn't that mean that the empty set has to contain itself and so not be empty?

Straighten me out here please!

(Edit: I just noticed too that every set is connected to every other set via the empty set. No set can be completely unique in its membership because it has to contain the empty set. I like that)

Yes the empty set is contained in the empty set (as it is contained in ever set) but that does not imply that the empty set contains an element. Look at what containment means in predicate logic and you should see that no existence claim is made.

How much topology do you know?

Originally Posted by river_rat

Yes the empty set is contained in the empty set (as it is contained in ever set) but that does not imply that the empty set contains an element. Look at what containment means in predicate logic and you should see that no existence claim is made.

How much topology do you know?

Ah this premepts my next question, which was how elements are more precisely defined. I'm not clear on whether there's meant to be a level of abstraction inherent in set theory (I'll be dissapointed if there is!) or whether set theory is attempting to not have any assumed abstractions?

I was wondering (especially since every entity is a set) whether a set (or sub-set especially) is an 'enclosed' entity as it were or simply a way to talk about what elements are common (or unique) between sets - ie an informal grouping or relationship?

Maybe I was assuming a level of abstraction that isn't there. I've probalby been taking the idea of a set too literally and rigidly, like it has boundaries like a container. That sounds niaive, but I'm a very visual thinker and can't help imagining containers flying round the place while I'm learning this :)

From what you say above, the empty set, while containing itself, and since it has no members, still has no members... ugh, i wish I could have put that better. Hmm, I'm still a bit unhappy with that definition since it implies that the empty set is iself not really an element in any set in the same way that a non-empty set is. Ugh, I don't like that, its sounds a bit ad hoc. tell me it isn't so...

-----
As for topology, I know next to nothing formally, but I know a bit because of my job (3D graphics), problalby more than I think I do though.

(Edit: eg how many holes a surface has is one of the major distinctions between different topologies, is that right?)

Originally Posted by gruff

Ah this premepts my next question, which was how elements are more precisely defined.

Umm. The elements of a set are precisely defined as being elements of of the set! Bear in mind that a set can be intuitively obvious (all dogs) or not (all things in my garage). The point about formal set theory is that emphasis is shifted away from point elements to the set as a whole: one writes f: X → Y, it being implicit that for some x in X there is f(x) = y in Y (one sometimes writes x|→ y for this. Notice the different style of arrow here).

In fact, set theory makes no real disinction between sets and elements. We may have x in X, X in Y where x is an element in X and X is an element in Y. This becomes important in topology.

EDIT: One says that a set is well-defined if any object in the universe is either defintely in the set or definitely not in it.

I was wondering (especially since every entity is a set) ?

What do you mean "every entity is a set? You must mean something other than it seems.

like it has boundaries like a container.

Ah, this is a whole can of worms, again intimately related to topology. You may, for now if you like, think of a set with a boundary as being closed, a set without a boundary as being open. There is an awful lot more to it than that, which you do need to understand, but there are a couple of fun theorems to prove here which might cheer you up!

Hmm, I'm still a bit unhappy with that definition since it implies that the empty set is iself not really an element in any set in the same way that a non-empty set is.

Yes, I had trouble with this at first. But look at the definition of a subset: X subset Y iff each element in X is also in Y. As I point out above, we can think of X as being contained in Y. And if X = Ø, then all elements in X (i.e. none) are contained in Y, trivially. (by the way, in Windows XP I get Ø by holding down alt while typing 0472 on the locked number pad, many other similar tricks too)

-----

As for topology, I know next to nothing formally, but I know a bit because of my job (3D graphics), problalby more than I think I do though.

For point set topology you need to be very familiar with set theory. It's a nice subject, though. Algebraic topology is something else again.

Umm. The elements of a set are precisely defined as being elements of of the set!

OK I've fallen foul of semantics. I don't have the understanding to be able to explain what I actually meant.

This will sound really stupid but - If say A is a member of B, and f(x) defines members of A, do we think of those members (when defining A as a subset) being 'loose' in B or still contained within the set A. It sounds really stupid but I can't help having this sensation of containers within containers. Is it simply a conveinience or shorthand for expressing the relationships between sets? I bloody hope so!

Hang on, perhaps this is better:

A={1,2,3}
B= {{A}, {C}}
C= {a,b,c}

Is there any way (and I mean in any possible implication whatsoever) that B={{A}, {C}} is *not* precisely the same things as B={1,2,3,a,b,c}?

What do you mean "every entity is a set? You must mean something other than it seems.

I meant every element is a set.

"like it has boundaries like a container."
Ah, this is a whole can of worms, again intimately related to topology. You may, for now if you like, think of a set with a boundary as being closed, a set without a boundary as being open. There is an awful lot more to it than that, which you do need to understand, but there are a couple of fun theorems to prove here which might cheer you up!

If I read some more I'll problably tie up the loose ends and it'll become obvious. At least there are fewer loose ends than with numbers.

"Hmm, I'm still a bit unhappy with that definition since it implies that the empty set is iself not really an element in any set in the same way that a non-empty set is."

Yes, I had trouble with this at first. But look at the definition of a subset: X subset Y iff each element in X is also in Y. As I point out above, we can think of X as being contained in Y. And if X = Ø, then all elements in X (i.e. none) are contained in Y, trivially.

Still having problems! I guess it comes down to the precise definition of existence and non-existance. On one hand the empty set is defined as a set, which has to have members for it to be defined as such. But its kind of saying that the empty set has the member 'no elements'. Ah hang on, perhaps it means that the empty set is only a set when it is a subset of another set and has no meaning on its own as it were.

I think I'll leave the precise meaning of the empty set and just move forward. I don't like accepting things without undertanding them, but I don't think its going to drastically affect my understanding of the rest of it if I leave this hole unplugged for the minute.

(by the way, in Windows XP I get Ø by holding down alt while typing 0472 on the locked number pad, many other similar tricks too)

I'm on OS X, is that unicode? Is there a tag for that in html?

-----

For point set topology you need to be very familiar with set theory. It's a nice subject, though. Algebraic topology is something else again.

I think topology can wait for bit yet :)

Originally Posted by gruff

If say A is a member of B, and f(x) defines members of A, do we think of those members (when defining A as a subset) being 'loose' in B or still contained within the set A.

Well first, why call elements of A as f(x)? This implies the existence of some function f, from where to
where? Why not just use x? Anyway yes, if A subset B then x in A is in A in B. Draw pictures, I do!

A={1,2,3}
B= {{A}, {C}}
C= {a,b,c}
Is there any way (and I mean in any possible implication whatsoever) that B={{A}, {C}} is *not* precisely the same things as B={1,2,3,a,b,c}?

Nope, none whatever. Note from what we were discussing recently, you can also write B = {1,a, c, 3, b, 2}. But let's straighten your notation a bit. From what you wrote B = A U C (B is the union of A and C).

But what if A = {a, b, c} and C = {c, d, e}? A U C = {a, b, c, d, e}, Note that c only appears once, this is part of the definition of a set.

I meant every element is a set.

No it's not. A set is a collection of elements. Tis tue, these elements may themselves be sets, but need not be. In any case, even if X is a set of sets, these latter will have point elements as set members. R is the set of real numbers. Is 1 a set?

I think I'll leave the precise meaning of the empty set and just move forward.

I strongly advise against it. Think of your containers, if you like. Ø is an empty container. It becomes important when doing set operations like intersection: A ∩ B = Ø means A and B have no elements in common. A U Ø = A and so on.

I'm on OS X, is that unicode? Is there a tag for that in html?

Is that MacIntosh? I think your option key might be worth eploring. I can't get html tags, other than sup and sub to work on this forum
-----

Originally Posted by gruff

Hang on, perhaps this is better:

A={1,2,3}
B= {{A}, {C}}
C= {a,b,c}

Is there any way (and I mean in any possible implication whatsoever) that B={{A}, {C}} is *not* precisely the same things as B={1,2,3,a,b,c}?

How is B = {1,2,3,a,b,c}?

It has two members, the set U = {A} which has only one element (namely the set A) and the set V = {B} which has only one element (namely the set B).

So B = {U, V} which is not the same thing as {1, 2, 3, a, b, c}

Originally Posted by guitarist

No it's not. A set is a collection of elements. Tis tue, these elements may themselves be sets, but need not be. In any case, even if X is a set of sets, these latter will have point elements as set members. R is the set of real numbers. Is 1 a set?

Well 1 = {Ø, {Ø}} so i guess it is a set

Originally Posted by river_rat

How is B = {1,2,3,a,b,c}?

It has two members, the set U = {A} which has only one element (namely the set A) and the set V = {B} which has only one element (namely the set B).

So B = {U, V} which is not the same thing as {1, 2, 3, a, b, c}

Ha! Behave yourself bad boy, I was trying to take it slowly. Sure his notation needs straightening out, that will come.

Well 1 = {Ø, {Ø}} so i guess it is a set ;)

Remember: Cantor went off his head. Seriously, let's be gentle with gruff here.

I strongly advise against it. Think of your containers, if you like. Ø is an empty container. It becomes important when doing set operations like intersection: A ? B = Ø means A and B have no elements in common. A U Ø = A and so on.

Is this just a difference in semantics? I take A disjoint B = Ø to mean 'A and B have only the empty set in common' which is different to 'A and B have no elements in common'. Again to my mind it comes down to what the empty set is, and whether all elements are sets (I did read that this was the case, but from what you're saying that's incorrect?).

I can see that if Ø is the set that has no elements and that A disjoint B = Ø that A and B have no elements in common, since by definition Ø has no elements.

But, if you say that a set is only a set if it contains elements then in what way is Ø a set? I'm only asking because I can't find a fuller definition.

I obviously don't understand the meaning of a set.

River_Rat, that's really great thanks...

Originally Posted by gruff

Is this just a difference in semantics? I take A disjoint B = Ø to mean 'A and B have only the empty set in common' which is different to 'A and B have no elements in common'.

OK, it's time to grow up a bit here, and learn proper terminology (else the South African rat will bite). "A disjoint B = Ø" is meaningless. You should say "A disjoint B iff A ∩ B = Ø". Why are you having such a problem with empty set: it's the nearest thing that set theory gets to zero.

OK, here's an execise for you. Take your "containers" labelled A and B, tip out all the contents of each, and tell me what you have left. Think carefully, the answer may not be the one you first think of!

and whether all elements are sets

Yeah, there is a way of thinking like that, as ratty indicated. I suggest you don't worry about that too much for now, just get your head round the basics.

But, if you say that a set is only a set if it contains elements then in what way is Ø a set?

Did I say that? If I did, I was wrong. Empty set is a valuable tool, it allows us to make sense of set operations.

Look.

Let A and B be sets, and let Ø be empty set. A ∩ Ø = Ø, A U Ø = A, A - Ø = A and so on, just like you need an identity to make sense of algebraic operations.

When you are comfortable with the idea of empty set, you might want to talk about open and closed sets

OK, it's time to grow up a bit here, and learn proper terminology (else the South African rat will bite). "A disjoint B = Ø" is meaningless. You should say "A disjoint B iff A ? B = Ø". Why are you having such a problem with empty set: it's the nearest thing that set theory gets to zero.

look between the chapter in this maths book, you guys and wikipedia thats all I have to go on! The ? symbol turned into a question mark when I replied that last time (though I was able to copy and paste it before, I don't know why it stopped) so I had to check on wiki for the english word - it's intersection, not disjoint I made a mistake. Sorry.

I meant A intersect B = Ø (Shift-option O on the Mac for Ø BTW)

You have to understand I am simply trying to comminicate using an unfamiliar language - would you tell a native Chinese speaker to grow up because they used incorrect English grammar?

I realise it's hard when discussing things that require such pedantic language but please, I take exception to beling told to grow up. Mistakes are easy to make in unfamiliar territory.

If its not possible to explain without my having a better grasp of the language of sets, then that's fair enough I'll study for a few months and see where that gets me.

Originally Posted by gruff

I take exception to beling told to grow up.

Oh dear, please don't be offended. I merely meant it's time to use the terminology that the experts (i.e. the grown-ups) use.

So, although I feel I know what you are trying to say, I wanted to get you frame it in a conventional way. Again, sorry for any offence.

Originally Posted by Guitarist

Originally Posted by gruff

I take exception to beling told to grow up.

Oh dear, please don't be offended. I merely meant it's time to use the terminology that the experts (i.e. the grown-ups) use.

So, although I feel I know what you are trying to say, I wanted to get you frame it in a conventional way. Again, sorry for any offence.

Sorry Guitarist - perhaps I shouldn't be so touchy. I'm a little stressed out!

I don't think I will be able to frame my questions better until I learn ZF some more. As I said I will have to accpet my poor understanding of Ø until I learn more.

OK, good. Now do me the exercise I set you. Remember that attempting exercises is a crucial part of learning math (note I said attempting, not getting right)

OK, here's an execise for you. Take your "containers" labelled A and B, tip out all the contents of each, and tell me what you have left. Think carefully, the answer may not be the one you first think of!

Do you mean this exersise?

If so, the answer is I have two empty containters.

Originally Posted by gruff

If so, the answer is I have two empty containters.

Hmm. Now think what it means for two sets to be equal.

Your answer is wrong, by the way, I did warn you.

Originally Posted by Guitarist

Originally Posted by gruff

If so, the answer is I have two empty containters.

Hmm. Now think what it means for two sets to be equal.

I don't know. Is it something to do with extensionality? My head is too fried to becable to contruct a meaningful explanation.

Your answer is wrong, by the way, I did warn you.

Well no, my answer to your question is correct. You didn't ask the right question. This is less trivial that it sounds and is an important point to understand when attempting to teach someone something.

I don't beleive a set is the same as a container in the real world - this is precesely my problem, if they were my literal answer to your question would be correct for set theory.

[/quote]

Originally Posted by gruff

Well no, my answer to your question is correct. You didn't ask the right question.

Maybe you're right about that. What I wanted you to see is:

a) containers are not a good way of thinking about sets, as you say;

b) 2 sets A and B are the same if every element in A is in B and every element in B is in A. If A and B are both empty, they are the same, therefore there is only one empty set;

c) there are no special rules for the empty set, the same apply whether whether empty or not.

OK, I'm going to say a bit about open and closed sets. Remember the interval (a, b) on the real line? This interval contains all points between a and b but not a and b. It is called an open interval. It is also a perfectly good open set. Conversely the interval [a, b] does contain a and b, it is a closed interval/set.

You can think of a and b as the boundary points of these intervals, which leads to the conclusion that a closed set contains its boundary, an open set does not.

Here's neat trick. Consider some set A completely embedded in a set B, A subset B. Those elements of B not in A are referred to as the complement of A and written Ac (actually the c should be superscripted, but I can't be arsed).

Now there is a boundary where A "ends" and Ac "begins", but only one. Then the boundary must either belong to A or to Ac, so if A is open, Ac is closed and v. v. (I'm being a bit loose with terminology here, but that needn't worry you for now. Edit: maybe I should say it after all. I really mean"if A is open, Ac is not open", which is not quite the same as closed).

So, the boundary of A can be called bdA. Some more definitions, so take it slow;

the interior of a set A is defined as the largest open set wholly contained in A; if A is open intA = A.

The closure of A, clA, is the smallest closed set wholly containing A. If A is closed clA = A. We can now give a more precise definition of the boundary.

bdA = clA - intA. There is an alternative but equivalenet definition of bdA which we can see later, if you want. Meanwhile, any questions?

Originally Posted by Guitarist

Originally Posted by gruff

Well no, my answer to your question is correct. You didn't ask the right question.

Maybe you're right about that. What I wanted you to see is:

a) containers are not a good way of thinking about sets, as you say;

b) 2 sets A and B are the same if every element in A is in B and every element in B is in A. If A and B are both empty, they are the same, therefore there is only one empty set;

c) there are no special rules for the empty set, the same apply whether whether empty or not.

OK, I'm going to say a bit about open and closed sets. Remember the interval (a, b) on the real line? This interval contains all points between a and b but not a and b. It is called an open interval. It is also a perfectly good open set. Conversely the interval [a, b] does contain a and b, it is a closed interval/set.

You can think of a and b as the boundary points of these intervals, which leads to the conclusion that a closed set contains its boundary, an open set does not.

Here's neat trick. Consider some set A completely embedded in a set B, A subset B. Those elements of B not in A are referred to as the complement of A and written Ac (actually the c should be superscripted, but I can't be arsed).

Now there is a boundary where A "ends" and Ac "begins", but only one. Then the boundary must either belong to A or to Ac, so if A is open, Ac is closed and v. v. (I'm being a bit loose with terminology here, but that needn't worry you for now).

So, the boundary of A can be called bdA. Some more definitions, so take it slow;

the interior of a set A is defined as the largest open set wholly contained in A; if A is open intA = A.

The closure of A, clA, is the smallest closed set wholly containing A. If A is closed clA = A. We can now give a more precise definition of the boundary.

bdA = clA - intA. There is an alternative but equivalenet definition of bdA which we can see later, if you want. Meanwhile, any questions?

That all makes PERFECT sense, thank you. So now I have a much simpler and self-consistent understanding of sets in terms of boundaries (well, I won't pretend I fully understand but I have a new tool in my tool box as it were, and I can forget about containers!).

(You see this is the problem I have learning by someone elses determination of what or what is not necessary for understanding. I need to see the big picture. If I feel something is not 'right' or self consistent, i know I have a hole in my understanding. If you leave out something important and try to reduce the explanation then you inevitably end up making things harder to understand, not easier.)

So... is the empty set open or closed, and if closed how are its boundaries defined?

Also there must be a set of all sets, which is closed right?

Originally Posted by gruff

So... is the empty set open or closed, and if closed how are its
boundaries defined?

A closed set contains it's boundary points. As Ø has no points, therefore no boundary points it is open. But as there are no elements in Ø, the non-existent boundary points fit very nicely in the empty set so it is closed.

This relates to my comment about loose language - sets can be open, closed, neither or both, so if a set is not open, we may not assume it is closed. The empty set is both open and closed!

By the way, I owe you an apology. river_rat was quite right, it is perfectly proper in axiomatic set theory to think of elements of a set as sets themselves. I guess I was being patronizing.

OK, it will be a good exercise to see if you can follow this, but don't panic if you can't, it's just a bit of fun.

We defined bdA = clA - intA

Set clAc ∩ bdA = clAc ∩ (clA - intA)

clAc ∩ bdA = clAc ∩ clA - clAc ∩ intA

Supose Ac closed, A open. Then clAc = Ac and intA = A.

By definition Ac ∩ A = Ø, so clAc ∩ intA = Ø and I have

clAc ∩ bdA = clAc ∩ clA. As Ac is closed, bdA subset clAc and therefore

clAc ∩ bdA = bdA and I arrive at

bdA = clAc ∩ clA as an alternative definition of the boundary of A

A closed set contains it's boundary points. As Ø has no points, therefore no boundary points it is open. But as there are no elements in Ø, the non-existent boundary points fit very nicely in the empty set so it is closed.

This relates to my comment about loose language - sets can be open, closed, neither or both, so if a set is not open, we may not assume it is closed. The empty set is both open and closed!

By the way, I owe you an apology. river_rat was quite right, it is perfectly proper in axiomatic set theory to think of elements of a set as sets themselves. I guess I was being patronizing.

OK, it will be a good exercise to see if you can follow this, but don't panic if you can't, it's just a bit of fun.

I can follow parts but to be honest I have difficulty remembering what the terms stand for and will need to spend a bit of time writing it out so I remember them.

I'm going to read some more armed with the new info you've given me.

I am more confortable with my fuller undertanding of the empty set, but though I accept sets can be closed, open and neither I'm not sure about being both open and closed, unless that only applies to the empty set?

OK, I'll have to ask.. can you give me some examples of closed and empty sets (if there are more than Ø).

PS what was RR saying about 1= {Ø,{Ø}}? That looks interesting... is that the definition of unity? And what about cardinal numbers... OK too may questions.

Originally Posted by gruff

OK, I'll have to ask.. can you give me some examples of closed and empty sets (if there are more than Ø).

Remember the open set on the real line (a,b) and the closed set [a,b]? The set [a,b) is both open and closed.

I've tried to think of an everyday example of sets which are neither open nor closed, but failed. Maybe it will come to me.

PS what was RR saying about 1= {Ø,{Ø}}?

Ask him, It's a level of abstraction you don't need just yet.

Remember the open set on the real line (a,b) and the closed set [a,b]? The set [a,b) is both open and closed.

I've tried to think of an everyday example of sets which are neither open nor closed, but failed. Maybe it will come to me.

The set [a, b) is open and closed? To be correct it is in fact neither, well at least if we are talking point-set topology and it looks like we are. An open set contains a neighbourhood of each of its points, obviously neither [a, b) nor its complement are open if you look at it that way.

The only clopen (i.e. open and closed) sets of the real line happens to be the empty set and the real line itself. That is because the real line is connected.

PS what was RR saying about 1= {Ø,{Ø}}? Ask him, It's a level of abstraction you don't need just yet.

It has to do with one of the ways the natural numbers are defined, don't worry about it yet.

Just a question gruff, are you interested in set theory or point-set topology as the idea of open and closed sets, boundaries and interiors are topological in nature and depend on the topology on the set in question.

Originally Posted by river_rat

at least if we are talking point-set topology and it looks like we are.

Drat! Found out! It's true I was borrowing heavily from topology to get across the flavour of sets, without ever going into what topology actually is. I hope I haven't thereby muddied the waters.

The only clopen

I feel sick!

(i.e. open and closed) sets of the real line happens to be the empty set and the real line itself. That is because the real line is connected.

Hmm, what you say is not true for all topologies on R, as you well know: in the discrete topology and the Sorgenfrey line, for example, all sets are both open and closed. In the latter, of course, sets are of the form [a. b). Anyway, let's not go too deeply into that just now.

the idea of open and closed sets, boundaries and interiors are topological in nature and depend on the topology on the set in question.

You may recall a much earlier post of mine where I hinted as much. Neverthelss, it seems reasonable to assume, when talking to a relative neophyte about the real line that they will have the standard topology in mind, even if they don't realize it! If I'm right about that, it seems appropriate to talk about open and closed sets, closures, interiors and boundaries.

I take it you disapprove of my approach?

The set [a, b) is open and closed? To be correct it is in fact neither, well at least if we are talking point-set topology and it looks like we are. An open set contains a neighbourhood of each of its points, obviously neither [a, b) nor its complement are open if you look at it that way.

[a,b) being open and closed didn't seem right to me either. Unless guitarist, you mean closed on one side, open on the other?

The only clopen (i.e. open and closed) sets of the real line happens to be the empty set and the real line itself. That is because the real line is connected.

Great, that was my question earlier. I get that Ø can be clopen, but not quite sure about the real line though. Wouldn't infinte sets be open by definition?(ie if you could define boundary points it wouldn't be infinite).

Ah hang on, I think I get it. It is both. If open then it would imply boundary points that are still greater. Likewise if closed, then the set is finite. Or would that imply neither?

(note, I edited this line as I got the words reversed:) From that then, given any open set does it imply there is another set that is closed but containing the open set?

What I'm getting at is the question of whether closed sets are in a way more fundamental than open sets, any open set being the interior closed set? Is there an ultimate closed set then - the set of all sets?

It has to do with one of the ways the natural numbers are defined, don't worry about it yet.

I AM worrying because this the whole reason I've come to set theory in the first place. If 1= {Ø,{Ø}} is right I will be very happy indeed. It looks utterly fundamental to me so I NEED this clarified....

Just a question gruff, are you interested in set theory or point-set topology as the idea of open and closed sets, boundaries and interiors are topological in nature and depend on the topology on the set in question.

If point-set topology is related and describes surfaces then yes I'm interested, though at the moment I'm still on the quest of nailing down the integers (as well as more fundamental questions).

Originally Posted by gruff

[a,b) being open and closed didn't seem right to me either. Unless guitarist, you mean closed on one side, open on the other?

As an interval it is both open and closed, for the reasons you gave. But there's a subtlety here. In what is called the standard topology on R, open intervals of the form (a, b) are open sets, any other sort of interval is not an open set, so I was wrong for this topology, sorry for any confusion. As I said ages ago, and river_rat also said, really speaking the issue of whether a set is open, closed, neither or both has to do with topology. Should I start a new thread, maybe?

If a deeper explanation requires topology, (and avoids confusion) then yes please...

Originally Posted by Guitarist

Drat! Found out! It's true I was borrowing heavily from topology to get across the flavour of sets, without ever going into what topology actually is. I hope I haven't thereby muddied the waters.

Not muddied the waters per se, but i dont think we are answering Gruffs original question about the nature of sets. The problem is that this question falls more in the realm of philosophy then mathematics, as sets (or more correctly classes) are treated as just understood and thus undefined.

Lol, what do you have against clopen sets? I kind of like zero-dimensional spaces

Hmm, what you say is not true for all topologies on R, as you well know: in the discrete topology and the Sorgenfrey line, for example, all sets are both open and closed. In the latter, of course, sets are of the form [a. b). Anyway, let's not go too deeply into that just now.

I was assuming we were talking about the natural topology on R. Anyway not all sets are clopen in the case of the Sorgenfrey line but it is zero dimensional (+ T0 => totally disconnected)

You may recall a much earlier post of mine where I hinted as much. Neverthelss, it seems reasonable to assume, when talking to a relative neophyte about the real line that they will have the standard topology in mind, even if they don't realize it! If I'm right about that, it seems appropriate to talk about open and closed sets, closures, interiors and boundaries.

I take it you disapprove of my approach?

Dont disapprove, i just dont think we have got to gruff's original question

Originally Posted by Gruff

I was wondering (especially since every entity is a set) whether a set (or sub-set especially) is an 'enclosed' entity as it were or simply a way to talk about what elements are common (or unique) between sets - ie an informal grouping or relationship?

Maybe I was assuming a level of abstraction that isn't there. I've probalby been taking the idea of a set too literally and rigidly, like it has boundaries like a container. That sounds niaive, but I'm a very visual thinker and can't help imagining containers flying round the place while I'm learning this

Originally Posted by river_rat

Lol, what do you have against clopen sets? I kind of like zero-dimensional spaces

Ha, nothing, it's the c-word I hate

I was assuming we were talking about the natural topology on R. Anyway not all sets are clopen in the case of the Sorgenfrey line but it is zero dimensional (+ T0 => totally disconnected)

Well, you may be right, but that's not my memory of the lower limit top. I'm pretty sure all sets here are both open and closed. It doesn't matter (in this thread, at least - I do have another more revelant one). Anyway, I had always thought of topologies other than T2, T3,... as somewhat pathological, I don't have a good reason though (maybe if I were a physicist I could hand-wave a bit about it)

Nope, if all sets are open (or closed or both - doesn't really matter) then you have the discrete topology, which the lower limit topology clearly is not. Its easy to check, for example any singleton is closed (so the space is T1) but no singleton is open.

Most spaces analysts work on are at least T2 as you like sequences to have unique limits but some inportant topologies are only T1 for example the Zariski topology is only T1.

river_rat.
I don't want to sound testy, because you are fun to talk to.

But, I think we have a communication problem here. if I talk about sets in the lower limit topology, I am referring to elements of T only, which are of the form [a, b), right? And if, for any such set I can find a set in the complement of T, like [b, c), for example, I am entitled to say say that all sets in the topology are both open and closed. Evidently {b} is also in the complement of [a,b), and is thereby closed. So what? "All open sets are also closed" does not imply "all closed sets are also open".

I never said, and I don't think I implied, that any subset whatever of the underlying set was both. Or do you personally not draw a distinction between subsets of the underlying set and those of its toplolgy? I'd be astonished if you didn't.
-b-

That is not true either guitarist - in the lower limit topology, X \ {x} is an open set for all x in X (so is in T for any x in X) but not one of those sets are closed (as {x} is not open).

The sets of T are the arbit. unions of sets of the form [a, b) - as {[a, b) : a, b in X} is a base for the lower limit topology.

All open sets are closed does imply all closed sets are open btw.