A set with a power of 'N'

Question

My set theory knowledge is limited and I wanted to inquire some help regarding this equation:

$$ (\widehat{a_1},\cdots,\widehat{a_N})=\underset{(a_1,\cdots,a_N)\in\{-1,1\}^N}{\operatorname{argmin}}\sum_{i=1}^{N}(\alpha_i+a_i\beta_i) $$

From my understanding, the equation will provide the argument that will output the minimum possible value of the function. So, does this equation work through all of $a$'s (i.e., from $\widehat{a_1}$ to $\widehat{a_N}$) and provide $N$ different number of answers?

However, my main equation is, how do you interpret the set with $\{-1,1\}^N$? Is this saying that $a_1$ to $a_N$ can only take a value of $\{-1,1\}^N$? I read in different sources that this is a power set and I wanted to know if this is correct:

$\{-1,1\}^N = \{\{\},\{-1\},\{1\},\{-1,1\}\}$

Thank you.

Answer 1

$\{-1,1\}^N$ is not a power set; it is the set of all $n$-tuples from $\{-1,1\}$. E.g., for $N=2$, $\{-1,1\}^2 = \{(-1,-1), (-1,1), (1,-1), (1,1)\}$. So this is just saying that $a_1, \dots, a_N$ are each either $-1$ or $1$.

The power set of a set $S$ is sometimes written as $2^S$, which is where you might have gotten confused.

(And, incidentally, you are correct about what the power set of $\{-1,1\}$ would be.)

Answer 2

In your linked equation (it's better to try and reproduce it in TeX), $\{-1,1\}^N$ is just the set of all sequences of length $N$ that consist only of $-1$ and $1$. I assume the $\alpha_i, \beta_i$ are probably reals you can add or substract, so for $N=2$ we get that possible sums are

• $\alpha_1 + \beta_2 + \alpha_2 + \beta_2$ (if we have the sequence $1,1$)
• $\alpha_1 + \beta_2 + \alpha_2 - \beta_2$ (for the sequence $1,-1$)
• $\alpha_1 - \beta_2 + \alpha_2 - \beta_2$ (for the seuquence $-1,-1$),
• $\alpha_1 - \beta_2 + \alpha_2 + \beta_2$ (for the sequence $-1,+1$)

and we take the mimimum of these sums and I think the $\hat{a_1}, \hat{a_2}$ are just the coefficients we used for the minimal of these numbers? I don't know what the "Arg" would be otherwise.

Answer 3

I'm kind of guessing and talking out of my hat here but I think what the text was trying to say was that if $S=\{s_i\} $ is a countable set then $\{-1,1\}^{\mathbb N}$ is equivalent to $P (S) $ with a natural bijection

$k: \{-1,1\}^{\mathbb N} \rightarrow P (S)$

via $k (\{a_i\})=\{s_i\in S| a_i =1\} $

In other words each subset corresponds to se sequence by assigning for each element in $S $ the value one if the element is in the subset and $-1$ if it is not.

For a finite equavilent statement.

So $S=\{a,b,c\}$ then

$P (S)\leftarrow\rightarrow \{-1,1\}^3$ via

{}<--> {-1,-1,-1}

{a}<-->{1,-1,-1}

{b}<-->{-1,1,-1}

{c}<-->{-1, -1,1}

{a,b}<-->{1,1,-1}

{a,c}<-->{1,-1,1}

{b,c}<-->{-1,1,1}

{a,b,c}<-->{1,1,1}

But if $S $ is countably infinite then $P (S) $ and $\{-1,1\}^{\mathbb N}$ are uncountable.

.......

You may be asked to prove there is a one to one corespondence between the real numbers and all subsets of the natural numbers. This tells you how to do it. And tells you why we frequently refer to the cardinality of the real numbers as $2^{\mathbb N} $.

(Convert the real to a binary decimal. Match it to a subset by: For each $a_i$ term in the expansion put $i$ in the subset if $i=1$ and leave it out otherwise.)

(Okay that's not actually $\mathbb R$ but is $[0,1] $ but it's the same principle and can be easily, albeit tediously, modified.)