Reflexive and Anti-symmetric

Using the abstract definition of relation among elements of set A as any subset of AXA (AXA: all ordered pairs of elements of A), give a relation among {1,2,3} that is antisymmetric other than {(1,1), (2,2, (3,3).

The standard non-strict order.

Quote:

---

Originally Posted by emakarov

The standard non-strict order.

---

This would include, for example, (1,2) and (2,1). How does this imply 1=2 (the requirement for anti-symmetric)?

It is not true that 1 ≤ 2 and 2 ≤ 1 in the standard order.

Quote:

---

Originally Posted by emakarov

It is not true that 1 ≤ 2 and 2 ≤ 1 in the standard order.

---

< and = are irrelative to the abstract definition of relation, but I see your point- for example, the relation (1,2) is not anti-symmetric by your judgement.

However, wliki defines antisymmetry as: If R(a,b) and R(b,a) then a=b.

So in order to judge R as anti-symmetric, R(a,b) and R(b,a) must both be present. So you can't call (1,2) (or the strict order) anti-symmetric because (a,b) and (b,a) are not both present to make the judgement.

Thanks for your challenging and informative response.

Quote:

---

Originally Posted by Hartlw

< and = are irrelative to the abstract definition of relation, but I see your point- for example, the relation (1,2) is not anti-symmetric by your judgement.

However, wliki defines antisymmetry as: If R(a,b) and R(b,a) then a=b.

So in order to judge R as anti-symmetric, R(a,b) and R(b,a) must both be present. So you can't call (1,2) (or the strict order) anti-symmetric because (a,b) and (b,a) are not both present to make the judgement.

Thanks for your challenging and informative response.

---

huh?

[R(a,b) & R(b,a)] → (a = b) is logically equivalent to (this equivalence is known as "equivalence of the contrapositive to the implication"):

(a ≠ b) → ¬[R(a,b) & R(b,a)] which is equivalent to (by DeMorgan's laws):

(a ≠ b) → ([¬R(a,b)] v [¬R(b,a)])

which says that if a and b are unequal, only ONE of the pairs (a,b) and (b,a) will be in R, at MOST (it might be that neither one is, a and b might be "incomparable").

here is a SECOND relation R that is anti-symmetric and reflexive on {1,2,3}:

R = {(1,1),(1,2),(1,3),(2,2),(3,3)}, how do we normally express this relation?

Please stick to subject and definitions.
Your example R is reflexive but not anti-symmetric. You can't judge it to be anti-symmetric unless (a,b) and (b,a) are both present.

Is ($,%,#,!) in alphabetical order? You can't judge it to be in alphabetical order unless letters are present. The absence of letters does not mean it is in alphabetical order, except in a very silly sense: it is not not in alphabetical order therefore it is in alphabetical order. Is the null set in alphabetical order because it is not not in alphabetical order?

EDIT: reflexive is necessary for anti-symmetric but not sufficient for {1,2,3} because the only relation that is reflexive and anti-symmetric is {(1,1),(2,2),(3,3)}. {(1,1),(2,2),(3,3),(1,2)} is reflexive but not anti-symmetric.

CORRECTION to EDIT {(1,1),(1,2)} is anti-symmetric but not reflexive: (a,b) and (b,a) are present and a=b=1

Quote:

---

Originally Posted by Hartlw

Your example R is reflexive but not anti-symmetric. You can't judge it to be anti-symmetric unless (a,b) and (b,a) are both present.

---

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.)

I think Devano's post was correct and quite relevant on this point. As was emakarov's example.

-Dan

you seem to feel that for an assertion "x implies y" to be true, we must actually have some x's to "test it". this is not the case, google "vacuous truth".

the assertion aRb & bRa → a = b only tells us when we can conclude a = b. if (a,b) or (b,a) is not in R, it might be that a = b, or it might not. we can't tell.

for example the relation R on the integers defined by aRb if a < b is anti-symmetric, but not reflexive. so neither (2,1) nor (2,2) is in R, but we cannot conclude just from "non-membership" in R that the second coordinate isn't equal to the first. both can happen.

i know what an anti-symmetric relation is. i don't believe you do.

Let me simplify my question:
Based on the following definitions:

A) Relation R: Subset of AXA (Plato)
B) Antisymmetric Relation: If R(a,b) and R(b,a), then a=b (wiki)

Are the following relations antisymmetric:

1) {(1.2), (2,1)}
2) {(1,2), (1,3)}
3) {(1,1), (1,2)}

