Thread: Reflexive and Anti-symmetric

As reference for others who like me may have been unclear about the term "vacuously true" used in the thread:

(If A then B) is vacuously true if hypothesis A is false.
For example: Let E be the empty set and S any set. Then E is a subset of S:
(If x ϵ E then x ϵ S) is vacuously true because x ϵ E is false. (Reference for others who may also have been un)

Note the last 2 lines in the truth table from post #26 are vacuously true:

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.

Found a clear, precise, non-trivial definition of anti-symmetry in Kelly (General Topology), pg 9: “R is anti-symmetric iff it is never the case that both xRy and yRx. “

* parentheses added to clarify. Pointed out by Deveno.

Originally Posted by Hartlw

Found a clear, precise, non-trivial definition of anti-symmetry in Kelly (General Topology), pg 9: “R is anti-symmetric iff it is never the case that both xRy and yRx. “

Umm...Is there an echo in here? Yes, Hartlw. You got it.

-Dan

PS Of course you still have the possibility that xRx.

Originally Posted by topsquark

Umm...Is there an echo in here? Yes, Hartlw. You got it.

Actually, I didn’t “get it.” This is “getting it:”

By definition of antisymmetric from first post, and standard definition (non math-logical) of “If Then” (→), R is antisymmetric if aRb and bRa and a=b.

The notion that one has to regard Truth Function concepts and Truth Tables from mathematical logic in ordinary and mathematical writing would make writing and reading virtually impossible. I caught myself doing it and thought, this is ridiculous. “If-Then “ is a fundamental, primitive, lanquage concept which occurrs repeatedly in any math text with a clear understanding of what it means. (If A then B) is true when A implies B and false when A is true and B is false. It has the force of y=f(x). Getting the same result for “antisymmetric” from a math logic point of view is interesting and forestalls an incomplete or vaque “math logic Proof” of a different conclusion.

Finally, showing that a so-called standard definiton is trivial, at the least, is worthy of note, and doesn’t deserve to get buried.

Originally Posted by Hartlw

Finally, showing that a so-called standard definiton is trivial, at the least, is worthy of note, and doesn’t deserve to get buried.

I had promised myself to stay out of this. But when I saw your posting "Found a clear, precise, non-trivial definition of anti-symmetry in Kelly (General Topology), pg 9: “R is anti-symmetric iff it is never the case that both xRy and yRx. “
I simply did not think that could be correct.
John L Kelley belongs to one of the most important lines of 20th century topology. He was even the chair of mathematics at Berkeley.
So I cannot believe he would have written that, that is totally out of the mainstream, some have said it is even wrong. On that same page Kelley goes on to write that if is anti-symmetric.

But most standard set theory texts (see Charles Pinter) have this theorem:
If is anti-symmetric then .

So I think that you are very unwise to rely on Kelley's definition.

There goes my nice post #33 into oblivion. Sic Transit Gloria.

"On that same page Kelley goes on to write that .... if R is anti-symmetric." That's preciseley why it makes sense. And like a true master, his definition is consumateley understandable. Who says it's wrong.

"But most standard set theory texts (see Charles Pinter) have this theorem:" Based on what (intelligible) definition of anti-symmetry?

EDIT: Just occurred to me that 0 is a subset of what you have in brackets (don't know how to access it from here, and I can't copy the whole formula), ie, Kelly's def is consistent with Pinter's theorem, ie, Pinters Theorem does not prove Kelly wrong.

Originally Posted by Hartlw

"But most standard set theory texts (see Charles Pinter) have this theorem:" Based on what (intelligible) definition of anti-symmetry?

Here is an exact definition of anti-symmetry from Pinter.
is a relation in , then is anti-symmetric if then .

I dare you to find a definition of anti-symmetry equivalent of Kelley's anywhere else.

Originally Posted by Plato

Here is an exact definition of anti-symmetry from Pinter.
is a relation in , then is anti-symmetric if then .

I dare you to find a definition of anti-symmetry equivalent of Kelley's anywhere else.

Your (Pinter's) definition is the same one we have been using throughout this thread, which has conclusiveley been proved trivial, ie, R is reflexive iff R is anti-symmetric, ie, WRONG. See posts 26 & 33.

By the way, Pinters Set Theory (1971) is out of print and only a few very expensive copies are left. Standard?

Originally Posted by Hartlw

Your (Pinter's) definition is the same one we have been using throughout this thread, which has conclusiveley been proved trivial, ie, R is reflexive iff R is anti-symmetric, ie, WRONG. See posts 26 & 33.
By the way, Pinters Set Theory (1971) is out of print and only a few very expensive copies are left. Standard?

The Pinter is out of print. But it is widely referenced in later texts. He did his PhD in Paris with some of the most important figures in set theory. He did not get it wrong.

As for Kelley, on page 9 of General Topology he writes " is anti-symmetric iff it is never the case that both " Had he stopped there, the the Moore tradition of precise language use would have made that a subset of Pinter's definition( the and implies two). However, he did not stop there. The very next sentence is "In other words, is anti-symmetric iff is void".

Once again here is a standard example.
Let and define . Now using the standard definition is anti-symetric, BUT . So Kelley's is not standard or even a subset of the standard.

Originally Posted by Hartlw

Your (Pinter's) definition is the same one we have been using throughout this thread, which has conclusiveley been proved trivial, ie, R is reflexive iff R is anti-symmetric, ie, WRONG. See posts 26 & 33.

By the way, Pinters Set Theory (1971) is out of print and only a few very expensive copies are left. Standard?

from: http://www.cse.unl.edu/~choueiry/S06...outNoNotes.pdf





.

i urge you to read some of his comments. this definition is STANDARD in mathematics, it is the same one as Pinter gives, and can be found on Wikipedia as well.

this DOES NOT IMPLY that R is reflexive. i will say this again, for emphasis:

an anti-symmetric relation may, or may not, contain diagonal elements (such as (a,a)). the pairs: {(a,a), (a,a)} (the colors are just to highlight the fact that we have made two choices, here: first a, then a again) are the ONLY "symmetric pairs" {(b,a),(a,b)} that occur in R.

sometimes the term "strictly anti-symmetric" (or less commonly "asymmetric") is used for anti-symmetric and irreflexive relations. this is what Kelly is talking about (and what is happening when we replace "≤" with "<" or talk about PROPER subsets or divisors, instead of just subsets or divisors).


what YOU said:

Originally Posted by Hartlw

R is antisymmetric if aRb and bRa and a=b

is NOT THE SAME as:

R is antisymmetric if aRb and bRa IMPLIES a=b.

the truth-tables for "and" and "implies" are very different.

Originally Posted by Hartlw

The notion that one has to regard Truth Function concepts and Truth Tables from mathematical logic in ordinary and mathematical writing would make writing and reading virtually impossible. I caught myself doing it and thought, this is ridiculous. “If-Then “ is a fundamental, primitive, lanquage concept which occurrs repeatedly in any math text with a clear understanding of what it means. (If A then B) is true when A implies B and false when A is true and B is false.

I assume that the last phrase also means that "if A, then B" is true when it is not the case that A is true and B is false, i.e., when A is false or B is true. But this is exactly the truth table definition of "if ... then ...". So, it's not hard after all. And without a clear understanding when "If A, then B" is true and when it is false it is impossible to do any mathematics. For example, it is impossible even to reason about the claim "For any integer n, if n is divisible by 4, then n is even."

Plato,

What Halmos, Quine, and others mean to say is:
R is antisymmetric if aRb and not bRa, or aRa.* Ex: { (3,1), (1,2), (1,1)}

What Kelly, Tarski, Kleene and others say is:
R is antisymmetric if aRb and not bRa. Ex: {(3,1), (1,2)}

Since they are definitions, which one is “right” depends on context in which they are used. There could be a problem if a proof invokes antisymmetry without specifying which definition.

* This is not the same as the definition R is antisymmetric if [aRb and bRa → a=b].
[aRb and bRa → a=b] is true if (aRb and bRa) is true or vacuously true if (aRb and bRa) is false. In either case a=b and reflexive = antisymmetric.

Originally Posted by emakarov

And without a clear understanding when "If A, then B" is true and when it is false it is impossible to do any mathematics. For example, it is impossible even to reason about the claim "For any integer n, if n is divisible by 4, then n is even."

It's easy. (If A then B) is true when A true implies B true and false when A true implies B false. That is the standard format of any theorem in mathematics. If you assume A is true and can show B is true, the theorem is true. If you assume A is true and can show B is false, the theorem is False.

"For any integer n, if n is divisible by 4, then n is even," Depends on n, ie, (If Then) is meaningless in this case without further qualification.

Originally Posted by Hartlw

Plato,

What Halmos, Quine, and others mean to say is:
R is antisymmetric if aRb and not bRa, or aRa.* Ex: { (3,1), (1,2), (1,1)}

What Kelly, Tarski, Kleene and others say is:
R is antisymmetric if aRb and not bRa. Ex: {(3,1), (1,2)}

Since they are definitions, which one is “right” depends on context in which they are used. There could be a problem if a proof invokes antisymmetry without specifying which definition.

you were doing fine up to here

Originally Posted by Hartlw

* This is not the same as the definition R is antisymmetric if [aRb and bRa → a=b].
[aRb and bRa → a=b] is true if (aRb and bRa) is true or vacuously true if (aRb and bRa) is false. In either case a=b and reflexive = antisymmetric.

no, [aRb and bRa → a=b] is true IF (aRb and bRa) is false (whether or NOT a = b)

OR

if (aRb and bRa) is true AND a=b is true.

the case where (aRb and bRa) is true is really the "uninteresting" one, but it is ONLY in this case we may conclude a = b.

there are THREE ways in which (aRb and bRa) may fail to be true:

1. aRb is false, and bRa is false. in this case R tells us NOTHING about the relationship between a and b.
2. aRb is false, and bRa is true. (see next case)
3. aRb is true, and bRa is false.

in both of these cases (2&3), we cannot have a = b, for if we did, we would have: aRa is true, and aRa is false, a contradiction (by substituting a ( = b) for b in the two formulae aRb and bRa).

so in 3 out of the 4 cases for the possible truth-values of (aRb & bRa), a might not equal b. in 2 of them, a and b MUST be unequal. in one case (1) we can't tell, because it might be that:

a)aRa is false, so when a = b aRb and bRa are BOTH false
b)aRa is true, but aRb is false for some b different from a, and bRa is false for the same pair {a,b}.
c)aRa is false, aRb is false for some b distinct from a, and bRa is also false.

