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

Printable View

- Nov 8th 2012, 06:07 AMHartlwReflexive 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).__ - Nov 8th 2012, 06:46 AMemakarovRe: Reflexive and Anti-symmetric
The standard non-strict order.

- Nov 8th 2012, 07:12 AMHartlwRe: Reflexive and Anti-symmetric
- Nov 8th 2012, 07:16 AMemakarovRe: Reflexive and Anti-symmetric
It is not true that 1 ≤ 2 and 2 ≤ 1 in the standard order.

- Nov 8th 2012, 07:58 AMHartlwRe: Reflexive and Anti-symmetric
< 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. - Nov 8th 2012, 08:15 AMDevenoRe: Reflexive and Anti-symmetric
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? - Nov 8th 2012, 08:28 AMHartlwRe: Reflexive and Anti-symmetric
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 - Nov 8th 2012, 09:29 AMtopsquarkRe: Reflexive and Anti-symmetric
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 - Nov 8th 2012, 09:37 AMDevenoRe: Reflexive and Anti-symmetric
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. - Nov 8th 2012, 05:05 PMHartlwRe: Reflexive and Anti-symmetric
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)} - Nov 8th 2012, 10:45 PMemakarovRe: Reflexive and Anti-symmetric
1) No. 2) Yes. 3) Yes.

- Nov 9th 2012, 08:10 AMHartlwRe: Reflexive and Anti-symmetric
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? - Nov 9th 2012, 10:16 AMDevenoRe: Reflexive and Anti-symmetric
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_{2}= s_{1}.

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). - Nov 9th 2012, 11:12 AMemakarovRe: Reflexive and Anti-symmetric
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.

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 <=. - Nov 9th 2012, 11:28 AMHartlwRe: Reflexive and Anti-symmetric
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.