Page 3 of 4 FirstFirst 1234 LastLast
Results 31 to 45 of 46
Like Tree3Thanks

Math Help - Reflexive and Anti-symmetric

  1. #31
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Vacuously True and Anti-symmetry

    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:

    Quote Originally Posted by Hartlw View Post
    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.
    Last edited by Hartlw; November 16th 2012 at 06:32 AM. Reason: post # 26
    Follow Math Help Forum on Facebook and Google+

  2. #32
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,939
    Thanks
    338
    Awards
    1

    Re: Vacuously True and Anti-symmetry

    Quote Originally Posted by Hartlw View Post
    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.
    Last edited by topsquark; November 16th 2012 at 07:52 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #33
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Vacuously True and Anti-symmetry

    Quote Originally Posted by topsquark View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #34
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1

    Re: Vacuously True and Anti-symmetry

    Quote Originally Posted by Hartlw View Post
    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 \mathcal{R}\cap\mathcal{R}^{-1}=\emptyset if \mathcal{R} is anti-symmetric.

    But most standard set theory texts (see Charles Pinter) have this theorem:
    If \mathcal{R} is anti-symmetric then \mathcal{R}\cap\mathcal{R}^{-1}\subseteq\Delta_A=\{(x,x):x\in A\}.

    So I think that you are very unwise to rely on Kelley's definition.
    Follow Math Help Forum on Facebook and Google+

  5. #35
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    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.
    Last edited by Hartlw; November 21st 2012 at 09:54 AM. Reason: Add "EDIT."
    Follow Math Help Forum on Facebook and Google+

  6. #36
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    "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.
    \mathcal{G} is a relation in A, then \mathcal{G} is anti-symmetric if (a,b)\in \mathcal{G}~\&~(b,a)\in \mathcal{G} then a=b.

    I dare you to find a definition of anti-symmetry equivalent of Kelley's anywhere else.
    Follow Math Help Forum on Facebook and Google+

  7. #37
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Plato View Post
    Here is an exact definition of anti-symmetry from Pinter.
    \mathcal{G} is a relation in A, then \mathcal{G} is anti-symmetric if (a,b)\in \mathcal{G}~\&~(b,a)\in \mathcal{G} then a=b.

    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?
    Follow Math Help Forum on Facebook and Google+

  8. #38
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    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 " \mathcal{R} is anti-symmetric iff it is never the case that both x\mathcal{R}y\text{ and }y\mathcal{R}y" 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, \mathcal{R} is anti-symmetric iff \mathcal{R}\cap\mathcal{R}^{-1} is void".

    Once again here is a standard example.
    Let A=\{1,2,3\} and define \mathcal{R}=\{(1,2),(2,3),(3,3}\}. Now using the standard definition \mathcal{R} is anti-symetric, BUT \mathcal{R}\cap\mathcal{R}^{-1}=\{(3,3)\}. So Kelley's is not standard or even a subset of the standard.
    Follow Math Help Forum on Facebook and Google+

  9. #39
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    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

    \text{A relation }R\ \text{on a set }A\ \text{is called } \emph{antisymmetric}\ \text{if}

    \forall a,b \left[((a,b) \in R \wedge (b,a) \in R) \implies a=b \right]

    \text{for all }a,b \in A.

    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:

    Quote 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.
    Follow Math Help Forum on Facebook and Google+

  10. #40
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: Vacuously True and Anti-symmetry

    Quote Originally Posted by Hartlw View Post
    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."
    Follow Math Help Forum on Facebook and Google+

  11. #41
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #42
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Vacuously True and Anti-symmetry

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #43
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    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

    Quote 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).
    Follow Math Help Forum on Facebook and Google+

  14. #44
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Reflexive and Anti-symmetric

    Quote Originally Posted by Hartlw View Post
    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.
    Last edited by Hartlw; November 22nd 2012 at 06:06 AM.
    Follow Math Help Forum on Facebook and Google+

  15. #45
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Reflexive and Anti-symmetric

    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?
    Follow Math Help Forum on Facebook and Google+

Page 3 of 4 FirstFirst 1234 LastLast

Similar Math Help Forum Discussions

  1. Reflexive And Symmetric
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: November 7th 2012, 12:58 PM
  2. reflexive, anti symmetric etc... for a set
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 23rd 2012, 04:52 PM
  3. Symmetric, transitive, not reflexive?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 2nd 2010, 12:32 AM
  4. Reflexive, symmetric, and transitive
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2009, 11:08 AM
  5. Reflexive and symmetric
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: March 12th 2009, 04:56 AM

Search Tags


/mathhelpforum @mathhelpforum