Sets, Functions and Preimages | Physics and Mathematics for AI

03 / LOGIC LAB

먼저 알아두면 좋아요 · 기본 정수 계산과 연결된 앞 단원의 표기

양화사·증인과 반례 →

단원 목록 (103) · 집합·함수와 역상

이해하는 속도로 읽으세요.개념도 이론 실험 확인 문제

BUILD YOUR INTUITION

먼저 그림으로 이해하기

한 번에 한 단계씩 살펴보세요.

원소의 소속과 함수의 입력·출력 공간을 구분하여 데이터 변환을 읽습니다.

고정한 유한 기준 모형입니다. 단계별 설명과 별도의 일반 논증을 구분해 읽으세요. 고정된 기준 예제이며 아래 실험의 설정과 독립적입니다.

1 / 4

집합 연산

A는 짝수 입력, B는 t 이상인 입력입니다.

A∩B, A∪B, A\B

실험에서 확인하기 →

이 단원 목차

변환하기 전에 대상을 구분하기

데이터 필터는 레코드 집합을 고르고, 인코더는 레코드를 표현으로 보내며, 디코더는 표현에서 객체로 돌아갑니다. 서로 다른 수학 연산이고 정의역에 따라 보장의 의미도 다릅니다.

집합은 소속만 기록하고 순서·중복 횟수는 기록하지 않습니다. {1,1,2}와 {1,2}는 같은 집합이지만 수열이나 다중집합은 추가 정보를 보존합니다. 순서가 있는 배치나 반복 관측을 집합으로 바꾸면 개수 정보가 사라질 수 있습니다.

집합 연산을 술어로 읽기

우주 D를 고정하면 합집합은 ‘또는’, 교집합은 ‘그리고’입니다.

x\in A\cup B\iff(x\in A)\lor(x\in B),\qquad x\in A\cap B\iff(x\in A)\land(x\in B).

차집합 $A\setminus B$ 는 A에 속하고 B에는 속하지 않는 경우입니다. 여집합은 반드시 어느 우주에 대한 것인지 정합니다. 소속 술어를 부정하면 De Morgan 법칙도 얻습니다.

실험의 D={0,…,m−1}, A는 짝수 입력, B={x∈D:x≥t}입니다. m=3,t=1이면 A={0,2}, B={1,2}, 교집합={2}, 합집합={0,1,2}, A에서 B를 뺀 집합={0}입니다. 표는 각 원소의 소속을 확인합니다.

함수에는 정의역과 공역이 포함된다

$f:D\to C$ 는 D의 각 입력에 C의 출력 하나를 대응합니다. 다른 입력이 같은 출력에 갈 수도, 공역의 일부를 전혀 쓰지 않을 수도 있습니다. 둘 다 함수 정의에 위배되지 않습니다.

대상	의미
D	허용 입력인 정의역
C	선언한 출력 공간인 공역
f(D)	실제로 도달한 상
f⁻¹(E)	공역 부분집합 E의 역상

실험은 C={0,…,n−1}, $f(x)=(ax+b)\bmod n$ 입니다. 소문자 b는 이동량으로 집합 B와 다릅니다. 정수 매개변수와 음이 아닌 입력을 사용하여 나머지는 지정한 비음수 잉여입니다.

단사·전사·전단사

단사는

\forall x_1,x_2\in D:\quad f(x_1)=f(x_2)\Rightarrow x_1=x_2

입니다. 전사는 $\forall y\in C\exists x\in D:f(x)=y$ 이고, 전단사는 둘 다입니다. 입력 충돌과 공역 전체의 사용이라는 다른 양화 질문입니다.

m=n=3,a=1,b=0이면 항등함수라 전단사입니다. m=4,n=2이면 출력이 0,1,0,1이어서 전사지만 단사가 아닙니다. m=2,n=4이면 출력 0,1이 달라 단사지만 공역 전체를 쓰지 않아 전사는 아닙니다.

유한 정의역과 공역의 원소 수가 같으면 단사와 전사가 동치입니다. 무한 집합에 그대로 적용하지 마세요. ℕ={0,1,…}에서 x↦x+1은 단사지만 0을 놓칩니다.

역상과 역함수는 다르다

E⊆C의 역상은

f^{-1}(E)=\{x\in D:f(x)\in E\}

입니다. 역함수의 존재가 필요하지 않습니다. 여러 입력이 같은 출력으로 가는 예제에서 짝수 출력 집합 {0}의 역상은 {0,2}입니다. 공역에서 정의역으로 가는 역함수라면 원래 입력을 유일하게 정해야 해서 이 충돌을 되돌릴 수 없습니다.

전단사 함수는 양쪽 역함수를 가집니다. 단사는 공역보다 작을 수 있는 상 위에서 역을 정의할 수 있습니다. 유한 전사 함수에 원상을 하나씩 선택할 수 있어도 모든 원래 입력을 복구하는 것과는 다릅니다.

역상의 항등식 직접 증명

임의의 x∈D를 따라가면

x\in f^{-1}(E\cap F) \iff f(x)\in E\land f(x)\in F \iff x\in f^{-1}(E)\cap f^{-1}(F)

입니다. 따라서 역상은 교집합을 보존합니다. 합집합과 상대 여집합도 같은 소속 논증으로 증명합니다. 표본 몇 개를 확인한 것이 아니라 임의 원소에 대한 직접 증명입니다.

상은 다릅니다. 일반적으로 $f(A\cap B)\subseteq f(A)\cap f(B)$ 이지만 충돌 때문에 등호는 실패할 수 있습니다. 여러 입력·한 출력 예제에서 A={0}, B={2}라면 왼쪽은 빈 집합, 오른쪽은 {0}입니다. 단사성은 등호를 위한 충분조건입니다.

대응도 읽기

왼쪽은 입력, 오른쪽은 공역 원소입니다. 각 입력에서 화살표 하나가 나갑니다. 여러 화살표가 모이면 충돌, 사용하지 않은 출력은 전사 실패를 나타냅니다. 노드 위치는 거리나 확률이 아닙니다.

소속 표와 상·역상은 같은 함수를 계산합니다. 도달한 값이 같아도 선언한 공역을 바꾸면 전사 여부가 바뀔 수 있습니다. 함수의 전체 형식을 명시하세요.

AI 해석과 한계

충돌이 있는 압축 인코더는 어떤 입력이 표현을 만들었는지 잃습니다. 추가 정보나 입력 제한 없이 같은 코드에서 다른 원본 둘을 모두 결정적으로 복원할 수는 없습니다. 표본의 낮은 재구성 손실이 전역 가역성을 입증하지는 않습니다.

특징 조건으로 레코드를 고르는 것은 역상입니다. 데이터 선택을 명확히 표현하지만 표집 편향이나 인과 타당성은 별도 문제입니다. 함수 형식만으로 수치 안정성·연속성·미분 가능성도 보장하지 않습니다.

연습과 근거

m=4,t=2에서 A,B,교집합은? 답: {0,2}, {2,3}, {2}입니다.
여러 입력·한 출력 예제의 {1} 역상은? 답: {1,3}입니다.
임의 입력을 따라가며 역상이 합집합을 보존함을 증명하세요.
인코딩 충돌을 만들고 디코더가 무엇을 추론할 수 없는지 정확히 적으세요.

보충은 MIT Mathematics for Computer Science 읽기 자료를 참고하세요. 유한 대응 예제는 이 교재의 직접 구성입니다.

CHECK YOUR UNDERSTANDING

설명할 수 있나요?

실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.

1. 역상 f⁻¹(E)는 역함수가 있어야 하나요?항상 필요아니요E가 비면 필요

2. 4개 입력을 2개 출력에 보내 모두 쓰면?전사지만 단사가 아니다반드시 전단사함수가 아니다

이 단원을 이해했고, 내 말로 설명할 수 있습니다.

선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.

INTERACTIVE LOGIC LAB

조건을 바꾸고 확인하세요

안내를 따라 실험하기

항등 대응

먼저 예측 · 각 입력에 다른 출력이 있고 모든 출력이 쓰이나요?

조작 방법 · 예제를 불러오고 그림·진리표·검사 범위를 비교하세요.

결과 해석 보기

m=n=3의 항등 대응은 전단사입니다.

예제를 열면 현재 실험 설정을 해당 값으로 바꿉니다. 아래에서 자유롭게 수정할 수 있습니다.

비교할 예제

D={0,…,2}, C={0,…,2}; f(x)=(1x+0) mod 3; B={x∈D:x≥1}

모형 설정 · 정수만 입력

입력 개수 m출력 공간 크기 n배율 a이동 bB의 하한 t

문장과 성질 확인

—는 표시한 범위에서 해당 증인이나 반례가 없음을 뜻합니다.

A: {0, 2}
B: {1, 2}
A∩B: {2}
A∪B: {0, 1, 2}
f(D): {0, 1, 2}
짝수 출력의 역상: {0, 2}
단사: 참
전사: 참
전단사: 참

표시한 유한 모형 · 3개 검사
x	x∈A	x∈B	x∈A∩B	x∈A∪B	x∈A\B	f(x)
0	참	거짓	거짓	참	참	0
1	거짓	참	거짓	참	거짓	1
2	참	참	참	참	거짓	2

D={0,…,m−1}, C={0,…,n−1}, A는 짝수 입력, B={x∈D:x≥t}입니다. 역상은 역함수와 다릅니다.

실험 설정은 이 브라우저에 자동 저장됩니다.