Question about proof from a guy with a highschool education

[Fredrik]

Why is it wrong? If from the universal set you take out AuBuC , then what you have left is everything that wasn't A , B or C , therefore the union of A' , B' and C'.

These rules are called de Morgan's laws: $(A\cap B)'=A'\cup B'$ and $(A\cup B)'=A'\cap B'$. Your result should be similar to that.

The union between multiple sets has to be guaranteed for these multiple sets to become a subset?

I don't understand the question.

 

[reenmachine]

1)These rules are called de Morgan's laws: $(A\cap B)'=A'\cup B'$ and $(A\cup B)'=A'\cap B'$. Your result should be similar to that. 2)I don't understand the question.

1) I don't understand the logic.

(A∩B)' should be everything within the universe of discourse (U) except the intersection of A and B (or anything within that intersection).

A'∪B' should be everything within the universe of discourse (U) that isn't A or B (or within A or B).

If both statements are correct , what about the part of A and the part of B that aren't intersecting with the other set (A or B) but that aren't in A' or B' (because a part of A or B)?

2) Basically , if you have two sets or two subsets , you have to ''unionize'' them in order to transform them into a subset if I want to write that A and B are a subset of N' (with N being a set that has no intersection with neither A or B).So I can't write (A,B) ⊆ N' but have to write A∪B ⊆ N'.Is that correct?

 

[Curious3141]

1) I don't understand the logic.

(A∩B)' should be everything within the universe of discourse (U) except the intersection of A and B (or anything within that intersection).

A'∪B' should be everything within the universe of discourse (U) that isn't A or B (or within A or B).

If both statements are correct , what about the part of A and the part of B that aren't intersecting with the other set (A or B) but that aren't in A' or B' (because a part of A or B)?

Draw a Venn diagram. A' includes the area of B that doesn't lie in A (i.e. excluding the intersection of A and B). Similarly, B' includes the area of A that doesn't lie in B. Both A' and B' include the area in U that's outside both A and B. The union operation includes all these areas (without double-counting the common ones).

 

[reenmachine]

Draw a Venn diagram. A' includes the area of B that doesn't lie in A (i.e. excluding the intersection of A and B). Similarly, B' includes the area of A that doesn't lie in B. Both A' and B' include the area in U that's outside both A and B. The union operation includes all these areas (without double-counting the common ones).

I currently have no idea what that is , but even without it I understand your point and am embarrassed that I didn't see it right away :X

I'll look for infos on Venn Diagrams tomorrow.

Thanks

 

[Curious3141]

I currently have no idea what that is , but even without it I understand your point and am embarrassed that I didn't see it right away :X

I'll look for infos on Venn Diagrams tomorrow.

Thanks

http://en.wikipedia.org/wiki/Venn_diagram

No need to feel "embarrassed" - we're all here to learn.

 

[reenmachine]

http://en.wikipedia.org/wiki/Venn_diagram

No need to feel "embarrassed" - we're all here to learn.

LOL I already made a similar diagram in this thread earlier.Just didn't know it was a ''Venn Diagram''.

I often feel embarrassed when I don't ''get'' something as quick as I would like , but these feelings are normally short-lived and my thirst to learn/know comes back to replace them pretty quickly. :)

cheers

 

[Fredrik]

A Venn diagram (yes, you already drew one) should be enough to convince you that $(A\cup B)'=A'\cap B'$. The proper way to prove this identity is based on the axiom that says that two sets X and Y are equal, if every member of X is a member of Y, and every member of Y is a member of X. The proof goes like this:

