Define a relation on A=Z by n~m iff n-m=3k where kEZ

[StephenPrivitera]

What is a relation? My book says
If A is a set, then R[subset] A x A is called a relation on A. Does this mean R[subset]A² or R, a subset of A, multiplied by A?
Then the book talks about ordering. And for partial orderings it uses the notation a[<=]b rather than a~b. Does this mean less than or equal to, or is it just another notation to mean related to? If it is the former, it seems silly to me that a linear ordering is a partial ordering with the additional property that if (a,b)E R, then a[<=]b or b[<=]a because one of those two statements must be true (if not both)!
Then the book says A=R with ordinary ordering is a linear ordering. This is nonsense, because we're talking about relations. Wouldn't we have to say A[subset]R^2 before we can talk about ordering?
As an example, the book gives, Define a relation on A=Z by n~m iff n-m=3k where kEZ. All I can say is if R[subset]Z^2, R can be defined by all points (n,m) such that mEZ and n=3k +m, where kEZ, but that seems rather simplistic, and I used no math to show that result.
Someone please help me!

 

[HallsofIvy]

For A and B sets, AxB is the "Cartesian product", the collection of all pairs where the first member is from A and the second is from B.
(I'll bet that's in your book.) It's not actually necessary that a "relation" be a subset of AxA. For example, if we take A to be "set of men", B to be "set of women" then the relation "a is married to b" is a subset of AxB.

An order (or partial order) is a special kind of relation that satisfies the condition "if a~b and b~c, then a~c" (the transitive property). It isn't necessarily "less than" but that's the key example. Another important example is: A is the collection of all sets and X<= Y means "X is a subset of Y".

 

[StephenPrivitera]

So a relation is any subset of a Cartesian product?

Say A has an equivalence relation. Does this mean that some subset of AxA has equivalence properties?

Does the symbol "~" represent the operation that relates a with b? For example, might a~b signify a=3b or a>b²?

 

[HallsofIvy]

1. Yes, any subset of AxA is, by definition, a relation on A. Any subset of AxB is a relation between A and B.


2. I'm not sure what you mean. An equivalence relation on a set A IS a subset of AxA such that a) (a,a) is in the subset for all a in A.
b) If (a,b) is in the set then (b,a) is also. c) If (a,b) and (b,c) are in the set then so is (a,c).
If that's what you mean by "equivalence properties", then, yes, the definition of "equivalence on A" is that the equivalence relation is a subset of AxA with those properties.

3. Yes, "~" is a standard notation for a general relation. If "a is related to b" (that is, if (a,b) is in the subset of AxB that defines the relation) then we may write a~b. You will also sometimes see "aRb" to mean "a is related to b".

 

[StephenPrivitera]

Yes, that's what I meant by equivalence properties. That helps clear things up, but could you give me a concrete example of a relation?
Let me show you an example from the book. Tell me what you think.
Define an equivalence relation on A=Z by n~m iff n-m is a multiple of 3. What are the equivalence classes?
I'm looking for S, where S[subset]Z².
n-m=3k
k is an element of Z
n=3k+m
S={(3k+m,m)}
so when k=0, we have the element (m,m) [property a]
if n=3k+m, then n~m
and m~n since
m-n=-3k=3k [property b]
If n~m and m~p, then n~p since
n-m=3k₁ and m-p=3k₂
n-3k₁-p=3k₂
n-p=3(k₁+k₂)=3k [property c]

From the book, we have, "If ~ is an equivalence relation on A, and a is an element of A,then cl(a)={xEA : a~x}"

So, I ask, in the example above, what is the relation ~? Is it n=3k+m? Then would cl(a)={xES : a=3k+x}? I don't even know what that means anyway. I just wrote it. Maybe, the equivalence class containing a is the set of all elements which are related to a. Can I be more specific than that for answering the second part of the example? Feel free to elaborate on equivalence classes, or anything else for that matter.

 

[HallsofIvy]

So, I ask, in the example above, what is the relation ~? Is it n=3k+m?

No, you already have defined a relation as a "set of ordered pairs" so the relation ~ is NOT an equation. In this case we can't actually write out all the pairs- there are an infinite number. I can show you a few of them: (3,6), (5,8), (4,16)- since 6-3= 3, 8-5= 3, 16-4= 12 are all divisible by 3. (3,5), (5,10) are examples of pairs that are NOT in the set.

I'm looking for S, where S subset Z².

No, the problem asked for "equivalance classes". The relation itself is a subset of Z² but as the definition you give says: "If ~ is an equivalence relation on A, and a is an element of A,then cl(a)={xEA : a~x}"- cl(a), the equivalence class that contains a, is a subset of A.

A crucial point about equivalence relations on a set is that they "partition" the set: every member of the set is in exactly one equivalence class. The simplest way to find equivalence classes is to pick an arbitrary member of A and start looking for other members that are equivalent.

In this case, A is the set of integers so let's start with 0.
What numbers are equivalent to 0? "a~b" means a-b is a multiple of 3 so a~0 means a-0= a is a multiple of 3: cl(0) is all multiples of 3: {3, -3, 6, -6, 9, -9,...}. We can write the set as {3k|k in Z}.

1 is not in that set. What numbers are equivalent to 1? Again, that means numbers n such that n-1 is a multiple of 3: n-1= 3k or
n= 3k+1. 1, 4, 7, ..., -2, -5, ... We can write this set as
{3k+1| k in Z}.

What about 2? Now we need n-2= 3k or n= 3k+ 2: numbers like 2, 5, 8, ... -1, -4,... are equivalent to 2 and so in the equivalence class. We can write this set as {3k+ 2| k in Z}.

We don't have to ask about 3 or 4 or negative numbers because those are already in the sets above (and the symmetric and transitive rules tell us that if a number a is in SOME equivalence class, then that is ITS equivalence class).

The relation "a~ b means a-b is divisible by 3" partitions the set of all integers into those three equivalence classes.

 

[HallsofIvy]

Here's a non-numerical example: ~ is defined on the set of people as: a~ b if and only if a is the same gender as b.

This is an equivalence relation because it satisfies the three requirements for an equivalence relation:
a) Reflexive: each person is the same gender as him/herself.

b) Symmetric: if a is the same gender as b, then b is the same gender as a.

c) Transitive: if a is the same gender as b and b is the same gender as c, then a is the same gender as c.

(Actually, these are due to the fact that "same" is basicaly the verbal idea of "equivalent".)

There being two genders, this partitions the set of all people into two equivalence classes. The equivalence classes are the set of all females and the set of all males.

The "equivalence relation" itself as a set of pairs would include all pairs in which both people are female or both people are male but none in which one is male and the other female.