Undergrad Sets, Subsets, Possible Relations

[Figaro]

Given a set, there are subsets and possible relations between those arbitrary subsets. For a given example set, the possible relation between the subsets of the example set will narrow down to the "true" possible relations between those subsets.

a) {1}
Number of Subsets: $2^1 = 2$ (∅, {1}) where the power means how many elements

Number of Possible Relations (suppose those two subsets A and B are arbitrary): $2^2 = 4$ (A⊆A, A⊆B, B⊆B, B⊆A) where the base is 2 since there are two subsets and the power is 2 since there are two possible ways to relate each pair.

Number of "True" Possible Relations: 3 (∅⊆∅, ∅⊆{1}, {1}⊆{1})

b) {1,2}
Number of Subsets: $2^2 = 4$

Number of Possible Relations (suppose those two subsets A and B are arbitrary): $4^2 = 16$

Number of "True" Possible Relations: 9

c) {1,2,3}
Number of Subsets: $2^3 = 8$

Number of Possible Relations (suppose those two subsets A and B are arbitrary): $8^2 = 64$

Number of "True" Possible Relations: 27

d) {1,2,3, ..., n}
Number of Subsets: $2^n$

Number of Possible Relations (suppose those two subsets A and B are arbitrary): $(2^n)^2 = 2^{2n}$

Number of "True" Possible Relations: $3^n$

Part d) is guesswork. So is part d) correct by the pattern that is given in part a)-c)? I know that I need to do induction in order to formally say that IT is correct but the question is if I can guess by the pattern.

 

[mfb]

For a set with n elements, you have
- 1 subset with 0 elements, leading to 2ⁿ true possible relations
- n subsets with 1 element, leading to n*2^n-1 true possible relations
- ...
- 1 subset with n elements, leading to 1 possible relation.

This is the binomial expansion of (2+1)ⁿ. No need to use induction.