Let $x\in (A\cup B)'$ be arbitrary. Since $x\in(A\cup B)'$, we have $x\notin A\cup B$. This implies that $x\notin A$ and $x\notin B$ (because if these two statements aren't both true, x would be a member of $A\cup B$). This implies that $x\in A'$ and $x\in B'$. This implies that $x\in A'\cap B'$.

Now let $x\in A'\cap B'$ be arbitrary. Since $x\in A'\cap B'$, we have $x\in A'$ and $x\in B'$. This implies that $x\notin A$ and $x\notin B$. This implies that $x\notin A\cup B$ (because if x had been a member of $A\cup B$, then it would be a member of A or B). This implies that $x\in (A\cup B)'$.

 

[reenmachine]

A Venn diagram (yes, you already drew one) should be enough to convince you that $(A\cup B)'=A'\cap B'$. The proper way to prove this identity is based on the axiom that says that two sets X and Y are equal, if every member of X is a member of Y, and every member of Y is a member of X. The proof goes like this:

Let $x\in (A\cup B)'$ be arbitrary. Since $x\in(A\cup B)'$, we have $x\notin A\cup B$. This implies that $x\notin A$ and $x\notin B$ (because if these two statements aren't both true, x would be a member of $A\cup B$). This implies that $x\in A'$ and $x\in B'$. This implies that $x\in A'\cap B'$.

Now let $x\in A'\cap B'$ be arbitrary. Since $x\in A'\cap B'$, we have $x\in A'$ and $x\in B'$. This implies that $x\notin A$ and $x\notin B$. This implies that $x\notin A\cup B$ (because if x had been a member of $A\cup B$, then it would be a member of A or B). This implies that $x\in (A\cup B)'$.

Very clear thank you again!

Where does this axiom comes from per say though (I understand the logic behind it , but not from which list of multiple axioms does it came from)? Is it an official accepted and necessary axioms in all of set theory?

 

[Fredrik]

Very clear thank you again!

Where does this axiom comes from per say though (I understand the logic behind it , but not from which list of multiple axioms does it came from)? Is it an official accepted and necessary axioms in all of set theory?

There are several different set theories, each defined by a set of axioms about sets, and a set of axioms about how we can obtain new theorems from the ones we already have. The latter is referred to as a "proof theory". I am very far from an expert in these matters, but I think I understand some of the basic ideas at least. There seems to be a lot of flexibility in how exactly the proof theory is defined. Given a set of axioms about sets, there are lots of different sets of axioms about how to prove theorems that are equivalent in the sense that they will agree about what statements will be considered theorems. Because of this, the proof theory is rarely even mentioned, and you can pretty much think of the set theory as being defined by the axioms about sets.

There's one specific set of axioms called ZFC (Zermelo, Fraenkel, and the axiom of Choice) that's powerful enough to include all the mathematics that you are likely to ever find interesting. This includes all the mathematics of physics, and a lot more. The specific axiom I was referring to is called the axiom of extensionality. It's #1 on the Wikipedia page I linked to.

If you find this stuff interesting, there are several good books about set theory. Hrbacek and Jech is a good choice. Goldrei may be even easier, at least when it comes to the construction of the number systems, but it doesn't go as deep into the theory. However, you don't need to study axiomatic set theory right now. What you need is to understand when sets are equal, and a little about how to get new sets from the ones we already have, e.g. by taking unions, complements, etc. People refer to this approach as "naive set theory".

 

[Curious3141]

However, you don't need to study axiomatic set theory right now. What you need is to understand when sets are equal, and a little about how to get new sets from the ones we already have, e.g. by taking unions, complements, etc. People refer to this approach as "naive set theory".

Just to add to Fredrik's excellent post, it might be interesting to you (reenmachine) that set theory as usually introduced at the school level is "naive set theory". It introduces students to the concept intuitively, e.g. "let C be the set of cats", without bothering with axioms or rigor in general. The reason this is called "naive" is because it's rather easy to trip it up by creating logical paradoxes, e.g. Russell's Paradox. That's why naive set theory had to be abandoned in favour of a more sound theory, e.g. ZFC which had rather stricter rules about how sets can be defined and manipulated.

 

[reenmachine]

Thanks to both of you!

This thread took me to some interesting and unknown places.This is how I love to learn.I understand the need to understand naive set theory before going deeper but I still like to see a little bit of what's ahead of me to motivate me to learn the basics in order to ''get there''.I will try to buy those book suggestions you gave me.

I will surely have more questions about these things , but first I'll try to finish the set theory basics read I pmed you (Fredrik).

cheers!

 

[WannabeNewton]

The cool thing is that with some mathematical maturity and a handle on proofs you could easily just start studying set theory since it has no other pre-requisites. Set theory is easily, in my opinion, the most beautiful of the mathematical branches. It is full of insanely elegant proofs (Cantor being the pervasive one in that department) and counter intuitive concepts (ordinals for example). The bible of all set theory books would have to be the one by Jech; it is very comprehensive but probably more than what you are looking for since it goes straight into ZFC. Good luck!

 

[reenmachine]

The cool thing is that with some mathematical maturity and a handle on proofs you could easily just start studying set theory since it has no other pre-requisites. Set theory is easily, in my opinion, the most beautiful of the mathematical branches. It is full of insanely elegant proofs (Cantor being the pervasive one in that department) and counter intuitive concepts (ordinals for example). The bible of all set theory books would have to be the one by Jech; it is very comprehensive but probably more than what you are looking for since it goes straight into ZFC. Good luck!

Thank you!

I have to face reality , I'm not getting any younger (mathematically speaking at least).I have no choice but to study by myself before returning to school , and even when I'm going to go to school hopefully I will be capable of learning more than what the programs has to offer in my free times.

At 26 years old with no university education , I can't simply wait here and pretend I'll rock everything on my way just by returning to school and doing like 95% of mathematics students.I have to breathe math , and for the moment my lungs are loving it.

Set theory strangely ressembles what logicians would work on.

edit: btw , when you're saying no pre-requisites are required to do set theory , does it mean set theory is a bit of an outsider as far as mathematic branches? Meaning you don't have to study for years and years before being able to understand the basics like some other branches might require?

I really enjoy the pure logic aspect of what I'm seeing right now.Is set theory a popular branch at the moment?

 

[WannabeNewton]

Set theory strangely ressembles what logicians would work on.

Axiomatic set theory does have a good chunk of formal logic. Most mathematics sequences I've seen usually start with a formal logic course before following up with an axiomatic set theory course.

 

[WannabeNewton]

edit: btw , when you're saying no pre-requisites are required to do set theory , does it mean set theory is a bit of an outsider as far as mathematic branches? Meaning you don't have to study for years and years before being able to understand the basics like some other branches might require?

I really enjoy the pure logic aspect of what I'm seeing right now.Is set theory a popular branch at the moment?

Well by no pre-requisites (other than formal logic depending on how deep you want to go) I meant you don't for example need to have done analysis or algebra beforehand to learn set theory. Set theory is a bit removed from the other branches if you get really deep. I don't know what your definition of "basics" are but to learn anything properly requires a good amount of time. As far as "popularity" I don't know anything about that. Micromass could probably answer that.

 

[reenmachine]

I just realized micromass is an high school student , he must be a sick mathematical talent.Great for him! If he sees this post maybe he can give me his take on the branch of set theory as far as popularity goes.

As for how deep I want to go , I guess it depends on what branch of mathematic I will ultimately choose , but even with my age I still dream of going as deep as I can in pure math.

 

[WannabeNewton]

I just realized micromass is an high school student , he must be a sick mathematical talent.Great for him!

Yes he is quite the brilliant high schooler

 

[reenmachine]

Yes he is quite the brilliant high schooler

I don't understand , why didn't they push him toward university?The guy looks like he is almost ready or ready to do serious research , but maybe that's just my own ignorance of what level you have to reach to do research :X

In any case I'm impressed.

 

[WannabeNewton]

I don't understand , why didn't they push him toward university?

He probably just wanted to enjoy his high school years while it lasted.

 

[reenmachine]

There's one specific set of axioms called ZFC (Zermelo, Fraenkel, and the axiom of Choice) that's powerful enough to include all the mathematics that you are likely to ever find interesting. This includes all the mathematics of physics, and a lot more. The specific axiom I was referring to is called the axiom of extensionality. It's #1 on the Wikipedia page I linked to.

If you find this stuff interesting, there are several good books about set theory. Hrbacek and Jech is a good choice. Goldrei may be even easier, at least when it comes to the construction of the number systems, but it doesn't go as deep into the theory.

Can you please suggest me some specific titles from these authors you think I should buy right now?

Also , do you happen to know a good book on formal logic that I should buy to get started with the basic concepts of formal logic?

(those questions applies for everybody who have suggestions)

 

[Fredrik]

Can you please suggest me some specific titles from these authors you think I should buy right now?

Also , do you happen to know a good book on formal logic that I should buy to get started with the basic concepts of formal logic?

These are the books I had in mind:

books.google.com/books?id=1dLn0knvZSsC
books.google.com/books?id=Er1r0n7VoSEC

Not sure what to recommend for logic. When I took a look at the basics a couple of years ago, I read a little in each of these three books: Enderton, Rautenberg, Kunen

But honestly, I don't think you will need to study logic at that level. You should only study this type of books if you're really interested in it. It is however very useful to study a little bit of logic at the level discussed in that "book of proof" that another forum member recommended in the thread I showed you under "academic guidance". http://www.people.vcu.edu/~rhammack/BookOfProof/. What you need to understand is how to use truth tables to determine if two statements are equivalent or not. For example "if p, then q" is equivalent to "if not q, then not p", because the two statements have the same truth table.

 

[reenmachine]

These are the books I had in mind:

books.google.com/books?id=1dLn0knvZSsC
books.google.com/books?id=Er1r0n7VoSEC

Not sure what to recommend for logic. When I took a look at the basics a couple of years ago, I read a little in each of these three books: Enderton, Rautenberg, Kunen

Damn they are pricey.Do you think I could find these in a public library?

But honestly, I don't think you will need to study logic at that level. You should only study this type of books if you're really interested in it. It is however very useful to study a little bit of logic at the level discussed in that "book of proof" that another forum member recommended in the thread I showed you under "academic guidance". http://www.people.vcu.edu/~rhammack/BookOfProof/. What you need to understand is how to use truth tables to determine if two statements are equivalent or not. For example "if p, then q" is equivalent to "if not q, then not p", because the two statements have the same truth table.

Well I do have some interest in logic , that's why I would like to understand it a bit more.I will buy the bookofproof on the net.

 

[CompuChip]

When I just started university my "Proofs 101" course was taught from Foundations Of Higher Mathematics by C Wayne Patty. No idea what the price is but it was pretty OK with attention for many different subjects in mathematics like different ways of proving a statement but also things like functions and relations.

 

[reenmachine]

So just for a quick refresher:

(see diagram at end of the post)

Just to be clear , U = universe of discourse

U - (A'∪B') = A∩B (and not A∪B)
U - (Z'∪Y') = ∅
Y ⊆ B'
Y ∉ B'
A∪B ⊆ Z'

Just trying to get a clearer picture on the ''is a subset of'' or ''is an element of'' confusion:

Every set that is a collection of elements can't become an element of a bigger set?
If (2,3) = Y then Y can't be an element of U is that right? So as long as any set is the sum of two or more elements he can't be an element? But suppose you look at these circles diagram below , if the cut is infinitely smaller everytime you can always split every sets into subsets until infinity , so when do you draw the line between the space required (within the set) to split the elements that are part of the same set and the infinite number of subset you can produce within that set? Basically when is the ''pureness'' of elements proved if we can always split them one way or another?

 

[Fredrik]

U - (A'∪B') = A∩B (and not A∪B)
U - (Z'∪Y') = ∅
Y ⊆ B'
Y ∉ B'
A∪B ⊆ Z'

That's right.

But is Y ⊆ U or Y ∈ U ?

The diagram indicates that Y is a subset of U, nothing else. An element of U is represented by a point in the diagram.

Basically , can a set be an element of a much bigger set?

Yes. It doesn't have to be a much bigger set. The simplest example is {∅}, the set whose only member is the empty set. ∅ is a set, and it's a member of {∅}.

It's actually possible for $y\in x$ and $y\subseteq x$ to both be true. A fun example of that is the set theory definition of the integers. The integers can be defined abstractly as a "ring" that satisfies a number of axioms. The only problem with such a definition is that when we just write down a number of axioms, it's possible that we will have screwed up by including an axiom that contradicts the other ones.

It would be nice to have a way to prove that the axioms don't contradict each other. Unfortunately, every proof relies on some set of axioms, so if we find a way to "prove" that our axioms for the integers don't contradict each other, it will raise the question of whether the axioms we used for the proof contradict each other. So we have a problem that's similar to the problem with definitions that I mentioned earlier. We can't define every term and symbol, and we also can't prove that every list of axioms is consistent. It would however be pretty nice if ZFC is the only list of axioms whose consistency is left unproved.

So how do we prove that the axioms for the integers don't contradict each other? We do it by showing that the ZFC axioms ensure that there exists a ring with the desired properties. This includes a definition of the non-negative integers that makes each integer a set:

0=∅
1={0}
2={0,1}
3={0,1,2}
...

So every non-negative integer is the set whose members are all the smaller integers. Note that

3={0,1,2}={0,1,{0,1}}

So 2={0,1} is both a member and a subset of 3.

It goes without saying that the full construction of the integers involves a lot more than this. I know that Goldrei covers this pretty well.

 

[reenmachine]

Very clear thank you!

 

[Fredrik]

I just realized micromass is an high school student ,

He's not a high shool student. At least I really really hope he isn't, LOL. I think my head would literally explode if I found out that he is. (It's hard enough to deal with the fact that WannabeNewton was in high school a year ago, and is making solid posts on topics like point-set topology and general relativity). Someone said something about micromass being a graduate student a couple of years ago, and I just assumed that was true. I also remember him saying something about teaching a course in functional analysis (a year ago?). So I think that if he doesn't have a Ph.D. in math already, he will soon. He's without a doubt the best math poster here.

 

[micromass]

My secret is out

It's true. I'm not a high school student, but rather a grad student in mathematics. Years ago, I've edited to my profile to say "high school student" as a joke. Somehow, I never changed it back

 

[reenmachine]

My secret is out

It's true. I'm not a high school student, but rather a grad student in mathematics. Years ago, I've edited to my profile to say "high school student" as a joke. Somehow, I never changed it back

LOL , thought it would be incredible for a 16 years old to be so mature , have over 14k advanced math posts on this forum and still wasting time in high school.

 

[reenmachine]

Couples of quick questions (again about set theory):

- Power sets

I've been reading a basic set theory textbook online and they make the following statements:

The set of all subsets of a set A is called the power set of A and denoted as ℘(A).

For example, if A = {a,b} , ℘(A) = {∅, {a}, {b}, {a,b}}.

From the example above: a∈A; {a}⊆A; {a}∈℘(A)
∅⊆A; ∅∉A; ∅∈℘(A); ∅⊆℘(A)

My confusions about the above statements :

Why is {a}⊆ A? Why is the use of ''{}'' magically appearing to transform element a into subset a?
Why not {a}⊆ ℘(A) instead?

Same confusion with ∅∉A vs ∅∈℘(A), is it only a matter of definitions? Since ℘(A) is the set of all subsets of A , it means all subset of A are elements of ℘(A).Since ∅⊆A but ∅∉A , then by definition it means ∅ is an element of ℘(A) , but I'm wondering how could something that can't even be an element of a set on a more primitive level be transformed into an element of a bigger set based on a definition?

Another general question , is every element of any set guaranteed to be a subset of this set?

- Ordered pairs and cartesian product:

<a,b> =def{{a}, {a,b}}

So to make an analogy with integers , <1,2> = {{1} , {1,2}} but ≠ {{1} , {1,2} , {2}}.

Are {1} and {1,2} elements of A , subsets of A or both?

Suppose A = {a,b} and B=∅. What is A×B?

If we use the same technic , it would give us: {<a,∅> , <b,∅>} , but what does that even mean? Can a and ∅ be an ordered pairs?

Last question , suppose you have two sets:

Set A = (1,2,3,4)
Set B = (3,4,5,6)

How do you deal with the intersection in A x B?

sorry if those questions are brutal , I appreciate the help greatly!

cheers