Explore BrainMass
Share

Explore BrainMass

    Relations and sets

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    1) Find a relation R on a set S that is neither Symmetric nor antisymmetric

    2) Let S be a set containing exactly n elements. How many antisymmetric relations on S are there.

    3) give a recursive definition of X^n for any positive integer n

    4) give a recursive definition of the nth odd positive integer

    5) Let g: Z -> Z be defined by g(x)= ax + b, where Z denotes the set of integers and a,b E Z with a not equal 0
    a) prove that g is one-to-one
    b) what must be true about a and b if g is onto?

    6) let S be a set of people. For x, y E S, define xRy to mean that x = y or x is a decendant of y. Prove that R is a partial order on S

    © BrainMass Inc. brainmass.com October 9, 2019, 9:29 pm ad1c9bdddf
    https://brainmass.com/math/combinatorics/relations-and-sets-187151

    Solution Preview

    1) Find a relation R on a set S that is neither Symmetric nor antisymmetric
    Let S = {a,b,c}, the relation on S is defined as R = {(a,b), (b,a), (a,c)}
    Then R is not symmetric because (a,c) is in R but (c,a) is not in R.
    R is not antisymmetric because (a,b) and (b,a) are in R but a is not equal to b.

    2) Let S be a set containing exactly n elements. How many antisymmetric relations on S are there.
    Suppose R is an antisymmetric relation on S, for a,b in S and a is not equal to b, if (a,b) is in R, then (b,a) is not in R.
    Because if (b,a) is in R, by antisymmetry, we have a = b. That is not true.
    Let X = {(a,b) | a, b are in S}. Any relation R is a subset in X. S has n elements, then X has n^2 elements.
    Assume S = {a_1, a_2, ..., a_n}, let X_ij = {(a_i, a_j), (a_j, a_i)}, i<j.
    Let X_0 = X_11 U X_22 U ... U X_nn, then X_0 has n elements. Each X_ij (i<j) has 2 elements.
    So X = X_0 U X_12 U ... U X_1n U X_23 U X_24 U ... U X_2n U ... U X_(n-1)n
    There ...

    Solution Summary

    This shows how to find relations for given characteristics, and complete proofs regarding sets.

    $2.19