in Set Theory & Algebra
231 views
0 votes
0 votes
Show that there is no one-to-one correspondence from the set of positive integers to the power set of the set of positive integers. [Hint: Assume that there is such a one-to-one correspondence. Represent a subset of the set of positive integers as an infinite bit string with $ith$ bit $1$ if $i$ belongs to the subset and $0$ otherwise. Suppose that you can list these infinite strings in a sequence indexed by the positive integers. Construct a new bit string with its $ith$ bit equal to the complement of the $ith$ bit of the $ith$ string in the list. Show that this new bit string cannot appear in the list.]
in Set Theory & Algebra
by
231 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true