Axiom of Choice
·
Mathematics/Set Theory
Axiom of ChoiceAxiom of Choice. To any nonempty family $\mathcal{P}$ whose elements are nonempty sets, there exists a function called a choice function $$f : \mathcal{P} \longrightarrow \bigcap_{A \in \mathcal{P}} A$$ such that $f(A) \in A$ for all $A \in \mathcal{P}$. 다시 말해 임의의 집합족이 있을 때 집합족의 원소인 각 집합에서 하나씩 원소를 꺼내서 대응시키는 그러한 함수가 존재한다는 내용이다. 집합족이 유한할 때는 당연하지만, 문제는 무한한 경우이다. (문제는 항상 무한에서 발생한다.) 쉽..
Cardinality
·
Mathematics/Set Theory
CardinalityDefinition 1. We define the cardinality of a set $X$, denoted by card $X$, by satisfying the following properties: (1) Each set $A$ is associated with card $A$, and for each cardinality $a$ there is a set $A$ with card $A = a$.(2) Card $X = 0 \iff X = \emptyset$(3) If $X \sim \mathbb{N}_k$ for some $k \in \mathbb{N}$, then card $X = k$.(4) For any two sets $A$ and $B$, card $A$ = card..
Denumerable and Countable Sets
·
Mathematics/Set Theory
Denumerable and Countable SetsDefinition 1. A set $X$ is said to be denumerable if $X \sim \mathbb{N}$. A countable set is a set which is either finite or denumerable.Countable set은 말 그대로 대상들을 하나하나 '셀 수 있는', 가산집합을 의미한다. 유한집합은 직관적으로도 당연히 셀 수 있다. 말 그대로 대상이 유한 개니까 시간은 좀 걸리더라도 언젠가 끝이 있기 때문이다. 그러나 무한집합의 경우는 어떻게 가능할까? 비록 세아려야 할 대상이 무한하지만, 각 대상이 모두 번호가 붙어 있어서 우리에게 그 번호의 규칙이 주어진다면 다른 의미에서 셀 수 있다고 말할 수 있..
Equipotence of Sets
·
Mathematics/Set Theory
EquipotentDefinition 1. Two Sets $X$ and $Y$ are said to be equipotent, symbolized as $X \sim Y$ provided that there exists a bijection $f : X \longrightarrow Y$.이때 $\sim$를 relation으로 정의할 수 있고 뿐만 아니라 동치 관계가 된다는 것을 쉽게 알 수 있다. 두 집합 사이의 bijection이 존재한다는 것은 집합의 각 원소를 일대일 대응시킬 수 있다는 말이고, 이는 두 집합의 크기가 같다는 말로도 이해할 수 있다. 이는 유한집합 뿐만 아니라 무한집합을 다룰 때에 매우 유용한 툴이라고 할 수 있다.Theorem 1Theorem 1. Let $X, Y, Z$ and..
Infinite Sets
·
Mathematics/Set Theory
Infinite SetsDefinition 1. A set $X$ is infinite if there is a proper subset $Y$ to be equipotent to $X$, that is, there is a bijection from $X$ to $Y$. A set is finite if it is not infinite.무한을 정의하기란 매우 어려운 일이다. 무한집합을 정의한 위 서술에서 '무한'이라는 말이 직접적으로 들어가 있지 않음에 주목하자. 이 정의는 언뜻 보면 쌩뚱맞지만, 우리가 직관적으로 생각하는 '무한' 집합에서만 볼 수 있는 특이한 성질이다. 예컨대 자연수 집합 $\mathbb{N}$을 생각하자. 이때 함수 $\sigma : \mathbb{N} \longrightarro..
Composition of Functions
·
Mathematics/Set Theory
Composition of FunctionsDefinition 1. Let $f : X \longrightarrow Y$ and $g : Y \longrightarrow Z$ be functions. The composition of $f$ and $g$ is the function $g \circ f : X \longrightarrow Z$ where $(g \circ f)(x) = f(g(x)), \forall x \in X$. In other words, $$g \circ f = \{(x, z) \in X \times Z \, | \, \exists y \in Y \text{ such that } (x, y) \in f \wedge (y, z) \in g\}. $$
Injective, Surjective, and Bijective
·
Mathematics/Set Theory
InjectiveDefinition 1. A function $f : X \longrightarrow Y$ is said to be injective or one-to-one if $x_1, x_2 \in X$ with $f(x_1) = f(x_2)$, then $x_1 = x_2$. SurjectiveDefinition 2. A function $f : X \longrightarrow Y$ is said to be surjective or onto if $y \in Y$, then there exists $x \in X$ such that $f(x) = y$. In other words, $f : X \longrightarrow Y$ is surjective $\iff f(X) = Y$.Bijectiv..
Function
·
Mathematics/Set Theory
FunctionDefinition 1. Let $X, Y$ be sets. A function from $X$ to $Y$ is a relation $f$ from $X$ to $Y$ satisfying (a) Dom($f$) = $X$,(b) If $(x, y) \in f$ and $(x, z) \in f$, then $y = z$.$(x, y) \in f$는 관습상 $xfy$가 아닌 $y = f(x)$라고 쓴다. 또한 $X$에서 $Y$로의 관계인 함수 $f$는 $f : X \longrightarrow Y$와 같이 표기한다. The Condition For Functions To Be EqualTheorem 1. Let $f, g : X \longrightarrow Y$ be functions. The..
Partition
·
Mathematics/Set Theory
PartitionDefinition 1. Let $X$ be a nonempty set. A partition $\mathcal{P}$ of $X$ is a set of nonempty subsets $X$ such that (a) If $A, B \in \mathcal{P}$ and $A \neq B$, then $A \cap B = \emptyset$(b) $\cup_{C \in \mathcal{P}} C = X$.직관적으로 말하면, partiton은 집합 $X$를 겹치는 부분 없이 잘라놓은 집합이라고 할 수 있다. Equivalence Class, Quotient SetDefinition 2. Let $R$ be an equivalence relation on a nonempty set $X$. F..
Indexed Families of Sets
·
Mathematics/Set Theory
UnionDefinition 1. Let $\mathcal{F}$ be a family of sets. The union of the sets in $\mathcal{F}$, denoted by $\cup_{A \in \mathcal{F}} A$ is the set of all elements that are in $A$ for some $A \in \mathcal{F}$. That is, $$\bigcup_{A \in \mathcal{F}} A = \{ x \in U \, | \, \exists A \in \mathcal {F}, x \in A \}.$$IntersectionDefinition 2. Let $\mathcal{F}$ be a family of sets. The intersection of..