Thread: Reflexive and Anti-symmetric

Originally Posted by Hartlw

Thanks Deveno:
If R is divisibility, only 2|4 belongs to R, not 4|2, in which case R is not anti-symmetric in my opinion based on:

“If A implies B, then C” requires A for C.

In which case, R is anti-symmetric iff it is reflexive, because, by def,
if aRb and bRa implies a=b, then reflexive, in my opinion.


Thanks Emakorov:
You are taking this into the realm of semantics and logic. I don’t think that fast. If that is what is required to understand the definition of anti-symmetric, then either the necessary logic, or reference to it, should be included in the definition. There is , of course, the possibility that I am the only one that does not understand the definitiion, in which case I can safeley be ignored. But note, I can only be safeley ignored if "I am the only one that does not understand the definitiion" is true, ie, exists.

I really should take this to “Math Forum” before I get canned. I’ll have to gather my thoughts first.

well, no that's not true. an anti-symmetric relation need not be reflexive. we need not have ANY elements of the diagonal in R. in fact, we need not have any elements in R at all! (the "empty relation" which consists of the empty subset of SxS, is anti-symmetric).

your opinion that to say we must have both (a,b) in R AND (b,a) in R in order to conclude something about the "relationship" between a and b is simply not true.

for example, let S = N, the natural numbers, with R = <: that is: aRb if and only if a < b.

well, 3 < 4, so (3,4) is an element of R. however, (4,3) is NOT in R, because 4 is NOT less than 3.

let's look more closely at statements of the form:

If A implies B, then C.

here is one statement of such a form:

"If rain falling on my car makes it wet, I shall wash it".

here: A = rain falls on my car, B = my car gets wet, C = I shall wash my car.

now given A, and given A implies B, we may conclude C.

but: this is not the ONLY circumstance under which C occurs: one might decide to wash their car just for the "heck of it", even if it has not rained.

also, it may be that "A implies B" is FALSE (perhaps the car is parked inside a garage when it rains), and yet the car is still washed at some point.

so we do NOT require A for C, or even A implies B, these are sufficient but not NECESSARY.

people often struggle with implication:

a statement like "P implies Q" in many people's minds means: we need to know P is true in order to know Q is true (we often use it this way in casual conversation).

but this is NOT what it means in mathematics: it means IF P is true, THEN Q is true (and if P is not true, we can't tell just from this information if Q is or isn't true).

a simple example:

if an integer is divisible by 4, it is an even number (divisible by 2).

this is a true statement.

but 6 is not divisible by 4, and yet 6 is nevertheless even, and

3 is not divisible by 4, and is NOT even.

so just because a number is not divisible by 4 (the premise is false), we cannot conclude that the consequence is true or false (it can go either way).

of course, statements like: "if the sky is green, then i'm a monkey's uncle" while "logically" true, are rather nonsensical: mathematical linguistics and natural language linguistics are not a perfect match. in mathematics "if...then", "and" and "or" have "special" meanings which are not quite the same as our everyday usage of them.

f is anti-symmetric if f(-x) = -f(x). If f(-x) doesn’t exist, is f anti-symmetric?

now, that is a distinct (different) use of the word "anti-symmetric", the more usual term in the case of functions is "odd function".

so your question is (for example): can we call a function "odd" if it is only defined on either non-negative, or non-positive real numbers?

for example, we might consider f(x) = √x. we can't say if it's odd or even, unless we are more careful about defining our terms.

this is a different situation than a binary relation R on a set S.

all we are saying is that IF aRb AND bRa, then a = b. possible things that could happen:

1. aRb but not bRa.
2. not aRb but bRa.
3. both aRb and bRa (in this case, we know a = b)
4. neither aRb nor bRa.

cases 1,2 and 4 don't tell us much about a and b, because we need reflexivity to deduce a ≠ b from 1,2 & 4. for example, suppose R is the relation on the set {1,2,3,4} given by:

{(1,2)}. more concretely, R might be the relation "is the son of", and S = {John Jr., John, Mary, Alice} where Alice and Mary are John Jr.'s sisters.

R in this case is anti-symmetric, "by default" because the situation aRb and bRa NEVER OCCURS.

we aren't required, by the definition of a relation R on S (a subset of SxS) to have aR(something) for every a.

the relation on the natural numbers aRb only if a is a factor of b is a perfectly good relation: given any two natural numbers a and b, we can decide if aRb or not:

