Question about proof from a guy with a highschool education

[reenmachine]

But then you're dealing with set difference, no? But the claim $(A\times C)\setminus C = A$ is simply not true. You should try to find a counterexample.

ok then what about (A × C) - (all elements of C) = A?

Sure that would leave all the elements of A that were previously inside ordered pairs , but since it doesn't matter how many times you write the same element in one set , then even if (A × C) = (1,2) , (1,3) where 2 and 3 are from C you're still left with A = 1.(I know i didnt use the set brackets , but couldn't find them quick enough for this short post)

 

[micromass]

ok then what about (A × C) - (all elements of C) = A?

Sure that would leave all the elements of A that were previously inside ordered pairs , but since it doesn't matter how many times you write the same element in one set , then even if (A × C) = (1,2) , (1,3) where 2 and 3 are from C you're still left with A = 1.(I know i didnt use the set brackets , but couldn't find them quick enough for this short post)

OK, I see what you mean. But I want you to realize that (A × C) - (all elements of C) = A is not what you want.

For example, take $A = \{1\}$ and $C=\{2\}$. Then $A\times C = \{(1,2)\}$. Now you want to remove all elements of $C$. But the only element in $C$ is $2$. And $2$ is not an element of $A\times C$. The only element of $A\times C$ is $(1,2)$. So if I remove $2$, then I just get $\{(1,2)\}$ again.

What you want to do is different. You want to obtain a set that is just the first coordinates of elements of $A\times C$. The best (and I guess, the only) way to write this down is by set-builder notation. It is written as follows

D=\{x\in A~\vert~\text{there exists an}~y\in C~\text{such that}~(x,y)\in A\times C\}

You should read this as follows: $D$ is the set of all elements $x$ in A such that there exists a $y\in C$ such that $(x,y)\in A\times C$.

This is the set you want. And indeed, this set is equal to $A$!

However, the proof you are trying to give is still incorrect even with this modification. The reason is again that you can't start from what you're trying to prove. Again, see the example

If 1=2, then 1*0 = 2*0, then 0=0.

What I wrote above is completely correct. But it would be incorrect to say that this proves that 1=2.

if (A × C) = (1,2) , (1,3) where

Don't forget the brackets! It should be

A\times C = \{(1,2), (1,3)\}

You might find it silly that I give so much criticism on your notation. But I think it's absolutely necessary to root out bad notations from the beginning. Bad notations may seem harmless now. But later on, bad notations will actually harm your understanding and make things very difficult.

 

[reenmachine]

OK, I see what you mean. But I want you to realize that (A × C) - (all elements of C) = A is not what you want.

For example, take $A = \{1\}$ and $C=\{2\}$. Then $A\times C = \{(1,2)\}$. Now you want to remove all elements of $C$. But the only element in $C$ is $2$. And $2$ is not an element of $A\times C$. The only element of $A\times C$ is $(1,2)$. So if I remove $2$, then I just get $\{(1,2)\}$ again.

What you want to do is different. You want to obtain a set that is just the first coordinates of elements of $A\times C$. The best (and I guess, the only) way to write this down is by set-builder notation. It is written as follows

D=\{x\in A~\vert~\text{there exists an}~y\in C~\text{such that}~(x,y)\in A\times C\}

You should read this as follows: $D$ is the set of all elements $x$ in A such that there exists a $y\in C$ such that $(x,y)\in A\times C$.

This is the set you want. And indeed, this set is equal to $A$!

However, the proof you are trying to give is still incorrect even with this modification. The reason is again that you can't start from what you're trying to prove. Again, see the example

If 1=2, then 1*0 = 2*0, then 0=0.

What I wrote above is completely correct. But it would be incorrect to say that this proves that 1=2.
Don't forget the brackets! It should be

A\times C = \{(1,2), (1,3)\}

You might find it silly that I give so much criticism on your notation. But I think it's absolutely necessary to root out bad notations from the beginning. Bad notations may seem harmless now. But later on, bad notations will actually harm your understanding and make things very difficult.

Ok I see where i was wrong now.Not sure I understand your ''modification'' but I guess i t doesn't matter for the moment as it stays irrelevant to the proof.

As for the notation , I mentionned I left them out on purpose , but I guess that was cheap on my part :X But no , I don't find anything you guys are saying silly , I'm here to learn and learning is both fun and painful.

Will try to prove the next exercises later.

thanks!

 

[micromass]

Ok I see where i was wrong now.Not sure I understand your ''modification'' but I guess i t doesn't matter for the moment as it stays irrelevant to the proof.

Set builder notation is important though. It comes up everywhere. I admit that the example above is not the easiest possible example of set builder notation though.

As for the notation , I mentionned I left them out on purpose , but I guess that was cheap on my part :X But no , I don't find anything you guys are saying silly , I'm here to learn and learning is both fun and painful.

It's perfectly ok to find something silly. You shouldn't blindly accept whatever we are telling you. Whenever something seems silly or unmotivated to you, it's better that you tell us. That way we can motivate what we're saying and help you ever further.
The problem with explaining this is that we have a lot of experience with proofs and set theory. This makes it very difficult to put ourselves in the shoes of somebody for who all of this is new. So any feedback is really important in order to allow us to adjust our explanations.

 

[reenmachine]

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

That was a tougher one , trickier.

Here I go:

We will attempt to prove that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Let x ∈ A be arbitrary.If x ∈ A , then {x}⊆ A.

If A ⊆ B , then x ∈ B , therefore {x}⊆ B.

Since {x}⊆ A , then {x}∈ ℘(A) , and since {x}⊆ B , then {x}∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

 

[lugita15]

Since all subsets of A are subsets of B

Wait a minute, you didn't prove that all subsets of A are subsets of B. You just proved that all *singleton* subsets of A are subsets of B. What about subsets of A that have more than one element?

 

[reenmachine]

How about that?

We will attempt to prove that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Let x and y ∈ A be arbitrary.If x and y ∈ A , then {x or y}⊆ A.

If A ⊆ B , then x and y ∈ B , therefore {x or y}⊆ B.

Since {x or y}⊆ A , then {x or y}∈ ℘(A) , and since {x or y}⊆ B , then {x or y}∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Take note that by {x or y} , I mean {x} , {y} and {x , y}.

Is that better?

 

[lugita15]

Since all subsets of A are subsets of B

You still haven't proved this. All you've proved is that all subsets of A which have one element or two elements are subsets of B. What about subsets of A that have more than two eleements?

Is that better?

It's better than before, but still not good enough. Here's a hint: Instead of just taking a subset of A that has one or two elements, consider an arbitrary subset of A.

 

[reenmachine]

You still haven't proved this. All you've proved is that all subsets of A which have one element or two elements are subsets of B. What about subsets of A that have more than two eleements?
It's better than before, but still not good enough. Here's a hint: Instead of just taking a subset of A that has one or two elements, consider an arbitrary subset of A.

So just start by saying : Let {x}⊆ A be arbitrary?

Let {x}⊆ A be arbitrary.Since A ⊆ B , it means that all elements of {x} are elements of B , therefore {x}⊆ B.Since {x}⊆ A , then {x}∈ ℘(A) , and since {x}⊆ B , then {x}∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

Does that work? If {x}⊆ A is arbitrary , it isn't necessarily a singleton anymore but a subset including an unknown number of elements?

Does this part:''Let {x}⊆ A be arbitrary.Since A ⊆ B , it means that all elements of {x} are elements of B , therefore {x}⊆ B'' proves that all subsets of A are subsets of B?

Another question , I wrote {x} instead of x since it was a subSET , but I didn't want to imply that {x} had only one element of x.Should I say ''Let x ⊆ A be arbitrary'' instead?

 

[Fredrik]

So just start by saying : Let {x}⊆ A be arbitrary?

Since you want to prove that ℘(A)⊆℘(B), you should start by saying "let x∈℘(A) be arbitrary", or equivalently, "let x⊆A be arbitrary".

To let {x}⊆ A be arbitrary is to consider an arbitrary singleton subset of A.

You seem to have the right idea about how to prove this, but the notation makes the proof weird.

 

[reenmachine]

Since you want to prove that ℘(A)⊆℘(B), you should start by saying "let x∈℘(A) be arbitrary", or equivalently, "let x⊆A be arbitrary".

To let {x}⊆ A be arbitrary is to consider an arbitrary singleton subset of A.

You seem to have the right idea about how to prove this, but the notation makes the proof weird.

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B , which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

is that correct?

Hey I really need to start getting them right on the first try :X , for all my mistakes I had the knowledge to realize it but didn't.

 

[reenmachine]

6) calculate $\mathcal{p}(a)$ explictely for

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

1) ℘(a): {∅}
2) ℘(a): {∅}
3) ℘(a): {∅,{1}}
4) ℘(a): {∅,{1},{2},{1,2}}

 

