Question about proof from a guy with a highschool education

[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

 

[Fredrik]

Why is {a}⊆ A?

Because A={a,b} and every member of {a} is a member of {a,b}. (The only member of {a} is a, and it's a member of {a,b}).

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

For all x, x is a member of {a} if and only if x=a. So {a} denotes the set whose only member is a.

For all x, x is a member of {a,b} if and only if x=a or x=b. So {a,b} denotes the set whose only members are a and b.

A set is a member of ℘(A) if and only if it's a subset of A. You defined A = {a,b}. If a≠b, a subset of A has 0,1 or 2 members. For each of the numbers 0,1,2, we can easily list all the subsets that have that number of members:

0: ∅
1: {a},{b}
2: {a,b}

So we can immediately conclude that ℘(A) = {∅, {a}, {b}, {a,b}}. (If a=b, we would have ℘(A)={∅,{a}} instead, because A={a}).

The statement {a}⊆ ℘(A) is true if and only if a is equal to one of the sets ∅, {a}, {b}, {a,b}. (It's certainly possible that a=∅ or a={b}, but the equalities a={a} and a={a,b} may not make sense. I need to think about that).

Same confusion with ∅∉A vs ∅∈℘(A), is it only a matter of definitions?

∅ is a subset of every set, because for all x, every member of ∅ is a member of x. (The statement "every member of ∅ is a member of x" can't be false since ∅ doesn't have a member that's not a member of x. And a statement that isn't false is true).

∅ is a member of {a,b} if and only if a=∅ or b=∅.

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

That's right.

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

What is A here? Did you mean A=<1,2>? I will assume that you did. {1} and {1,2} are elements of <1,2>, not subsets. 1 and 2 are however said to be components of <1,2>. The first component is 1, the second is 2.

Note however that if you say this to a typical physics student for example, they will not understand what you're talking about. They understand ordered pairs intuitively and have a lot of experience working with them, but they are not familiar with the definition <x,y>={{x},{x,y}}. They may not even be familiar with the notation <x,y>, because they're used to seeing the alternative notation (x,y) instead of <x,y>.

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?

I'm not sure what technique you're referring to. The definition of the power set? a and ∅ can certainly be the components of an ordered pair. (But I can't think of a situation where we would find this useful).

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?

I will simplify the example. I assume that you meant {...} when you wrote (...) (I would interpret the latter as meaning the same thing as <...>). If A={1,2} and B={2,3}, then A×B = {<1,2>,<1,3>,<2,2>,<2,3>}, i.e. 2 isn't given any special treatment just because it's a member of both.

 

[reenmachine]

Sorry for answering so late , I had quite the week-end :)

Because A={a,b} and every member of {a} is a member of {a,b}. (The only member of {a} is a, and it's a member of {a,b}).

So basically {a} is a singleton?

For all x, x is a member of {a} if and only if x=a. So {a} denotes the set whose only member is a.

For all x, x is a member of {a,b} if and only if x=a or x=b. So {a,b} denotes the set whose only members are a and b.

A set is a member of ℘(A) if and only if it's a subset of A. You defined A = {a,b}. If a≠b, a subset of A has 0,1 or 2 members. For each of the numbers 0,1,2, we can easily list all the subsets that have that number of members:

0: ∅
1: {a},{b}
2: {a,b}

So we can immediately conclude that ℘(A) = {∅, {a}, {b}, {a,b}}. (If a=b, we would have ℘(A)={∅,{a}} instead, because A={a}).

At the beginning all of this was very confusing , but apparently sitting back for a day and coming back to it works wonders.

Just a very basic question for the sake of ultimate clearness:

If A = {a,b} , then why would {a,b} be a subset of A (therefore becoming an element of ℘(A))?

The statement {a}⊆ ℘(A) is true if and only if a is equal to one of the sets ∅, {a}, {b}, {a,b}. (It's certainly possible that a=∅ or a={b}, but the equalities a={a} and a={a,b} may not make sense. I need to think about that).

Hmm that's a little bit more confusing.

∅ is a subset of every set, because for all x, every member of ∅ is a member of x. (The statement "every member of ∅ is a member of x" can't be false since ∅ doesn't have a member that's not a member of x. And a statement that isn't false is true).

∅ is a member of {a,b} if and only if a=∅ or b=∅.

Very clear.

What is A here? Did you mean A=<1,2>? I will assume that you did. {1} and {1,2} are elements of <1,2>, not subsets. 1 and 2 are however said to be components of <1,2>. The first component is 1, the second is 2.

I'm not even sure what I truly meant LOL.

The way I see it this morning though , is that <1,2> is an ordered pair , which could be expressed as a set by {{1} , {1,2}} , making {1} and {1,2} elements of this set.

1 and 2 are components , but at their root they were elements of sets that were used to make the cartesian product is that correct? To create an ordered pair , you have to take elements from set(s) , and this is where ordered pairs comes from(?).

I'm not sure what technique you're referring to. The definition of the power set? a and ∅ can certainly be the components of an ordered pair. (But I can't think of a situation where we would find this useful).

OK , but what would A X B gives us if A={1,2} and B={∅}?

<1,∅> , <2,∅> ?

I will simplify the example. I assume that you meant {...} when you wrote (...) (I would interpret the latter as meaning the same thing as <...>). If A={1,2} and B={2,3}, then A×B = {<1,2>,<1,3>,<2,2>,<2,3>}, i.e. 2 isn't given any special treatment just because it's a member of both.

Yes I meant {...} , sorry about that.Very clear again.Can't thank you enough.

To conclude this post , I'm still having trouble understanding the use of cartesian products or where does ordered pairs should be.When you are saying that A×B = {<1,2>,<1,3>,<2,2>,<2,3>} , what are the ordered pairs here? Elements? Subsets? Do we keep the ordered pair symbols to ensure that we don't forget that <1,2> are placed in a specific order whereas with {1,2} there's no order?

Just for a quick update on my (slow) progress , I'm getting into relations now.

 

[micromass]

So basically {a} is a singleton?

Yes.

At the beginning all of this was very confusing , but apparently sitting back for a day and coming back to it works wonders.

It always works wonders in math! I don't know why, but coming back to the same question after a day usually works.

Just a very basic question for the sake of ultimate clearness:

If A = {a,b} , then why would {a,b} be a subset of A (therefore becoming an element of ℘(A))?

You say that $B\subseteq A$ if every element of $B$ is an element of $A$. In your case, you have $\{a,b\}\subseteq A$. Indeed: what are the elements of $A$? They are $a$ and $b$. What are the elements of $\{a,b\}$, they are $a$ and $b$. So every element of $\{a,b\}$ is an element of $A$.

The way I see it this morning though , is that <1,2> is an ordered pair , which could be expressed as a set by {{1} , {1,2}} , making {1} and {1,2} elements of this set.

1 and 2 are components , but at their root they were elements of sets is that correct? To create an ordered pair , you have to take elements from set(s) , and this is where ordered pairs comes from(?).

You can create an ordered pair just by taking two arbitrary elements. They don't need to be elements of the same set (but they often are).

For example, I can take a pig and I can take the number $2$ and I can form
$(2,\text{pig}) = \{\{2\}, \{2,\text{pig}\}\}$.
I do need to say that this only works in naive set theory, but formal set theory is more restrictive. Don't worry about that for now though.

OK , but what would A X B gives us if A={1,2} and B={∅}?

<1,∅> , <2,∅> ?

Yes, it would give $A\times B=\{(1,\emptyset),(2,\emptyset)\}$.

To conclude this post , I'm still having trouble understanding the use of cartesian products or where does ordered pairs should be.When you are saying that A×B = {<1,2>,<1,3>,<2,2>,<2,3>} , what are the ordered pairs here? Elements? Subsets?

They are elements of $A\times B$. So $(1,3)\in A\times B$.

Do we keep the ordered pair symbols to ensure that we don't forget that <1,2> are placed in a specific order whereas with {1,2} there's no order?

Yes, that is basically the only reason we bother with ordered pairs. We know that $(1,2)\neq (2,1)$ (you should try to prove this actually!). But we know that $\{1,2\}=\{2,1\}$. So we care about ordered pairs because they give some kind of order.

Just for a quick update on my (slow) progress , I'm getting into relations now.

I recommend you to make some exercises on the things you've already seen. If you want, I can give you good exercises that you should consider.

 

[reenmachine]

It always works wonders in math! I don't know why, but coming back to the same question after a day usually works.

That's good.What I like is doing a little bit of sport to clear the mind.

You say that $B\subseteq A$ if every element of $B$ is an element of $A$. In your case, you have $\{a,b\}\subseteq A$. Indeed: what are the elements of $A$? They are $a$ and $b$. What are the elements of $\{a,b\}$, they are $a$ and $b$. So every element of $\{a,b\}$ is an element of $A$.

So A ⊆ A?

You can create an ordered pair just by taking two arbitrary elements. They don't need to be elements of the same set (but they often are).

For example, I can take a pig and I can take the number $2$ and I can form
$(2,\text{pig}) = \{\{2\}, \{2,\text{pig}\}\}$.
I do need to say that this only works in naive set theory, but formal set theory is more restrictive. Don't worry about that for now though.

Very clear!

They are elements of $A\times B$. So $(1,3)\in A\times B$.

Can we name the A x B set , like A x B = Set C , so that (1,3) ∈ F?

Yes, that is basically the only reason we bother with ordered pairs. We know that $(1,2)\neq (2,1)$ (you should try to prove this actually!). But we know that $\{1,2\}=\{2,1\}$. So we care about ordered pairs because they give some kind of order.

Hmm , let me give it a quick try.

In this proof we are accepting the axioms of Zermelo–Fraenkel set theory with choice.We will attempt to prove that (1,2) ≠ (2,1).

First let's express the ordered pairs into sets: (1,2) = {{1},{1,2}} and (2,1) = {{2},{2,1}}.

As we can see , both ordered pairs expressed as sets have unique elements ({1} in (1,2) but not in (2,1) and {2} in (2,1) but not in (1,2)) , and since {1} ≠ {2} it proves that (1,2) ≠ (2,1).

(I'm not sure whether or not I have to prove that {1} ≠ {2})

I recommend you to make some exercises on the things you've already seen. If you want, I can give you good exercises that you should consider.

Of course! That would be fantastic! Thanks a lot!

 

[micromass]

So A ⊆ A?

Yes, this is always true. Here is something you should try to prove:

$$A=B ~\text{if and only if}~A\subseteq B~\text{and} ~B\subseteq A$$

So there are two directions here, you already proved one!

Can we name the A x B set , like A x B = Set C , so that (1,3) ∈ F?

What is $F$??

Yes, you can say $A\times B = C$, and then $(1,3)\in C$. Saying "= Set C" is not a good notation though, just say "=C", it is clear that it's a set from context.

In this proof we are accepting the axioms of Zermelo–Fraenkel set theory with choice.We will attempt to prove that (1,2) ≠ (2,1).First let's express the ordered pairs into sets: (1,2) = {{1},{1,2}} and (2,1) = {{2},{2,1}}.

Both ordered pairs expressed as sets have unique elements ({1} in (1,2) and {2} in (2,1)) , and since {1} ≠ {2} , then (1,2) ≠ (2,1).

Hmmm, that is not enough. You indeed want to prove that $\{\{1,\},\{1,2\}\} \neq \{\{2\},\{2,1\}\}$. So you want to show this by saying that $\{1\}$ is an element of the LHS but not of the right hand side.

But to show this, you need to show that $\{1\}$ is not an element of $\{\{2\},\{2,1\}\}$. But to see that, you need that $\{1\} \neq \{2\}$ AND $\{1\}\neq \{1,2\}$. Just saying that $\{1\}\neq \{2\}$ is not enough.

Of course! That would be fantastic! Thanks a lot!

OK, here are some things you should try:

1) Remember that equality of sets is defined as follows: $A=B$ is true if all elements of $A$ are in $B$ and if all elements of $B$ are in $A$.
Prove:

• $A=A$
• If $A=B$, then $B=A$
• If $A=B$ and $B=C$, then $A=C$

2) Show that for any sets $A,B,C$ holds that

• $A\subseteq A$ (you already done this)
• If $A\subseteq B$ and $B\subseteq A$, then $A=B$. (again: remember the definition of equality of sets)
• If $A\subseteq B$ and $B\subseteq C$, then $A = C$.

3) Is it always true that $A\times B = B\times A$??

4) Prove the following (again: remember the definition of equality)

• $A\cap (B\cap C) = (A\cap B)\cap C$. Formulate something analogous for unions
• $A\cap (B\cup C) = (A\cap B)\cup (A\cap C)$.
• $A\cap A = A$ and $A\cup A=A$
• $(A\cap B)\times C = (A\times C)\cap (B\times C)$. Is the same true if we replace intersection by union?)

5) If $A\subseteq B$, is it true that $\mathcal{P}(A)\subseteq \mathcal{P}(B)$?

6) Calculate $\mathcal{P}(A)$ explictely for

