I've got this last problem to do and I'm stuck. for and A and B i'm just showing they have the same cardinality or domains? Not sure how to do all parts to this question at all
For the purposes of this exercise, consider a social network to be a graph whose vertices are called actors and whose edges are called ties. A social network is called simple if the graph is simple; that is, there are no loops (i.e., ties from an actor to itself) and there is no more than one tie between any pair of actors.
a. Two actors A and B in a simple social network are called structurally equivalent if, for all actors C in the network, A has a tie to C if and only if B has a tie to C. Show that structural equivalence is an equivalence relation.
b. Show that two actors A and B in a simple social network cannot be structurally equivalent if there is a tie between them.
c. Let S denote the set of all actors in a simple social network. Two actors A and B are called automorphically equivalent if there exists a bijection f : S → S with the following properties: • f(A) = B. • If C and D belong to S, then C has a tie to D if and only if f(C) has a tie to f(D). Show that automorphic equivalence is an equivalence relation.
d. Show that any pair of actors A and B that are structurally equivalent must also be automorphically equivalent. Construct a specific example of a simple social network in which two actors are automorphically equivalent but not structurally equivalent. (Be sure to verify all the details of the automorphic equivalence.)
For each actor $A$ let $\mathscr{N}(A)$ be the set of actors to whom $A$ has ties. The definition of structural equivalence can then be rephrased as follows:
Write $A\sim_sB$ if $A$ and $B$ are structurally equivalent; in (a) you’re to show that $\sim_s$ is an equivalent relation on the set $S$ of actors. In other words, you must show that it’s reflexive, symmetric, and transitive: $A\sim_sA$ for each actor $A$; if $A\sim_sB$, then $B\sim_sA$; and if $A\sim_sB$ and $B\sim_sC$, then $A\sim_sC$. This is very straightforward.
In (b) you’re to show that if there is a tie between $A$ and $B$, then $A\not\sim_sB$; according to the highlighted rephrasing, this amounts to showing that $\mathscr{N}(A)\ne\mathscr{N}(B)$.
In (c) a new relation between actors is defined, automorphic equivalence. As it says, actors $A$ and $B$ are automorphically equivalent if there is a bijection $f:S\to S$ such that $f(A)=B$, and for all actors $C$ and $D$, $C$ and $D$ have a tie if and only if $f(C)$ and $f(D)$ have a tie. In graph-theoretic language, $f$ is an automorphism (i.e., an isomorphism to itself) of the graph whose vertices are the actors and whose edges are the ties. Write $A\sim_aB$ if $A$ and $B$ are automorphically equivalent. Your task is to show that $\sim_a$ is another equivalence relation. I’ll get you started on the argument that $\sim_a$ is symmetric.
In (d) you have two tasks. First, you have to show that for any actors $A$ and $B$, if $A\sim_sB$, then $A\sim_aB$. That is, you have to show that if $\mathscr{N}A=\mathscr{N}(B)$, then there is a bijection $f:S\to S$ such that $f(A)=B$, and for all actors $C$ and $D$, $C$ and $D$ have a tie if and only if $f(C)$ and $f(D)$ have a tie. HINT: Let $f(C)=C$ for all $C\in S$ except $A$ and $B$. What should $f$ do to $A$ and $B$?
Your second task is to construct an example of a social network that has two actors $A$ and $B$ such that $A\sim_aB$, but $A\not\sim_sB$. HINT: