Задачки по матлогике

[Bec0o1]

Приветствую! Помогите, пожалуйста, разобраться с несколькими задачками по матлогике, второй семестр, 1 курс.

1. Верно ли, что для любых двух отношений экивалентности R и S, отношение R U S (U - объединение) также является отношением эквивалентности.
(Я, в принципе, показал, что не выполняется транзитивность, но препод попросил привести конкретный пример...)
2. Сравнить мощности множеств вещественных чисел и счетных последовательностей вещественных чисел.
(Вроде бы они оба континуальны, но строгое доказательство написать что-то не выходит)
3. Определить мощность множества (n x n)-матриц над множеством рациональных чисел с определителем, равным 1.
(Один раз вышло что счетно, другой раз, что континуально o_o )
4. (вроде сам только что разобрался, так что пропускаю)
5. Пусть A и B - системы одной сигнатуры такие, что существует гомоморфизм из A на B. Предложение не"Фи", где "Фи" не содержит импликаций или отрицаний, истинно в B. Доказать, что A |= не"Фи". (тожд. истинность в А)
6. Пусть N = (N ; | ), где N - множество натуральных чисел, | - бинарное отношение, истинное на паре элементов тогда и только тогда, когда перый элемент делит второй. Записать формулу, истинную только на элементе 2 (либо установить, что такой формулы не сущетсвует).
[ ( (x | 2) \/ не(x | 1) ) - неправильно, тогда ( ( (x ; 2) < | ) \/ не( (x ; 1) < |) ) ? ]
7. Пусть (An)n<N (< - принадлежность) - семейство систем данной сигнатуры такое, что |An| = n/2, если n четное и не превосходит 100, |An| = (n+1)/2, если n нечетное, и |An|<=3 (меньше, либо равно) в остальных случаях. Какие значения может принимать ультрапроизведение П An/U (n<N)?
(классно было бы про эту задачу поподробнее, т.к. с ней я совсем плохо)

Очень надеюсь на вашу помощь, заранее спасибо.

[мат-ламер]

По поводу второй задачи. Мно-во вещ. чисел эквивалентно множеству счётных последовательностей нулей и единиц. Счётное произведение таких множеств само есть такое (т.е. состоит из счётных последовательностей нулей и единиц).

[nn910]

Bec0o1 в сообщении #224923 писал(а):

6. Пусть N = (N ; | ), где N - множество натуральных чисел, | - бинарное отношение, истинное на паре элементов тогда и только тогда, когда перый элемент делит второй. Записать формулу, истинную только на элементе 2 (либо установить, что такой формулы не сущетсвует).
[ ( (x | 2) \/ не(x | 1) ) - неправильно, тогда ( ( (x ; 2) < | ) \/ не( (x ; 1) < |) ) ? ]

[ ( (x | 2) & [ ( (2 | x)]

[мат-ламер]

По поводу третьей задачи. Рассмотрите сначала случай $n=2$ и воспользуйтесь рациональной параметризацией окружности.

-- Пт июн 26, 2009 14:46:47 --

А откуда у Вас вылезла континуальность? Даже если снять ограничение на ортогональность, то и тогда более чем счётность не выходит.

-- Пт июн 26, 2009 14:49:43 --

По поводу первой задачи. Посмотрите, что будет, если первое отношение связывает первые два элемента множества, а второе - третий и четвёртый.

[Таня Тайс]

Bec0o1 в сообщении #224923 писал(а):

1. Верно ли, что для любых двух отношений экивалентности R и S, отношение R U S (U - объединение) также является отношением эквивалентности.

Попробую написать пример
Определим два отношения эквивалентности для множеств А, В
$A\cap B=\varnothing$
$x\sim_{A}y \Leftrightarrow x,y \in A$
$x\sim_{B}y \Leftrightarrow x,y \in B^{C}$
Рассмотрим элементы $x, y, z$ такие, что
$x,y \in A, \; z\in (A\cup B)^{C}$
Тогда
$x\sim_{A}y, \; y\sim_{B}z, \; x\sim_{B}z, \; x\nsim_{A}z,\; y\nsim_{A}z $

[vlad239]

Зачем такие сложности? Два двузначных числа эквивалентны, если у них совпадает первая цифра (это отношение $R$) или вторая (это отношение $S$). А их объединение - фигня какая-то.

Влад.

[Таня Тайс]

vlad239
так это почти то же самое

[Bec0o1]

Всем большое спасибо за помощь! Однако есть некоторые вопросы.

По поводу второй задачи. Навесим на R звездочку Клини, насколько я понимаю, мы как раз получим множество счетных последовательностей R. А по теореме о том, что декартово произведение конечного числа счетных множеств, есть множетво счетное, получается, что |R*|=|R|. Т.е. получается, что таким образом задача решена, или это ерунда?

По поводу [ ( (x | 2) & [ ( (2 | x)]. Оно как-бы верно, но проблема в том, что двоек у нас в сигнатуре нету, так что получается, что формула записана неверно. (препод в таком виде точно не примет) По-идее нужно как-то обозначить двойку через "|". Единицу-то легко (для любого а из N: b|a, т.е. b = 1), а вот как двойку я что-то никак не смекну.

Цитата:

А откуда у Вас вылезла континуальность? Даже если снять ограничение на ортогональность, то и тогда более чем счётность не выходит.

Ну вот если взять множество диагональных матриц с определителем равным единице, то тогда любому числу из R, можно сопоставить диагональную матрицу с опр. = 1 вида:
( a; 1/a; a; 1/a; ... ; 1/a ) - элементы матрицы, стоящие на главной диагонали, если их количество четно и
( a; 1/a; ...; a; 1/a ;1) - если нечетно. Т.е. получается, что уже только количество диагональных матриц, с опр. = 1 более чем счетно. Или это опять бред?

[vlad239]

У Вас матрицы с рациональными элементами, а не с вещественными!

Влад.

[Bec0o1]

vlad239 в сообщении #224997 писал(а):

У Вас матрицы с рациональными элементами, а не с вещественными!

Влад.

Точно! Мда, во я дубина. Ну ладно, тогда как-то так можно каждому рациональному числу сопоставить (n x n) матрицу. Но как тогда каждой (n x n) матрице сопоставить рациональное число, чтобы выполнялось и в обратную сторону?

[ИСН]

Ну а как доказывают, что множество рациональных чисел счётно? Вот и тут так же.