• $A=\emptyset$
• $A = \{0\}$
• $A=\{0,1\}$
• $A=\{0,1,2\}$

How many elements does $\mathcal{P}(A)$ have if $A=\{0,1,...,n\}$?? With other words: how many subsets does $\{0,1,...,n\}$ have? Just make an educated guess without proof. Proving that your guess is true is quite difficult! It requiress the technique of proof by induction.

 

[reenmachine]

What is $F$??

Just a typo.Meant C.

Hmmm, that is not enough. You indeed want to prove that $\{\{1,\},\{1,2\}\} \neq \{\{2\},\{2,1\}\}$. So you want to show this by saying that $\{1\}$ is an element of the LHS but not of the right hand side.

But to show this, you need to show that $\{1\}$ is not an element of $\{\{2\},\{2,1\}\}$. But to see that, you need that $\{1\} \neq \{2\}$ AND $\{1\}\neq \{1,2\}$. Just saying that $\{1\}\neq \{2\}$ is not enough.

I was editing my post as you wrote , but I questionned the completeness of {1} ≠ {2}.I don't understand how I can prove it.Or did you mean I had to write BOTH , and not just {1} ≠ {2}?

EDIT: On second thought , you could say that {1} ≠ {1,2} because set {1} has only one element in 1 and set {1,2} have 2 elements in 1 and 2.Since 2 isn't in {1} , then {1} ≠ {1,2}.