if b = qa + 0, then yes (here, and below, q ≥ 0)
if b = qa + r, with 0 < r < a, then no (this happens, for example, when b < a, because we can use q = 0, and r = b).

so (3,6) is in R, but (4,6) is not (and neither is (6,3) or (6,4)).

if we restrict ourselves to the subset of the natural numbers S = {1,2,3,4,5,6} we have:

R = {(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,2),(2,4),( 2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}

this is *A* subset of SxS, so it's a perfectly good relation.

is this R anti-symmetric?

suppose aRb and bRa.

so b = qa, and a = q'b.

thus b = q(q'b) = (qq')b.

since b is in {1,2,3,4,5,6}, b ≠ 0, so we can cancel the b's:

1 = qq' since q and q' are non-negative integers, we must have q = q' = 1, so b = a.

but one can see BY INSPECTION R is anti-symmetric:

the only "off-diagonal elements" are:

(1,2),(1,3),(1,4),(1,5),(1,6),
(2,4),(2,6),
(3,6)

is (2,1) in R? no.
is (3,1) in R? no.
is (4,1) in R? no.
is (5,1) in R? no.
is (6,1) in R? no.
is (4,2) in R? no.
is (6,2) in R? no.
is (6,3) in R? no.

so the only time we get an "symmetric pair" (a,b) and (b,a) in R, are those times when a = b.

you're missing something fundamental, here. i'm not exactly sure what it is. i suspect it's related to a misapprehension of logic, you feel that a true conclusion can only be drawn from a true premise, but this just isn't so in mathematical logic.

Originally Posted by Hartlw

f is anti-symmetric if f(-x) = -f(x). If f(-x) doesn’t exist, is f anti-symmetric?

And all I'm saying is that you can't conclude that a condition is true if the condition doesn't exist.

"all we are saying is that IF aRb AND bRa, then a = b. possible things that could happen:"
That is what you are saying. The definition says if aRb AND bRa lmplies a=b, R is anti-symmetric. And what I am saying is that you can't conclude a condition exists unless the test condition exists, and the test condition is "if aRb AND bRa lmplies a=b."

Any other combination of aRb and bRa doesn't allow a determination of anti-symmetric.

EDIT: Would you agree that if "something" is true if a condition is true, and that if the condition doesn't exist you can't conclude "something" is true?

Every member of Φ is also a member of A → Φ < A is vacuously true.
Every member of Φ is also a member of A → the world is flat is vacuously true.

EDIT: I note Kelly gives the definitions:
R is Symmetric if aRb whenevr bRa.
R is Anti-Symmetric iff it is never the case that aRb and bRa.

Even I can understand that. But I notice the modern mathematician doesn't like simple explanations. Job Security?

Originally Posted by Hartlw

R is Anti-Symmetric iff it is never the case that aRb and bRa.

This is a non-standard definition. It would be standard if it said, "R is Anti-Symmetric iff it is never the case that aRb and bRa for distinct a and b."

What are you opposing? If you don't agree with some claims made in this thread, make your own claims. But make them formally and precisely, with minimum English and using universally accepted notation. (For example, I don't know what "Φ < A" means.) Then it would be easy to see if they are correct.

It seems pretty obvious that a unequal to b, but if you need the extra clarification, by all means use it.

Can you refer to a definition of anti-symmetry where a unequal b is specifically spelled out? I haven't seen any.

Sorry, I used < than because I didn't know how to get the symbol for subset- I would have thought it was obvious..

"Vacuous" has been used throughout the thread as a justification for the interpretation of "R is anti-symmetric iff aRb and bRa -> a = b." Obviously the premise starts out with the assumption that a unequal b.

Every member of Φ is also a member of A → Φ < A is vacuously true. (< means subset)
Every member of Φ is also a member of A → the world is flat is vacuously true.

Originally Posted by Hartlw

It seems pretty obvious that a unequal to b, but if you need the extra clarification, by all means use it.

I think this clarification is necessary. Read Plato's story in this post.

Originally Posted by Hartlw

Can you refer to a definition of anti-symmetry where a unequal b is specifically spelled out? I haven't seen any.

I can't give a source with literally this definition, but I know the standard definition up to equivalence. For example, I know that is not equivalent to the definition of an antisymmetric relation, for example, in Wikipedia, but is equivalent to it (it's the contrapositive of that definition).

Originally Posted by Hartlw

"Vacuous" has been used throughout the thread as a justification for the interpretation of "R is anti-symmetric iff aRb and bRa -> a = b." Obviously the premise starts out with the assumption that a unequal b.

In this definition, it is not necessary to start the assumption with a not equal to b.

Originally Posted by Hartlw

Every member of Φ is also a member of A → Φ < A is vacuously true. (< means subset)
Every member of Φ is also a member of A → the world is flat is vacuously true.

By Φ, do you mean the empty set? "Every member of the empty set is also an element of A" is indeed true, and "the world is flat" is false (if "the world" means "the Earth" at least), so the implication of these two propositions is false.

So, what precisely is the statement that you disagree with?

You are right, the earth is not flat, and that is the whole point, the vacuous proof can't be used as a proof- in my opinion based on the example: Every member of Φ is also a member of A → the earth is flat is vacuously true.

On the definition of Kelly for anti-symmetric, I agree with you:
As given, Kelly would say {(1,2)} is anti-symmetric but not {(1,1), (1,2)}.
The original Wiki definition, and it looks like your definition is saying the same thing, supposedly would say {(1,2)} is anti-symmetric and {(1,1),(1,2)} is anti-symmetric.

My objection to the Wiki definition was that if for all aRb belonging to R aRb and bRa implied a=b, then R was antisymmetric, the judgement could only be made if both aRb and bRa existed simultaneously in which case R could only be anti-symmetric if it were reflexive. The vacuous argument was used by others to contradict this conclusion, and that's why I showed that the vacuous argument could not be used as a proof.

Originally Posted by Hartlw

You are right, the earth is not flat, and that is the whole point, the vacuous proof can't be used as a proof- in my opinion based on the example: Every member of Φ is also a member of A → the earth is flat is vacuously true.

If by Φ you mean the empty set and by → you mean "implies," then "Every member of Φ is also a member of A → the earth is flat" is false.

Originally Posted by Hartlw

On the definition of Kelly for anti-symmetric, I agree with you:
As given, Kelly would say {(1,2)} is anti-symmetric but not {(1,1), (1,2)}.

{(1,1), (1,2)} is antisymmetric according to the conventional definition. This is why one can't omit the premise from Kelly's definition.

Originally Posted by Hartlw

The original Wiki definition, and it looks like your definition is saying the same thing, supposedly would say {(1,2)} is anti-symmetric and {(1,1),(1,2)} is anti-symmetric.

That's correct.

Originally Posted by Hartlw

My objection to the Wiki definition was that if for all aRb belonging to R aRb and bRa implied a=b, then R was antisymmetric

This is not the correct definition. The correct definition starts with "For all a, b" and not "For all aRb belonging to R."

Originally Posted by Hartlw

the judgement could only be made if both aRb and bRa existed simultaneously in which case R could only be anti-symmetric if it were reflexive.

One can't say that aRb "exists," only that it is true or false. Which judgment: that R is antisymmetric? Then which a and b exactly are meant in this case?

Originally Posted by Hartlw

The vacuous argument was used by others to contradict this conclusion, and that's why I showed that the vacuous argument could not be used as a proof.

What exactly is the vacuous argument?

In any case, we need something more precise to work with. I suggest the following statement. "Let R = {(1,1), (1,2)}.The for all a, b in {1, 2}, aRb and bRa imply a = b." This statement is equivalent to the conjunction of 4 statements:

(1) If 1R1 and 1R1, then 1 = 1
(2) If 1R2 and 2R1, then 1 = 2
(3) If 2R1 and 1R2, then 2 = 1
(4) If 2R2 and 2R2, then 2 = 2

Writing T for true and F for false, we have 1R1 is T, 1R2 is T, 2R1 is F and 2R2 is F. Therefore, (1)-(4) can be rewritten as

(1) If T and T, then T
(2) If T and F, then F
(3) If F and T, then F
(4) If F and F, then T

Now, T and T is T, T and F is F, F and T is F, F and F is F. So we get

(1) If T, then T
(2) If F, then F
(3) If F, then F
(4) If F, then T

By the definition of implication, all of (1)-(4) are true.

Def: aRb is True if it is a member of R. aRb is False if it is not a member of R.

Def: R is anti-symmetric iff, for all a,b belonging to R, the logical implication A→B is true, where A = (aRb and bRa) and B = (a=b).

A B A→B
T T T aRb and bRa and a=b
T F F
F T T aRb and a=b
F F T

R is anti-symmetric iff it is reflexive.

that is NOT the definition of anti-symmetric. for one thing, a and b are not elements of R, R consists of elements of a set SxS. the underlying set (S) is important. a and b are elements of S.

a logical implication is true when:

the premise is false, OR

the premise AND the conclusion are true.

possible scenarios:

1. aRb = T, bRa = T
2. aRb = T, bRa = F
3. aRb = F, bRa = F
4. aRb = F, bRa = F

of these 4 possibilities the conjunction (aRb)&(bRa) is only true in case (1). therefore, this is the ONLY case in which whether or not a = b MATTERS.

in this ONE possibility, for the statement: "R is anti-symmetric" to be TRUE, we MUST have a = b. if ONLY one of aRb or bRa is true, we "just don't know" if a = b or a ≠ b (neither conclusion invalidates the implication). more importantly if NEITHER aRb NOR bRa is true, we ALSO do not know if a = b or a ≠ b.

the thing is, we may not know a priori if a = b or not. with elements like numbers, this is rather obvious. but a and b might be ratios (for example). i submit that it is not obvious at first glance that:

2/3 = 702/1053

more complicated examples with rational functions can be devised (it isn't always obvious, for example, that two polynomials share a common factor).

but let's say we can tell "at once" whether or not a = b. we can split our first criteria into 2 cases each:

1a) aRb = T, bRa = T and a = b
1b) aRb = T, bRa = T and a ≠ b
2a) aRb = T, bRa = F and a = b
2b) aRb = T, bRa = F and a ≠ b
3a) aRb = F, bRa = T and a = b
3b) aRb = F, bRa = T and a ≠ b
4a) aRb = F, bRa = F and a = b
4b) aRb = F, bRa = F and a ≠ b.

we can see that case (2a) and (3a) are impossible:

for (2a): aRb = T and bRa = F and a = b leads to aRa = T and aRa = F, a contradiction. (3a) is similar.

what the definition of anti-symmetric tells us, is that (1b) is also impossible. this gives 5 situations which may occur in an anti-symmetric relation:

(1a) aRb = T, bRa = T and a = b (this is the most "useful" situation)
(2b) aRb = T, bRa = F and a ≠ b
(3b) aRb = F, bRa = T and a ≠ b
(4a) aRb = F, bRa = F and a = b (this tells us that aRa = F, an anti-symmetric relation R NEED NOT BE REFLEXIVE)
(4b) aRb = F, bRa = F and a ≠ b (two elements may be "incomparable" (unrelated) according to R)

look at row 4 of your table: R can be anti-symmetric even if the only pairs (a,b) (aRb = T) satisfy a ≠ b.

Originally Posted by Hartlw

Def: aRb is True if it is a member of R. aRb is False if it is not a member of R.

Def: R is anti-symmetric iff, for all a,b belonging to R, the logical implication A→B is true, where A = (aRb and bRa) and B = (a=b).

A B A→B
T T T aRb and bRa and a=b
T F F
F T T aRb and a=b
F F T

R is anti-symmetric iff it is reflexive.

The definition of R was established in the first post and never questioned. Truth or Falsity of aRb is established in the first definition above. The definition of anti-symmetric (wiki) was established at the very beginning and never questioned throughout the discussion. The definition of implication is the mathematically logical one.

Originally Posted by Hartlw

Def: R is anti-symmetric iff, for all a,b belonging to R, the logical implication A→B is true, where A = (aRb and bRa) and B = (a=b).

Deveno is right: there is a type error. If aRb makes sense, then a and b belong to S but don't belong to R ⊆ S × S, and if a and b belong to R, then a, b ∈ S × S, so aRb does not make sense.

Originally Posted by Hartlw

A B A→B
T T T aRb and bRa and a=b
T F F
F T T aRb and a=b
F F T

R is anti-symmetric iff it is reflexive.

I don't see how this conclusion follows.

Originally Posted by topsquark

I think a more emphatic way to phrase this statement is "If R(a,b) and R(b,a) then we must have a = b." I think this is clearer in the contrapositive: "If R(a,b) but a is not equal to b, then R(b,a) must not hold." (Also from Wiki.)

-Dan

Okay, I'm not keeping up with all the posts here, but the definition of an reflexive and anti-symmetric deals with
R(a, b) but a is not equal to b, then R(b, a) must not hold. So for a = 1 to 3, and b = 1 to 3 an anti-symmetric relation would give (for example)
{(1, 2), (1, 3)}

or
{(1, 1), (1, 2), (2, 2)}

Am I missing something obvious? And if I am right, then why all the fuss? It's merely a definition.

-Dan