1) No. 2) Yes. 3) Yes.

Quote:

---

Originally Posted by emakarov

1) No. 2) Yes. 3) Yes.

---

Thanks for your reply.

I would answer 1) No. 2) No. 3) Yes, on the basis that for "if A then B" to be true A has to exist.

I forgot to add,

4) {(2,2)}.

Presumably we would agree that this is "Yes."

EDIT: Deveno wrote: " the assertion aRb & bRa → a = b only tells us when we can conclude a = b. if (a,b) or (b,a) is not in R, it might be that a = b, or it might not. we can't tell." If we can't tell we can't conclude that it is anti-symmetric.

PS: I couldn't find a definition of standard non-strict order. A simple set of number pairs would have sufficed to answer my original question, and avoided a lot of subsequent discussion. I guess this is partially my fault. In retrospect, the essence of the discussion is: Is {(1,2)} anti-symmetric? (easy for mathemiticians), but why?

yes R = {(1,2)} is anti-symmetric on the set {1,2} (it is important to specify the underlying set the relation is on). why? because (2,1) is NOT in R.

symmetric and anti-symmetric have a geometric interpretation:

one can view a set SxS as a plane, of sorts (especially if S is a subset of a field). the diagonal of S is the subset of SxS that lies on the "diagonal line" s₂ = s₁.

a symmetric relation is one that if it includes a point (a,b) also includes its "reflection across the diagonal".

an anti-symmetric relation is one that includes only one of a "reflection-pair" {(a,b),(b,a)} (if a = b there is only one element in this set, anyway).

some "typical" anti-symmetric relations (ones the "general idea" is modeled on, or abstracted from):

a,b belong to some (subset) of an ordered field (like the real numbers), and R = ≤

a,b are natural numbers and R = | (that is: aRb means a divides b).

A,B are elements of a power set, P(S), and R = ⊆.

an anti-symmetric relation need not induce a dichotomy: it need not be that case that one of aRb, bRa hold (a total non-strict order will).

for example, with R = divisibility, and S = N, the natural numbers, we do not have 4 divides 6 OR 6 divides 4. but we DO have: if a|b and b|a, then a = b.

or: for R = ⊆, we cannot say that {a,c} ⊆ {b,c} or vice versa, but we CAN say if A ⊆ B and B ⊆ A, then A and B are the same set.

usually, the anti-symmetric relations of most interest to mathematicians are those which are reflexive AND transitive, which form partial orders (these are very different from their symmetric counter-parts, the equivalences).

Quote:

---

Originally Posted by Hartlw

Are the following relations antisymmetric:

1) {(1.2), (2,1)}
2) {(1,2), (1,3)}
3) {(1,1), (1,2)}

---

Quote:

---

Originally Posted by Hartlw

I would answer 1) No. 2) No. 3) Yes, on the basis that for "if A then B" to be true A has to exist.

---

One cannot say "A exists" when A is a proposition. A proposition can be either true or false. And an implication "if A then B" can be true even if A is false. In fact, in this case the implication is true regardless of whether B is true. Recall that "if A, then B" is true iff A is false or B is true; this means the implication is false iff A is true and B is false.

Why is {(1,2), (1,3)} antisymmetric? We need to check "For all a, b, if R(a, b) and R(b, a), then a = b." Let's substitute all possible pairs of a and b. For example if a = 1 and b = 1, then both R(a, b) and R(b, a) are false, so "R(a, b) and R(b, a)" is false. Therefore, the implication is automatically true. If a = 1 and b = 2, then R(a, b) is true, but R(b, a) is false, so "R(a, b) and R(b, a)" is again false.In fact, you can't find a single pair (a, b) such that "R(a, b) and R(b, a)" is true. This means that the implication "if R(a, b) and R(b, a), then a = b" is true solely because the premise is always false. Therefore, the relation is antisymmetric.

Quote:

---

Originally Posted by Hartlw

PS: I couldn't find a definition of standard non-strict order.

---

A strict order is irreflexive while a non-strict order is reflexive, i.e., it contains the equality relation. The standard strict order on reals and its subclasses is <, and the standard non-strict order is <=.

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.