I have to go out for dinner so I will try your exercices later today or tomorrow and post my results.

Thanks!

 

[micromass]

Just a typo.Meant C.



I was editing my post as you wrote , but I questionned the completeness of {1} ≠ {2}.I don't understand how I can prove it.Or did you mean I had to write BOTH , and not just {1} ≠ {2}?

You, you had to write both.

EDIT: On second thought , you could say that {1} ≠ {1,2} because set {1} has only one element in 1 and set {1,2} have 2 elements in 1 and 2.Since 2 isn't in {1} , then {1} ≠ {1,2}.

That works. But I want to note that this can be tricky. For example, $\{1,1\}=\{1\}$ (prove it!). So apparently $\{1,1\}$ contains 2 elements, but it actually contains only one.

Your approach works of course since $1\neq 2$. So it's all good. But don't think that $\{x,y\}$ always contains two elements!

 

[reenmachine]

You, you had to write both.
That works. But I want to note that this can be tricky. For example, $\{1,1\}=\{1\}$ (prove it!). So apparently $\{1,1\}$ contains 2 elements, but it actually contains only one.

Your approach works of course since $1\neq 2$. So it's all good. But don't think that $\{x,y\}$ always contains two elements!

{1} = {1,1} because both sets have only one element in 1.They are composed of the same single element , making them identical sets and therefore the same set and singleton.

...or all elements of {1} are in {1,1} and all elements of {1,1} are in {1}.

{x,y} is not necessarily composed of 2 elements because it's possible that x=y or that x or y = ∅

 

[reenmachine]

delete this post

sorry.

 

[Fredrik]

{1} = {1,1} because both sets have only one element in 1.They are composed of the same single element , making them identical sets and therefore the same set and singleton.

...or all elements of {1} are in {1,1} and all elements of {1,1} are in {1}.

Correct.

{x,y} is not necessarily composed of 2 elements because it's possible that x=y or that x or y = ∅

Correct, but I need to add that if x=∅ and y≠∅, then {x,y} has two elements.

If you want more exercises, you can just try to prove the identities in section 1.8 of the document you're reading. http://people.umass.edu/partee/NZ_2006/Set Theory Basics.pdf. The solutions should all look a lot like what I did in post #37. Several of the exercises that micromass suggested can be dealt with using the same method.