you also don't seem to really comprehend "vacuous truth". this is not the same as having a FALSE premise, it means that there are NO instances where the premise is true.

let me illustrate the difference: suppose our set is S = {1,2}.

here is relation R1 = {(1,2),(2,2)}

if we take a = 1, b = 2, the premise aR1b & bR1a is false (1(R1)2 is true, but 2(R1)1 is false). this is case (2) above, and we know from the (Halmos) definition of anti-symmetry that a cannot equal b. we do indeed, however, have an instance that makes aR1b and bR1a true, the pair (2,2).

here is R2 = { } (no elements at all).

here we have "vacuous truth", there aren't any elements (a,b) to test! the premise "doesn't apply". we can say with conviction R2 is "anti-symmetric" but that's not saying a whole lot. it's symmetric, too (it is, however, NOT reflexive, because neither (1,1) nor (2,2) are elements of R2).

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.

I see my mistake. I forgot to fill in the fourth line , so the truth table should be:

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 aRb only and a unequal b.

So the definition "R is antisymmetric if [aRb and bRa imply b=a]" is only true if the implication is the Truth Table Function of Mathematical Lanquage. If that isn't specified the definition is not specified because in standard lanquage, math or otherwise, (If A then B) may or may not be true if A is false. It depends on A and B. So "if A then B" is only unequivocally true if A is true.

well, here's the thing: in logic, we can't assign a truth value of "i dunno". there's true, and there's false, and that's all that is on the menu.

yes, the statement A implies B is usually only MEANINGFUL to us (in ordinary language) if indeed A is true. if A ISN'T true, we can't really be certain of our "derivation" (or deduction) of B.

an example i have seen before is this one:

your professor says, "if you get an A on the final, i will give you an A for the course".

well, if you get an A on the final, and the prof gives you a B, it's clear he was lying.

and if you get an A on the final, and he gives you an A as a grade, he was being truthful.

but what if you get a B on the final? can you say with any certainty what your grade will be, even if you know the professor never lies?