Я бы сделал что-то вроде этого
$('#check').change(function() {
$(this).attr('checked', false);
$('label[for="' + $(this).attr('id') + '"]').WHATEVER();
});
Это позволит вам сохранить тот же HTML, что и у вас.
В качестве альтернативы, вы можете использовать метод closest
, как описано в @ kprobst
$("#Check").closest('label');
Однако это «могло бы» быть неверно истолковано, если рядом расположены две метки.Первое предложение гарантирует, что вы называете «правильную» метку для ввода.