Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set Proof math

  1. Nov 30, 2006 #1


    User Avatar
    Homework Helper

    I've started to read a book called "Types and Programming Languages" and this excerpt is from the section entitled "Mathematical Preliminaries".

    Now I can justify the conclusion to myself by reflecting that there is no tuple in R' that is neither a member of R nor (s,s) with s a member of dom(R), and none of those tuples can be removed because if an (s,s) tuple is excluded, the relation will no longer be reflexive for all s in dom(R), and if one of the other tuples "(p,q), p <> q" is excluded, it will no longer be the case that R is a subset of R'.

    But I don't imagine this was what was wanted, an informal discussion. So I'm wondering how this would be said more formally, with reasons included because I imagine reasons should be given at each step.

    Also this looks to be a proof by contradiction, so I'm wondering if there is a better way to show this.

    Okay, so after writing the above, I decided to try and write out what I hoped would be a good attempt at proving it, but after writing the next part I realise #2 is wrong. I presumably can't show that R' meets the definition by assuming it does and then showing no proper subset of it does. If I must show that it meets the definition, I should show how it meets each part of the definition. Well I'm tired now, I'll think about this perhaps on Saturday, but if you can give be some advice about proofs in general, please do.

    My mishapen attempt:

  2. jcsd
  3. Dec 1, 2006 #2
    Here's an outline of one approach to a proof.
    Arbitrary relation R on SxS.
    Relation E = {(x,x)| for all x in S} (the "equality" relation on SxS, and often denoted R^0).
    Definiton: Reflexive closure of R, denote r(R), has following properties:
    1. r(R) is reflexive.
    2. R is a subset of r(R).
    3. For any reflexive relation R' on SxS [(R a subset of R') -> (r(R) a subset of R')]

    Proposition: r(R) = (R U E).
    Proof: (direct)
    Let T = (R U E), and show that T satisfies the definition of reflexive closure stated above.

    1,2. Show that T is reflexive and that R is a subset of T. Pretty obvious.
    3. Assume a T' that is reflexive on SxS and that R is a subset of T'.
    Show T is a subset of T', i.e., show that
    for arbitrary (a,b) [(a,b) in T -> (a,b) in T'].
    Now if (a,b) is in T, then either a=b or (a,b) is in R. Again, pretty obvious.
    Consider the two cases:
    If a=b, then (a,b) is in T', since T' is reflexive.
    If (a,b) is in R, then (a,b) is in T', since R is a subset of T'.
    Consequently, we shown that T is a subset of T', and
    the definition of r(R) is satisfied for T (i.e., T = r(R)).
  4. Dec 1, 2006 #3


    User Avatar
    Homework Helper

    Thank you fopc. I am taking note of a number of things.

    Firstly, I see you define R well before proceeding. You also choose to use SxS because you know that further on you will need to speak of the elements individually.

    Then, I see you list the properties of a reflexive closure knowing you will show them in order.

    Then you state the problem and show those properties in order. This is obviously a pattern to be reused. I also see that this shows only as much as it needs to show. It makes no assumptions about S, for instance.

    Thank you, I can see that mathematical thinking is different to any other type of thinking; it is thinking out of context, perhaps pure thought or reasoning.

    To say that one is given a set or a relation seems odd because a set or relation is not something that can be given as such. I can't say "here, let me give you a set". So this is giving in a new sense. Perhaps it would be better phrased as "If I were to be given some set S with such and such properties, etc, I could know the following about that given set S".

    So mathematics is then reasoning about quantity abstracted, and for it to be useful it requires some concrete realisation. Or rather, we practice the abstracted reasoning so that when we find a realisation of it, we can deduce things straight away. So I should probably say that mathematics is practice. To do mathematics is to practice mathematics, and there is no more to it than the practice.

    Abstract algebra would merely be a higher level of abstraction, not different in kind from 1+1=2. I should also say then that foundations are arbitrary; mathematics has extremities rather than foundations.

    Ok, I think I have a much clearer idea of things now. I have got more than expected from this thread.
  5. Dec 6, 2006 #4


    User Avatar
    Gold Member

    The mathematical objects are given in the sense that some fact or statement about them is assumed to be true (or to be a theorem). In this case, their existence is assumed. (You can give descriptions of mathematical objects that cannot possibly exist, so whether an object exists is a question that needs to be decided.) The given statements are just the statements that you are assuming to be true, in contrast to those statements that you are trying to prove. Given statements are also generally called assumptions, hypotheses, or premises, and usually in a more specific context, axioms or postulates.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook