I Map possible values of a set with a condition to the naturals

[olgerm]

I want a way to map natural numbers to possible values of set A. It would also be helpful if you could tell me how many possible values are for set A(it depends of k).
All that is known about set A is: Non of set A elements is subset to another element of A, but all elements of set A are proper subsets to set B. Empty set is not element of A. Set B contains k elements.

example if k=1

1. A={}

example if k=2

1. A={}
   
2. A={{0}}
3. A={{1}}
4. A={{0}{1}}

example if k=3

1. A={}
2. A={{0}}
3. A={{1}}
   
4. A={{2}}
5. A={{0},{1}}
6. A={{0},{2}}
7. A={{1},{2}}
8. A={{0},{1},{2}}
9. A={{0,1}}
10. A={{0,1},{2}}
11. A={{0,2}}
12. A={{0,2},{1}}
13. A={{1,2}}
14. A={{1,2},{0}}
15. A={{0,1},{0,2}}
16. A={{0,1}{1,2}}
17. A={{0,2}{1,2}}
18. A={{0,1},{0,2},{1,2}}

 

[mfb]

Your description is very confusing. What is B? You use k before you introduce k. What is k? What do you mean by "possible values of set A"?

If this is a homework problem, please post the full original problem statement.

 

[andrewkirk]

Formally, we can write this as:
$$B_k = \{m\in\mathbb N\ |\ 1\le m \le k\}$$
$$S_k = \left\{A \in 2^{B_k}\smallsetminus\{B_k,\emptyset\}\ |\
\forall x\forall y((x\in A\wedge y\in A\wedge x\neq y)
\to x\not\subset y)
\right\}$$

My use of $B_k$ here corresponds to what you call B, and my $A$ corresponds to your A.

You have said you are looking for a formula for $|S_k|$, the size of set $S_k$. Are you also looking for an algorithm for writing out the elements of $S_k$ given $k$?

Also, is this homework? (we need to check)

 

[olgerm]

It is not homework.

What is k?

It is number of elements in set B.

What is B?

I defined B to describe set A more easily.

What do you mean by "possible values of set A"?

I mean set of all sets that, fulfill the conditions, that I used for describing set A.

 

[olgerm]

Formally, we can write this as:

$$\forall_x(x\in A \leftrightarrow \forall_y( y \in x \to y \in B))\wedge \forall_x(\forall_y(y \not \in x)\to x \not \in A)\wedge B \not \in A$$
That is how I think of it. I just brought subsets into describe it better.

 

[mfb]

Ah thanks, that is clearer.

If I'm not mistaken, for k=4 we get 134 options. There are 4 sets with 3 elements, 6 sets with 2 elements and 4 sets with 1 element we can include or not. As long as we only include sets from one category there are no collisions, as n-element sets are never subsets of other n-element sets. Therefore:
- 1 option is A={}
- 15 options using 3-element sets only (2⁴-1), e.g. A={{0,2,3},{0,1,3}}
- 31 options using 2-element sets only
- 15 options using 1-element sets only
- 4 options using one 3-element set and one 1-element set, e.g. A={{0,1,2},{3}}. I'll write this as "3+1".
-6 options for two 3-element sets and one 2-element sets ("3+3+2")
-12 options for 3+2
-12 options for 3+2+2
-4 options for 3+2+2+2
-6 options for 2+1+1
-12 options for 2+1
-12 options for 2+2+1
-4 options for 2+2+2+1

OEIS doesn't recognize 1,4,18,134 (or even 4,18,134).

 

[andrewkirk]

$$\forall_x(x\in A \leftrightarrow \forall_y( y \in x \to y \in B))\wedge \forall_x(\forall_y(y \not \in x)\to x \not \in A)\wedge B \not \in A$$
That is how I think of it. I just brought subsets into describe it better.

The three conjuncts say the following, in order:

1. a set is an element of A iff it is a subset of B
2. the empty set is not an element of A
3. B is not an element of A (ie all the subsets are proper)

There are two issues with this:
a. Unless I have overlooked it, the requirement that no element of A be a subset of any other element of A is missing.
b. Item 1 contradicts items 2 and 3, since item 1 implies that B and $\emptyset$ are elements of A while 2 and 3 say they are not. To fix this, the $\leftrightarrow$ in the first conjunct needs to be changed to $\to$, so that the 'iff' becomes an 'only if'.

On looking at that, I realize that requirement 2 of this list is missing from my formulation above. I will fix that now.

 

[andrewkirk]

OEIS doesn't recognize 1,4,18,134 (or even 4,18,134).

What a great site!

I have been playing around with partitions of a set of n elements, in relation to extensions of the Birthday Problem.

I wrote a program to generate the sequence of numbers of partitions of each natural number. I did a difference table to many levels, compared it with exponentials, Fibonacci, factorials and anything else I could think of, and found nothing.

But the site recognised the sequence straightaway and provided a mine of info about it here.

 

[olgerm]

a. Unless I have overlooked it, the requirement that no element of A be a subset of any other element of A is missing.
b. Item 1 contradicts items 2 and 3, since item 1 implies that B and $\emptyset$ are elements of A while 2 and 3 say they are not. To fix this, the $\leftrightarrow$ in the first conjunct needs to be changed to $\to$, so that the 'iff' becomes an 'only if'.

You are right. I try to fix it.

$$\forall_x(x\in A \to \forall_y( y \in x \to y \in B))\wedge \forall_x(\forall_y(x \in A \wedge y \in A \to \not \forall_z(z \in x \to z \in y))) \wedge \forall_x(\forall_y(y \not \in x)\to x \not \in A)\wedge B \not \in A$$