[lugita15]

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B , which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

is that correct?

It's fine for the most part, but if you want to be a bit more precise you can start by saying "let x ∈ ℘(A) be arbitrary", then say that x ⊆ A, then show that x ⊆ B, then say that x ∈ ℘(B), and then say that since all elements of ℘(A) are elements of ℘(B), it follows that ℘(A) ⊆ ℘(B).

 

[lugita15]

1) ℘(A): {∅}
2) ℘(A): {∅}
3) ℘(A): {∅,{1}}
4) ℘(A): {∅,{1},{2},{1,2}}

What about all the subsets that have 0's in them? Also, you seem to have forgotten that for any set A, A is always a subset of itself.

 

[reenmachine]

What about all the subsets that have 0's in them? Also, you seem to have forgotten that for any set A, A is always a subset of itself.

6) calculate $\mathcal{p}(a)$ explictely for

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

Woops! I thought 0 = ∅ but I already knew it was not the case , another brain cramp on my part :X

Corrected version:

1) ℘(A): {∅}
2) ℘(A): {∅ ,{0}}
3) ℘(A): {∅,{0},{1},{0,1}}
4) ℘(A): {∅,{0},{1},{2},{0,1}{0,2}{1,2}{0,1,2}}

 

[reenmachine]

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.

Is 2^(n+1) an acceptable answer?

This would complete the exercises you gave me.

 

[lugita15]

Is 2^(n+1) an acceptable answer?

Yes.

 

[Fredrik]

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B , which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B).

Since all subsets of A are subsets of B , all elements of ℘(A) are elements of ℘(B) , proving that if A ⊆ B , then ℘(A) ⊆ ℘(B).

This is good, but some of your statements are a bit awkward. Let me show you how I would do it, before I say anything specific. The statement we want to prove is this one: For all A, if A⊆B, then ℘(A)⊆℘(B). My proof:

Let A be an arbitrary set. Let x∈℘(A) be arbitrary. Since x⊆A and A⊆B, we have x⊆B. This implies that x∈℘(B).​

Compare these two parts of your proof:

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B,​

which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A)​

The first "it" refers to the thing you said in the previous sentence, but the second "it" refers to the thing you're saying in the first part of the current sentence. There's no need for an "it" in the second sentence. Just write "Since x ⊆ A, we have x ∈ ℘(A)". There's also a big overlap between the statements in the first paragraph (in the quote above) and the statements in the second paragraph. If you're going to say the things in the second paragraph, all of this is unnecessary: "Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B)."

 

[reenmachine]

This is good, but some of your statements are a bit awkward. Let me show you how I would do it, before I say anything specific. The statement we want to prove is this one: For all A, if A⊆B, then ℘(A)⊆℘(B). My proof:

Let A be an arbitrary set. Let x∈℘(A) be arbitrary. Since x⊆A and A⊆B, we have x⊆B. This implies that x∈℘(B).​

Compare these two parts of your proof:

Let x ⊆ A be arbitrary.Since A ⊆ B , it means that all elements of x are elements of B,​

which implies that x ⊆ B.Since x ⊆ A , it implies that x ∈ ℘(A)​

The first "it" refers to the thing you said in the previous sentence, but the second "it" refers to the thing you're saying in the first part of the current sentence. There's no need for an "it" in the second sentence. Just write "Since x ⊆ A, we have x ∈ ℘(A)". There's also a big overlap between the statements in the first paragraph (in the quote above) and the statements in the second paragraph. If you're going to say the things in the second paragraph, all of this is unnecessary: "Since x ⊆ A , it implies that x ∈ ℘(A) , and since x ⊆ B , it implies that x ∈ ℘(B)."

What do you mean by ''Let A be an arbitrary set.'' and why is it important?

I get your other points , thanks!

What should I do next? Continue the textbook and start learning about relations? Have I done enough proof of this part of the textbook? I'm getting hungry for some new concepts :D

Also was the 2^(n+1) answer to the micromass question hard to find?

Anyway , thanks again Fredrik , your help is greatly appreciated (same with everybody else helping me here).

 

[Fredrik]

What do you mean by ''Let A be an arbitrary set.'' and why is it important?

It's not. It's just that several times recently, I've found myself saying that the most common mistake made by people who lack experience with proofs, is to not make it clear which ones of their variables have been assigned values, and which ones are targets of a "for all" or a "there exists". So I wanted to make it clear that A is the target of a "for all". Of course, so is B. It doesn't make sense to include the statement "Let A be an arbitrary set" unless we also include something similar for B.

Note that this is the theorem we want to prove: For all A and all B, if A⊆B, we have ℘(A)⊆℘(B). This is an alternative way of saying the same thing: For all A and B such that A⊆B, we have ℘(A)⊆℘(B).

A good way to start the proof is this:

Let A and B be arbitrary sets such that A⊆B. Let x∈℘(A) be arbitrary.​

Here we are explicitly stating the assumptions in the proof. That's never a bad thing. But it's not always required. Since the theorem makes it clear that A and B are arbitrary sets such that A⊆B, it's also OK to just start the proof like this:

Let x∈℘(A) be arbitrary.​

What should I do next? Continue the textbook and start learning about relations? Have I done enough proof of this part of the textbook? I'm getting hungry for some new concepts :D

You should move on. You will have to use these same techniques to prove statements about relations and functions, so it's not like we're leaving them behind.

Also was the 2^(n+1) answer to the micromass question hard to find?

It's fairly easy to guess, if you just count the number of subsets for each of the cases n=1, n=2, n=3. But it's somewhat hard to prove the formula for arbitrary n rigorously, since you have to know how to prove infinitely many statements in a finite number of steps. This is what induction is for. The idea is this: For each non-negative integer k, let P(k) denote the statement "{0,1,...,k} has 2^k+1 subsets". We want to prove the infinitely many statements

P(0)
P(1)
P(2)
...

Induction is the trick to do it by proving only the following two statements:

P(0)
For all integers k such that k≥0, if P(k), then P(k+1).

 

[reenmachine]

Very clear! Thank you again.

I will move on and come back when I don't understand something in the textbook (which should be fairly soon I guess lol).

I also purchased the Book of Proof that people suggested thanks to your help , I will probably receive it at the end of the week or monday.I'm aware that it is free online but I like to have it in my hands in case I'm not in front of my computer.

cheers!

 

[Fredrik]

I also purchased the Book of Proof that people suggested thanks to your help , I will probably receive it at the end of the week or monday.I'm aware that it is free online but I like to have it in my hands in case I'm not in front of my computer.

Sounds like a good idea. I've been somewhat skeptical about books about proofs, since I've been thinking that the way to learn proofs is to just study many examples, and to practice writing proofs while you're doing this. But I've realized that I was fortunate to have math teachers who explained the basics of set theory at the beginning of several different courses in the first and second year at the university. And the first course we got covered truth tables and stuff. If one doesn't already know the basics of set theory and logic, and doesn't have teachers who keep explaining those things repeatedly, a book like this will make it much easier to get started.

I realized that some of my old posts have discussed definitions of the term "function", so I figured I might as well paste some of what I've said into this thread.

The idea behind the definition of "function" is that we should be able to think of a function f:X→Y as a rule that takes each member of the set X to exactly one member of the set Y. But to properly define the term in the framework of ZFC set theory, we must specify which set f is. Since there are many sets that we can think of as representing a rule like that, there are also many ways to make the concept of "function" (that we already understand on an intuitive level) mathematically precise. These are two similar, but not equivalent, ways to make the concept mathematically precise:

Definition 1

A set $f\subseteq X\times Y$ is said to be a function from X into Y, if
(a) For all $x\in X$, there's a $y\in Y$ such that $(x,y)\in f$.
(b) For all $x,x' \in X$ and all $y\in Y$, if $(x,y)\in f$ and $(x',y)\in f$, then $x=x'$.
X is said to be the domain of f. Y is said to be a codomain of f. f is also called the graph of f. So the function and its graph is the same thing.

Definition 2

A triple $f=(X,Y,G)$ such that $G\subseteq X\times Y$ is said to be a function from X into Y, if
(a) For all $x\in X$, there's a $y\in Y$ such that $(x,y)\in G$.
(b) For all $x,x' \in X$ and all $y\in Y$, if $(x,y)\in G$ and $(x',y)\in G$, then $x=x'$.
X is said to be the domain of f. Y is said to be the codomain of f. G is said to be the graph of f.

If we use definition 1, then a function has many codomains. If f is a function from X into Y and Y is a subset of Z, then Z is also a codomain of f. If we use definition 2, each function has exactly one codomain.
​

There are other definitions that make just as much sense as these two. It rarely matters which one you use as the definition of "function". (You will still think of a function from X into Y as a rule that associates exactly one element of Y with each element of X). Note that a function from X into Y is (according to definition 1) a special kind of subset of X×Y. A subset of X×Y is said to be a binary relation on X×Y. If Y=X, the terminology is simplified somewhat, and we say that a subset of X×X is a binary relation on X.

So a function is a special kind of binary relation. The idea behind a binary relation can be understood by considering the order < on ℝ. We have an intuitive understanding of what it means for a number to be less than another, but we need to make it mathematically precise. The idea is to define < as the set of all pairs (x,y) in ℝ×ℝ such that x is less than y in the intuitive sense. So if you imagine a plane with an "x axis" drawn to the right, and a "y axis" drawn up, and you draw a diagonal line that makes a 45 degree angle with both axes from "down left" to "up right" (this is the set of points (x,y) such that x=y), the set of points above that line is what we will call <. The notation x<y is then defined to mean $(x,y)\in <$.

Note that I'm just trying to illustrate what sort of thing < is. The above isn't precise enough to be a valid definition of <.

Both the "book of proof" and the pdf you found define relations before functions, because binary relations are a special kind of relation, and functions are a special kind of binary relation. This is all very logical, but the most important part of it all is the definition of "function", so I want to mention it as early as possible.

In the thread that I copied the above from, several people mentioned to me that it's fairly common to use the term "range" for what I call "codomain". I don't like that terminology, but you need to be aware that it exists. I define the range of $f:X\to Y$ as the set $f(X)=\{f(x)|x\in X\}$.

 

[CompuChip]

Is 2^(n+1) an acceptable answer?

Actually there is another proof for this that does not require induction. I don't know if giving the full proof will confuse you, but in case you're interested, I can sketch it.

Let A = {1, 2, ..., n} be a set of n elements (I'll leave out the 0 to avoid the slightly awkward n + 1). Let S be a subset of A and construct an n-tuple b_i (i = 1, .., n) where b_i = 0 if i \not\in S and b_i = 1 if i \in S. So for example, if n = 5 and S = {1, 3, 4} then you write down <1, 0, 1, 1, 0>. It's pretty straightforward to see that the number of such possible n-tuples is 2ⁿ (as for each of the n positions you can either write 0 or 1). The trick is that each of these maps one-on-one to a subset of A, i.e. every such n-tuple represents a subset of A, and every subset of A is represented by exactly one such n-tuple. (I don't know if you have learned about formal theory of functions, but I'm basically saying that there is a bijective mapping from \mathscr{P}(A) onto \{ 0, 1 \}^n).

 

[reenmachine]

Hey guys! Hope everything is going well for y'all!

I've been pretty busy these past few days so I haven't had the chance to continue my set theory textbook but here I am now reading it and I admit I'm hitting a wall.There's some things I don't understand about relations so I'm just going to quote the textbook (if it is allowed?!) and ask some questions and hopefully you guys can explain to me (if you have the time of course).

Note to Fredrik: Your last post seems to have some material on what I'm about to ask , I tried to read it fast but I didn't manage to understand it , I'll give it another in-depth shot later so I apologize if some of my questions were answered in your post.I will reply to your post later or tomorrow as I do have some questions about it.

We may write Rab or aRb for “a bears R to b”. And when we formalize relations as sets of ordered pairs of elements, we will officially write <a,b> ∈ R.

My first question is probably due to english being my second language , but when they say ''a bears Relation to b'' , what does bears truly mean? I checked the definition and it says ''to hold up , support'' or ''to carry from one place to another , transport''.

I don't understand what they mean by ''when we formalize relations as sets of ordered pairs of elements , we will officially write <a,b> ∈ R''.In <a,b> , are a and b elements or componants? I thought an ordered pair as a whole could be an element but not the individual components of the ordered pair.Also , how can a relation be a set? Basically as you can see I don't have a clue.

If A and B are any sets and R ⊆ A × B , we call R a binary relation from A to B or a binary relation between A and B.A relation R ⊆ A × A is called a relation in or on A.

So now R would be a subset of a cartesian product of 2 sets? Previously , they mentionned that an ordered pair was the element of R , but then R would be the subset of a cartesian product of 2 sets? Maybe I should know what a relation do in general but for the moment I'm clueless.Also , why binary relation if a subset? I understand these are very basic and vague question but this is where my brain is at the moment.

The set dom R = {a<a,b> ∈ R for some b} is called the domain of the relation R and the set range R = {b <a,b> ∈ R for some a} is called the range of the relation R

Here I'm not sure which question to ask , I guess a refreshing on what a domain is would be useful.What's the real difference between a set dom and a set range? First of all what does the first ''a'' or ''b'' between the brackets means? I see the range is when the ''b'' is first , ''b'' being the second components of the ordered pair.In the range example , what does it mean that the ordered pair is an element of the Relation ''for some a''.For some ''a''?Don't get it.

I apologize if this post is a little bit more confusing than my previous ones , but it reflects my state of mind at the moment

If my questions are too vague to answer , please tell me so and I'll try to come up with something clearer.

Thanks a lot!

 

[micromass]

My first question is probably due to english being my second language , but when they say ''a bears Relation to b'' , what does bears truly mean? I checked the definition and it says ''to hold up , support'' or ''to carry from one place to another , transport''.

I'd say that it means "being in relationship to". Let me start by giving two examples.

An example of a relationship is "being friends with". We can denote this relationship by F. Then we can say things like "micromass is friends with Fredrik" (hopefully) and we denote this by micromass R Fredrik.

A more serious and mathematical example would be the < relation. This is a relation between numbers (let's restrict ourselves to the numbers 1, 2 and 3 for notational issues). So we have things like 1<3 and 2<3.

This is what you should intuitively understand by a relation. However, this is not very mathematical. What exactly is a relation?? Modern mathematics has as philosophy that everything defined must be a set. So a relationship must be defined as a set somehow.

We do this by saying that a relation is a certain subset of $A\times B$.

For example, consider $A=\{1,2,3\}$ and $B=\{1,2,3\}$. Then we can perfectly define a relation by $R=\{(1,2),(1,3),(2,3)\}$.

What does this mean?? If an element $(a,b)\in R$, then that means that $aRb$ or in other words, it means that $a$ is in an $R$-relation with $b$.
In our example, we have that $1R2$, $1R3$ and $2R3$. So we see that our relation is exactly the < relation!

Another example of a relation on the same sets $A$ and $B$ would be $\{(1,1), (2,2), (3,3)\}$. This relation would be the equality.

It may look weird that a relation is defined a certain subset of a cartesian product. But this is only done to make things mathematically rigorous and to fit relations in the current mathematical framework of set theory. The intuition should be the relations such as <, = or "being friends with".

Let's assume for a minute that marriage can only happen between a man and a woman. Now we have another relation: "is married to". In that case, we can work with the following sets: take $A$ the set of all men in the world, take $B$ the set of all women in the world. Then we got a married-relationship $R$ that is a subset of $A\times B$ and this is a good example of a case where $A\neq B$! Now, if $(a,b)\in R$, then that means that $a$ and $b$ are married. For example $(\text{Barack Obama}, \text{Michelle Obama})\in R$.

A more mathematical example is the following. Take a set $A$, and take the powerset $\mathcal{P}(A)$. Then we can define relations $R\subseteq A\times \mathcal{P}(A)$. For example, the relation "is an element of" is such a relation.

Concretely, take $A=\{1,2\}$, then the relation "is element of" can be seen as $\{(1,\{1\}),(1,\{1,2\})\}\subseteq A\times \mathcal{P}(A)$.

In <a,b> , are a and b elements or componants?

We have that $a$ and $b$ are components of the ordered pair $(a,b)$.

I thought an ordered pair as a whole could be an element but not the individual components of the ordered pair.

Not sure what you mean. Take $(1,2)$, then $1$ and $2$ are components of $(1,2)$. An ordered pair can be an element of a set, for example $(1,2)\in \{(1,2)\}$. The components of an ordered pair can also be elements of some set, for example $1\in \{1\}$. However, the components of an ordered pair are generally not elements of the ordered pair.

Also , how can a relation be a set?

By definition of a relation. We define a relation as a certain set.

Very important: EVERYTHING in mathematics is a set. So everything that you encounter in mathematics has been or should be defined as a set. This is one of the philosophies of mathematics. There are other kinds of mathematics where not everything is a set, but those are rarely used.

So now R would be a subset of a cartesian product of 2 sets? Previously , they mentionned that an ordered pair was the element of R , but then R would be the subset of a cartesian product of 2 sets Maybe I should know what a relation do in general but for the moment I'm clueless.Also , why binary relation if a subset? I understand these are very basic and vague question but this is where my brain is at the moment.

Formally: given sets $A$ and $B$, then every subset of $A\times B$ is called a relation from $A$ to $B$. This is just a definition. Some of the relations from $A$ to $B$ are useful, most are not useful.

For example, let $A=B=\{1,2,3,65\}$, then $R=\{(1,65),(65,3)\}$ is a relation from $A$ to $B$ because it is a subset of $A\times B$. However, it is not a very useful relation.
A useful relation would be $\{(1,1), (2,2), (3,3), (65,65)\}$ which just formalizes the equality.
Whether a relation is useful or not depends on circumstances of course. I'm sure we can invent some circumstances in which the previous relation $R$ is useful.

Here I'm not sure which question to ask , I guess a refreshing on what a domain is would be useful.

Those are questions about functions. Let's not touch that yet until you know relations well. Domain and codomain are things that make sense with relations however.

For example, let $R$ be a relation from $A$ to $B$. The only thing that this means is that $R\subseteq A\times B$. Elements of $R$ have the form $(a,b)$. The set of all $a$ that occur is called the domain, the set of all $b$ that occur is called the codomain.

For example, consider $A=B=\{1,2,3\}$. Take the relation <, that means: $\{(1,2),(1,3),(2,3)\}$. What is the domain?? Well, exactly the elements occurring in the first components. So we have that the domain is equal to $\{1,2\}$. The element $3$ is not in the domain because $(3,x)$ is not an element of the relation for any $x$.
Similarly, the range is $\{2,3\}$, they are all the elements occurring in the second components.

Let's take our marriage relation. So $A$ is the set of all the men, $B$ is the set of all the women. Then the domain of the relation consists of all the married men, the range consists of all the married women. For example, Barack Obama is in the domain of the relation. The pope is not in the domain of the relation.

Then we also have the codomain. Let $R$ be a relation from $A$ to $B$ (thus: $R\subseteq A\times B$). Then $B$ is defined as the codomain.
The set $A$ has no special name, because we will see that in the case of functions that the domain of a relation will always coincide with $A$. This is obviously not true for all relations, but often we are only interested in functions.

 

[reenmachine]

I'd say that it means "being in relationship to". Let me start by giving two examples.

An example of a relationship is "being friends with". We can denote this relationship by F. Then we can say things like "micromass is friends with Fredrik" (hopefully) and we denote this by micromass R Fredrik.

A more serious and mathematical example would be the < relation. This is a relation between numbers (let's restrict ourselves to the numbers 1, 2 and 3 for notational issues). So we have things like 1<3 and 2<3.

This is what you should intuitively understand by a relation. However, this is not very mathematical. What exactly is a relation?? Modern mathematics has as philosophy that everything defined must be a set. So a relationship must be defined as a set somehow.

We do this by saying that a relation is a certain subset of $A\times B$.

For example, consider $A=\{1,2,3\}$ and $B=\{1,2,3\}$. Then we can perfectly define a relation by $R=\{(1,2),(1,3),(2,3)\}$.

What does this mean?? If an element $(a,b)\in R$, then that means that $aRb$ or in other words, it means that $a$ is in an $R$-relation with $b$.
In our example, we have that $1R2$, $1R3$ and $2R3$. So we see that our relation is exactly the < relation!

Another example of a relation on the same sets $A$ and $B$ would be $\{(1,1), (2,2), (3,3)\}$. This relation would be the equality.

It may look weird that a relation is defined a certain subset of a cartesian product. But this is only done to make things mathematically rigorous and to fit relations in the current mathematical framework of set theory. The intuition should be the relations such as <, = or "being friends with".

Let's assume for a minute that marriage can only happen between a man and a woman. Now we have another relation: "is married to". In that case, we can work with the following sets: take $A$ the set of all men in the world, take $B$ the set of all women in the world. Then we got a married-relationship $R$ that is a subset of $A\times B$ and this is a good example of a case where $A\neq B$! Now, if $(a,b)\in R$, then that means that $a$ and $b$ are married. For example $(\text{Barack Obama}, \text{Michelle Obama})\in R$.

A more mathematical example is the following. Take a set $A$, and take the powerset $\mathcal{P}(A)$. Then we can define relations $R\subseteq A\times \mathcal{P}(A)$. For example, the relation "is an element of" is such a relation.

Concretely, take $A=\{1,2\}$, then the relation "is element of" can be seen as $\{(1,\{1\}),(1,\{1,2\})\}\subseteq A\times \mathcal{P}(A)$.
We have that $a$ and $b$ are components of the ordered pair $(a,b)$.
Not sure what you mean. Take $(1,2)$, then $1$ and $2$ are components of $(1,2)$. An ordered pair can be an element of a set, for example $(1,2)\in \{(1,2)\}$. The components of an ordered pair can also be elements of some set, for example $1\in \{1\}$. However, the components of an ordered pair are generally not elements of the ordered pair.
By definition of a relation. We define a relation as a certain set.

Very important: EVERYTHING in mathematics is a set. So everything that you encounter in mathematics has been or should be defined as a set. This is one of the philosophies of mathematics. There are other kinds of mathematics where not everything is a set, but those are rarely used.
Formally: given sets $A$ and $B$, then every subset of $A\times B$ is called a relation from $A$ to $B$. This is just a definition. Some of the relations from $A$ to $B$ are useful, most are not useful.

For example, let $A=B=\{1,2,3,65\}$, then $R=\{(1,65),(65,3)\}$ is a relation from $A$ to $B$ because it is a subset of $A\times B$. However, it is not a very useful relation.
A useful relation would be $\{(1,1), (2,2), (3,3), (65,65)\}$ which just formalizes the equality.
Whether a relation is useful or not depends on circumstances of course. I'm sure we can invent some circumstances in which the previous relation $R$ is useful.
Those are questions about functions. Let's not touch that yet until you know relations well. Domain and codomain are things that make sense with relations however.

For example, let $R$ be a relation from $A$ to $B$. The only thing that this means is that $R\subseteq A\times B$. Elements of $R$ have the form $(a,b)$. The set of all $a$ that occur is called the domain, the set of all $b$ that occur is called the codomain.

For example, consider $A=B=\{1,2,3\}$. Take the relation <, that means: $\{(1,2),(1,3),(2,3)\}$. What is the domain?? Well, exactly the elements occurring in the first components. So we have that the domain is equal to $\{1,2\}$. The element $3$ is not in the domain because $(3,x)$ is not an element of the relation for any $x$.
Similarly, the range is $\{2,3\}$, they are all the elements occurring in the second components.

Crystal clear explanations! This was a great post!

So suppose everything is a set , is ''×'' a set in A × B?

EDIT: about this part:

An example of a relationship is "being friends with". We can denote this relationship by F. Then we can say things like "micromass is friends with Fredrik" (hopefully) and we denote this by micromass R Fredrik.

Can you give me an example (if it exist!) of where ''F'' could fit in a formula (as opposed to R) based on this context?

Let's take our marriage relation. So $A$ is the set of all the men, $B$ is the set of all the women. Then the domain of the relation consists of all the married men, the range consists of all the married women. For example, Barack Obama is in the domain of the relation. The pope is not in the domain of the relation.

Then we also have the codomain. Let $R$ be a relation from $A$ to $B$ (thus: $R\subseteq A\times B$). Then $B$ is defined as the codomain.
The set $A$ has no special name, because we will see that in the case of functions that the domain of a relation will always coincide with $A$. This is obviously not true for all relations, but often we are only interested in functions.

This is the only part I'm not sure of understanding , if you take A as the set of all men and B as the set of all women (with the relation being marriage) , the domain of the relation consist of all married men and the range of the relation consist of all married women , but based on your last paragraph , is the range the same as co-domain?

EDIT: Is the co-domain the set of all women while the range only the set of all married women , meaning that some women are just elements of the co-domain while others are elements of both the co-domain and the range?

 

[micromass]

Crystal clear explanations! This was a great post!

So suppose everything is a set , is ''×'' a set in A × B?

You mean the symbol that denotes multiplication?? No, it's just a symbol. It's not a part of the mathematics. This is getting into mathematical logic, but there is a difference between the actual mathematics and the symbols used to describe the mathematics. For example, the empty set is part of the mathematics, but the symbol $\emptyset$ is not.

EDIT: about this part:

Can you give me an example of where ''F'' could fit in a formula (as opposed to R)?

Sorry, the R should have been an F.

This is the only part I'm not sure of understanding , if you take A as the set of all married men and B as the set of all married women , if the domain of the relation consist of all married men and the range of the relation consist of all married women , based on your last paragraph , is the range the same as co-domain?

I took A the set of all men (not necessarily married). I took B the set of all women. In that the case, the range of the relation "is married to" is not equal to the codomain. Indeed, the range is the set of all married women. The codomain is the set of all women.

If I take A the set of all married men and if I take B the set of all married women, then the range equals the codomain.

Is this the paragraph you're not understanding:

The set A has no special name, because we will see that in the case of functions that the domain of a relation will always coincide with A. This is obviously not true for all relations, but often we are only interested in functions.

In that case, don't worry. It will be more clear later. The point is that the terminology domain, codomain and range is most often used with functions. It is very seldom used with general relations. So don't worry too much about these things until you're studying functions.

 

[Fredrik]

so I'm just going to quote the textbook (if it is allowed?!)

It's both allowed and encouraged. If the context is relevant, you should also mention the page number in the online version.

Note to Fredrik: Your last post seems to have some material on what I'm about to ask , I tried to read it fast but I didn't manage to understand it , I'll give it another in-depth shot later so I apologize if some of my questions were answered in your post.I will reply to your post later or tomorrow as I do have some questions about it.

You may find it easier after reading micromass' reply about relations, and in particular the comments about how everything is a set (except the symbols of the language that we use to talk about sets).

When I learned these things, I learned about functions before relations. I thought that it would probably have been harder to learn about relations first, because I had a stronger intuitive understanding of functions. That's why I started with functions here. But now you're already well on your way to understanding relations, so you should continue with that before you move on to functions.

Functions are often taught by saying that a function from X into Y is "a rule that associates exactly one element of Y with each element of X". But this isn't a definition, because what the bleep is a "rule" and what does "associates" mean? To define "function" in the framework of ZFC set theory, in which everything is a set (even the elements of the sets are sets), we must specify which sets will be called "functions".

When you look at one of my definitions (either of them), note that condition (a) can be thought of as saying that f associates at least one y in Y with each x in X, and that condition (b) can be thought of as saying that f associates at most one y in Y with each x in X. This is why these definitions can be thought of as making the idea of "a rule that associates exactly one element of Y with each element of X" mathematically precise.

 

[Fredrik]

An example of a relationship is "being friends with". We can denote this relationship by F. Then we can say things like "micromass is friends with Fredrik" (hopefully) and we denote this by micromass R Fredrik.

I do think of you as a friend.

 

[reenmachine]

You mean the symbol that denotes multiplication?? No, it's just a symbol. It's not a part of the mathematics. This is getting into mathematical logic, but there is a difference between the actual mathematics and the symbols used to describe the mathematics. For example, the empty set is part of the mathematics, but the symbol $\emptyset$ is not.

Hmmm , but if we take something like A × B , isn't the ''×'' a relation from A to B , meaning that it should be a set since all relations will be sets?

Sorry, the R should have been an F.

So we would write micromass F Fredrik.In fact , do we often write another letter than ''R'' to describe a relation , depending on which letter we attribute to the specific relation we are working with?

I took A the set of all men (not necessarily married). I took B the set of all women. In that the case, the range of the relation "is married to" is not equal to the codomain. Indeed, the range is the set of all married women. The codomain is the set of all women.

If I take A the set of all married men and if I take B the set of all married women, then the range equals the codomain.

I was probably editing while you were typing the post , I realized it right after.

In that case, don't worry. It will be more clear later. The point is that the terminology domain, codomain and range is most often used with functions. It is very seldom used with general relations. So don't worry too much about these things until you're studying functions.

Good , thanks a lot again.

 

[Fredrik]

Hmmm , but if we take something like A × B , isn't the ''×'' a relation from A to B , meaning that it should be a set since all relations will be sets?

He's making a distinction between relations and the symbols that represent them. Relations are sets. Symbols are not. They are part of the language that we use to talk about sets.

The symbol × doesn't represent a relation from A into B. The notation A×B does however represent a relation from A into B.

So we would write micromass F Fredrik.In fact , do we often write another letter than ''R'' to describe a relation , depending on which letter we attribute to the specific relation we are working with?

You can use any symbol you want. It's actually pretty uncommon to use letters for binary relations. People seem to prefer symbols like $<,\leq,\precsim$. If it's an equivalence relation, most people seem to prefer symbols that don't appear to be "pointing" to the left or right, symbols like $\sim,\simeq,\equiv$.

 

[CompuChip]

\times is not a relation, it is a symbol denoting an operation on two sets which produces another set. If you want, view it as the intersection in A \cap B or the complement in A^\mathrm{c}.

As for relations, R is generally used for relations, just like x is generally used for variables, but you can have different ones. Unlike variables, In the case of relations, these are often not letters but symbols, such as <. E.g. you could write
"Define the relation < by ..."
Another common way of putting this is:
"Define a relation R by ... If (a, b) \in R, we write a < b."
i.e. we first define the relation in a formal way, and then introduce a more intuitive notation matching the purpose of the definition.

 

[reenmachine]

Thanks guys! So basically × is an element of the set containing all mathematical symbols?

 

[Fredrik]

Thanks guys! So basically × is an element of the set containing all mathematical symbols?

Yes, if you mean a set in the sense of naive set theory. I'm not sure that it would make sense to say that it's a set in the sense of ZFC set theory, since the set of symbols is part of what defines the language used to form the sentences that define the set theory. These are aspects of mathematical logic that I don't fully understand myself. I just think that some caution is required to avoid circularity.

 

[reenmachine]

Yes, if you mean a set in the sense of naive set theory. I'm not sure that it would make sense to say that it's a set in the sense of ZFC set theory, since the set of symbols is part of what defines the language used to form the sentences that define the set theory. These are aspects of mathematical logic that I don't fully understand myself. I just think that some caution is required to avoid circularity.

Still , it doesn't make sense that ''something'' wouldn't be a set in U.If U is the set containing all sets , and everything is a set , then somehow the human thoughts that produce these symbols are sets and so on...Why exclude some sets because they were concepts created to explain their own existence? I understand there's a difference between the symbol and the ''transformation of some sort'' that happens expressed by a symbol , but why can't they both be in some kinds of different sets?

Perhaps those questions are more philosophical than mathematical.

 

[CompuChip]

The idea that a set is a general "collection of objects" makes sense, but it leads to some paradoxes. For example, http://en.wikipedia.org/wiki/Russell's_paradox]Russell's[/PLAIN] paradox, which can be phrased as "if the barber only shaves the men who do not shave themselves, does he shave himself?" or more formally as "if S is defined as { S | S is a set that contains itself }, then is S \in S?".

This goes to show that what is now called intuitive set theory is not a good basis for a rigorous theory, leading to - amongst others - ZF(C).

 

[reenmachine]

The idea that a set is a general "collection of objects" makes sense, but it leads to some paradoxes. For example, http://en.wikipedia.org/wiki/Russell's_paradox]Russell's[/PLAIN] paradox, which can be phrased as "if the barber only shaves the men who do not shave themselves, does he shave himself?" or more formally as "if S is defined as { S | S is a set that contains itself }, then is S \in S?".

This goes to show that what is now called intuitive set theory is not a good basis for a rigorous theory, leading to - amongst others - ZF(C).

The fact that he only shaves the men who do not shave themselves doesn't make it obligatory that he shaves all the men who do not shave themselves , but the fact that he only shaves the men who do not shave themselves makes it impossible for him to shave his own self , so the answer would be no , he doesn't shave himself.

But I get your point , if he needs to shave all men who doesn't shave themselves then the paradox is still there.

I'm not sure what to say , this probably has been thought by logic/mathematic superstars , so it's embarrassing to give it a shot.

One hypothesis is that a set can't contain itself , meaning that the concept of U is only practical , not representing truth.What I mean is that the logic of the universe would always make it impossible for a set to contain itself , something would get in the way of that happening , logically.

edit: Just to push a little further , suppose the statement is:

''If he needs to shave all men who do not shave themselves , does he shave himself?'' , the key word would be ''needs'' which would in reality makes it impossible to happen one way or another.

Then you could say someone said:''He shaved all men who do not shave themselves'' , then the key concept would be that of a lie.You could logically take for granted this qualify as a lie and his statement lacked precision to describe what really happened.

 

[Fredrik]

As CompuChip has already said, there's no "set of all sets" in ZFC set theory. I'm sure I've seen micromass prove that, but unfortunately I don't remember the proof.

It's easier to prove that $\{x|x\notin x\}$ isn't a set. Suppose that it is a set and denote it by R. If $R\in R$, then the definition of R tells us that $R\notin R$. This is a contradiction. If $R\notin R$, then the definition of R tells us that $R\in R$. This is also a contradiction. So we have a contradiction regardless of whether $R\in R$ is true or false. This means that the original assumption that R is a set is false.

 

[micromass]

As CompuChip has already said, there's no "set of all sets" in ZFC set theory. I'm sure I've seen micromass prove that, but unfortunately I don't remember the proof.

It's easier to prove that $\{x|x\in x\}$ isn't a set. Suppose that it is a set and denote it by R. If $R\in R$, then the definition of R tells us that $R\notin R$. This is a contradiction. If $R\notin R$, then the definition of R tells us that $R\in R$. This is also a contradiction. So we have a contradiction regardless of whether $R\in R$ is true or false. This means that the original assumption that R is a set is false.

There's a typo there, you should have talked about $\{x~\vert ~x\notin x\}$, as I'm sure you know.

Basically, you've proved it yourself now that the set of all sets do not exist. Why? It is an axiom that if $A$ is a set and if $P$ is some property, then
\{x\in A~\vert~P\}
is a set. Now, if the set of all set existed, then we can define this set as $A$. We can also define the property $P$ as $x\notin x$. So if the set of all sets existed, then also
\{x\in A~\vert~x\notin x\}
exists. But this would yield the Russell paradox as shown in the quote.

Anyway, the set of all sets is a fun thing to discuss. It doesn't exist in ZFC. But there are many other set theories where a set of all sets does exist. Those set theories avoid the Russel paradox in another way.

That said, there is a way to make sense of the collection of all sets, even in ZFC. Such an object is called a class. So we can talk about the class of all sets, but not the set of all sets. However, I have already said that everything in mathematics is a set. But a class isn't a set. So a class isn't really part of the mathematics, but more of the language we use to talk about mathematics. It is useful to pretend that it is an actual object though.
In fact, it is that useful that there is another very popular set theory, called NBG, which allows both sets and classes to formally exist. So if we accept NBG, then we can say that everything in mathematics is either a set or a class.

I know you will probably not understand everything I said here. You should come back to this after you have are more comfortable with sets and proofs. It's very interesting material, so I couldn't really hold myself back of posting it. Don't worry about it now if you don't get it.

 

[Fredrik]

There's a typo there, you should have talked about $\{x~\vert ~x\notin x\}$, as I'm sure you know.

Thanks. I have edited that now.

Basically, you've proved it yourself now that the set of all sets do not exist. Why? It is an axiom that if $A$ is a set and if $P$ is some property, then
\{x\in A~\vert~P\}
is a set. Now, if the set of all set existed, then we can define this set as $A$. We can also define the property $P$ as $x\notin x$. So if the set of all sets existed, then also
\{x\in A~\vert~x\notin x\}
exists. But this would yield the Russell paradox as shown in the quote.

Of course. I should have thought of that. I had a feeling that the proof you have posted before was a bit trickier, so I didn't really think. I probably just remembered that wrong.

 

[CompuChip]

There's a typo there, you should have talked about $\{x~\vert ~x\notin x\}$, as I'm sure you know.

That's probably partly my fault, I am also missing a "not" in the post above where I wrote this out in words. Unfortunately I cannot edit that one anymore.

 

[Fredrik]

That's probably partly my fault, I am also missing a "not" in the post above where I wrote this out in words.

It's not your fault. I managed to type that wrong all by myself.

 

[reenmachine]

Now I'm having a problem , the next paragraph about relations in my textbook is suppose to have a picture in it but it's not there.I searched the web with the name of the picture and it doesn't exist.

Should I copy-pasta the textbook anyway and try to deal with this with you guys?

The problem is I think the whole page about relation is based on that missing picture.

 

[Fredrik]

If it's from "the book of proof", just post the link to the online version and tell us the page number in the online version. If you don't see a way to show us the image, tell us what book and page number you're talking about. You can copy and paste some of the text if you think that may be sufficient.

 

[reenmachine]

We may visually represent a relation R between two sets A and B by arrows in a diagram displaying the members of both sets. In Figure 2-1 in PtMW [Partee, ter Meulen,and Wall], A= {a.b}, B= {c,d,e}, and the arrows represent a set-theoretic relation R = {<a,d>,<a,e>,<b,c>}. [see Fig 2-1, p. 29.]

I don't understand how the picture is supposed to look like.I also don't get why the R = {<a,d>,<a,e>,<b,c>} if A= {a.b}, B= {c,d,e}.Or is it just random?

Let us consider some operations on relations.The complement of a relation R ⊆ A×B is defined as:

R’ = def(A×B) –R.

Why ''def'' ?

Note that what the complement of a relation is depends on what universe we are considering. A given relation may certainly be a subset of more than one Cartesian product, and its complement will differ according to what Cartesian product we are taking to be the relevant universe.

What is the complement of the relation R = {<a,d>,<a,e>,<b,c>} on the universe {a,b} × {c,d,e}? (Answer: R’ = {<a,c>, <b,d>, <b,e>}.)

So the complement of X in a specific universe is X'.But what happens if it's not clear which universe we are talking about? (or is this not supposed to happen?)

Also what is R' if A = {1,2} and B = {1,2,3} , A × B and R = {<1,1>,<1,2>,<2,2>}.Is it R' = {<1,3>,<2,3>,<2,1>} ?

 

[reenmachine]

If it's from "the book of proof", just post the link to the online version and tell us the page number in the online version. If you don't see a way to show us the image, tell us what book and page number you're talking about. You can copy and paste some of the text if you think that may be sufficient.

No , I'm still waiting for my books unfortunately.Hoped I could have them for the week-end but apparently they're slow as hell to deliver it to my address.

This is from the mini-textbook again.The image just doesn't exist , I can't even see it.I know it's suppose to be there because they mention it.

(see post above)

 

[Fredrik]

First a reminder for everyone else. We're talking about this pdf: http://people.umass.edu/partee/NZ_2006/Set Theory Basics.pdf

I don't understand how the picture is supposed to look like.I also don't get why the R = {<a,d>,<a,e>,<b,c>} if A= {a.b}, B= {c,d,e}.

A binary relation from A into B is by definition a subset of A×B. That R is a subset of A×B.

The image is a Venn diagram showing the sets A and B drawn as disjoint ellipses. a,b are drawn as two points inside A. c,d,e are drawn as points inside B. They have drawn three arrows: From a to d, from a to e, and from b to c.

The document says that the image is on page 29 of the book "Mathematical methods in Linguistics". (See the PM I sent you on April 4).

Why ''def'' ?

Some authors prefer to use a different symbol instead of = when they define something. Here they use $=_{def}$.

So the complement of X in a specific universe is X'.But what happens if it's not clear which universe we are talking about?

It usually is. If it's not, then you have to write something like U-X instead of X' or X^c.

Also what is R' if A = {1,2} and B = {1,2,3} , A × B and R = {<1,1>,<1,2>,<2,2>}.Is it R' = {<1,3>,<2,3>,<2,1>} ?

Yes.

I have to go, so I don't have time to check for typos or if what I said made sense.

 

[micromass]

I don't understand how the picture is supposed to look like.I also don't get why the R = {<a,d>,<a,e>,<b,c>} if A= {a.b}, B= {c,d,e}.Or is it just random?

The picture you want looks like this

In your case, you should have elements {a,b} on the left side and {c,d,e} on the right side. You have an arrow going from a to d, from a to e and from b to c.

 

[micromass]

So the complement of X in a specific universe is X'.But what happens if it's not clear which universe we are talking about? (or is this not supposed to happen?)

The universe here is $A\times B$. The book should probably have mentioned it.

Also what is R' if A = {1,2} and B = {1,2,3} , A × B and R = {<1,1>,<1,2>,<2,2>}.Is it R' = {<1,3>,<2,3>,<2,1>} ?

That is correct. It might be a good practice to draw those relations in a diagram.

 

[reenmachine]

The inverse of a relation R ⊆ A × B is defined as the relation R-1 ⊆ B × A , R–1=def{<b,a><a,b> ∈ R}. Note that (R–1)-1=R.

They define R-1 by the bolded part.Do they justify <b,a> being R-1 by stating that <a,b> ∈ R? If that's the case , if ,

A = {1,2} and B = {2,3} , isn't <2,2> both ∈ R and ∈ R-1 ?

More examples:
Let N be the set of natural numbers, {0, 1, 2, 3, 4, ... }

Let R be “is less than” on N(i.e., on N × N)

Then what is R’?

R' = ''≥ than'' on N (i.e., on N × N)

?

What is R -1?

R -1 = ''> than'' on N (i.e., on N × N)

?