This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

0
votes
0answers
25 views

How to prove that composition of functions is a function

Using the fact that a function is a relation, which is a subset of the product of X and Y. (a,b) belongs to f and (a,c) belongs to f implies b=c
2
votes
4answers
45 views

What does $f^{-1}(B)= \{ x \in X \mid f(x) \in B\}$ mean?

I have encountered the expression $$f^{-1}(B) = \{ x \in X \mid f(x) \in B\}$$ My questions are: 1) What does the $-1$ exponent mean in this context? 2) Is it right to say "if the set $X$ ...
4
votes
2answers
29 views

Prove that $f(X\cap f^{-1}(Y))=f(X)\cap Y$

Let $\ f\colon A\to B$ and let $X\subset A$, $Y\subset B$, prove that $$f(X\cap f^{-1}(Y))=f(X)\cap Y$$ The "$\subset$"$-$inclusion is easy: if $y\in f(X\cap f^{-1}(Y))$, exists a $x\in X\cap ...
1
vote
2answers
60 views

What is the actual definition of a function?

I am learning precalculus and my book defines the following: A function $f$ from a set $A$ to a set $B$ is a rule that assigns to every element $a$ in $A$ one and only one value in $B$. Well, I ...
1
vote
1answer
42 views

formal definition of ordinal addition by recursion

I'm reading Kunen's Set Theory, An Introduction to Independence Proofs (1980). On page 26 he explains how to introduce ordinal addition through recursion. For the sake of convenience i'll give the ...
1
vote
1answer
61 views

Pronuntiation of the symbol $\varnothing$ of the empty set

The symbol $\varnothing$ for the empty set was introduced by Bourbaki, inspired by the Norwegian alphabet $\varnothing.$ It has no relation with the Greek letter $\phi.$ From my schooldays, when the ...
4
votes
5answers
61 views

Explanation of $\overline{\lim} A_n$ and $\underline{\lim}A_n$

Let $(A_n)_n$ be a countable family of subsets of a set $X$. We define: $$\lim \inf A_n = \underline{\lim} A_n = \bigcup_{n \in \mathbb N} \bigcap_{k \ge n} A_k$$ $$\lim \sup A_n = \overline{\lim} ...
3
votes
3answers
53 views

Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice)

I am interested in proving the titular claim: Transitive Closure of a Well-Founded Relation is Well-Founded (without Axiom of Choice) My approach: Let $R$ be a well-founded relation. We ...
4
votes
4answers
81 views

Is it possible to assign probability to a set $X$ with $|X|>2^{\aleph_0}$?

Is it possible to assign probability to a set $X$ with cardinality $|X| > 2^{\aleph_0}$? Example would be a set $|X| = 2^{2^{\aleph_0}}$.
0
votes
2answers
43 views

What does $A^{B}$ mean? [duplicate]

Assume, that A and B are finite sets. What notion $$A^{B}$$ does mean? Have been looking for awhile now.
0
votes
3answers
23 views

If A and B are disjoint and B and C are disjoint so $A\cup C$ and B are disjoint

Prove: If A and B are disjoint and B and C are disjoint so $A\cup C$ and B are disjoint We know that $A\cap B=\emptyset \wedge B\cap C=\emptyset \rightarrow (A\cap B)\cap (B\cap C)= \emptyset ...
-10
votes
1answer
39 views

SET; RELATIONS; FUNCTIONS [on hold]

For set of Real no. R which statement is false. (A). N is subset of R (B). $(a,b)$ is subset of R. $a<b$ (C). $\pi$ (pi) does not belongs to R (D). $\Phi$ (phi) is subset of R
3
votes
2answers
44 views

Question regarding proof that $V = \{ f : \Bbb N \to \Bbb N \mid f(n)\text{ is a prime for all }n \in N\}$ is uncountable

I'm studying for an exam for tomorrow and one of the old exams has this problem: Given the set $V = \{ f : \Bbb N \to \Bbb N \mid f(n)\text{ is a prime for all }n \in N \}$ Prove that this set is ...
1
vote
1answer
52 views

Power set of $\{\emptyset,\{\emptyset\}\}$ [duplicate]

For writing the power set of $\{\emptyset,\{\emptyset\}\}$, do I have to consider $\emptyset$ as null set or as a member of the given set? If I consider $\emptyset$ as a member, then the power set is ...
1
vote
1answer
40 views

Cartesian product with all elements

I have two sets A and B with $A = \{1,2,3\} \\ B = \{ A, B, C, D, E \}$ Now I need to get something similar to the Cartesian product. If my understanding is correct, the Cartesian product would ...
0
votes
1answer
26 views

Write all elements of A.A = {$x|x^2<x<10$,x is a whole number}. Answer: A ={$x|x^2+1=0$}.Explain like i'm five.

Write all elements of A.A = {$x|x^2<x<10$,x is a whole number}. Given Answer: A ={$x|x^2+1=0$}. Is this a typo?
2
votes
2answers
48 views
+100

Does meet of two partitions of a set always exist?

Let $\Omega$ be any set. Let $\mathcal{P_1}$ and $\mathcal{P}_2$ be partitions of $\Omega$. By $P_i(\omega)$ we denote cell of partition $i$ containing $\omega$. Meet of partitions $\mathcal{P}_1$ ...
0
votes
2answers
16 views

Invalid function or invalid domain

Let $ f : A \rightarrow B $ What happens if $\exists\ a\in A $ which doesn't map to any element in B ?
-2
votes
2answers
47 views

An injection from R × {0, 1} to R [on hold]

What would be an example of this An injection from R × {0, 1} to R i think it is all real numbers f(x) = x Can some one help me on this. Thanks in advance
0
votes
1answer
42 views

Defining exponentiation on the integers

If one defines the integers as equivalence classes of pairs of natural numbers, there is a (canonical?) way to define addition and multiplication for the integers based on addition and multiplication ...
-2
votes
0answers
34 views

“Elementary Set Theory - Leung, Chen” - Solution manual? [on hold]

I'm trying to study some ST on me own :-) ! I have found a very nice book with lots of problems but without any solution to the problems. Do you guys know whether someone have made a solution manual ...
-2
votes
2answers
42 views

Problem on elementary logic and set theory

Let A and B be sets with B is a subset of A. Prove that A \ (A\B)=B. I start by saying that suppose x is in A \ (A\B). By definition, x is in A and X is not in (A\B) . However, x is not in A\B ...
2
votes
2answers
42 views

Relationship between completeness and well ordering (meta).

Here is the definition for completeness of the reals (there are many equivalent formulations but I am interested in this one); Completeness: Every non-empty subset of the reals which is bounded above ...
0
votes
1answer
19 views

Set intersection of finite,nested sets of real numbers [duplicate]

I'm currently trying to write up a solution to the following problem: If $ \displaystyle A_1 \supseteq A_2 \supseteq A_3 ... $ where each $ \displaystyle A_j $ is a non-empty, finite set of real ...
3
votes
1answer
35 views

Existence of differentiable functions on $\mathbb R$ whose derivative is constant on the complement of uncountable set but not everywhere

Let $ A $ be a countable subset of the set of real numbers and $f:\mathbb R \to \mathbb R$ be a differentiable function such that $f'$ is constant on $\mathbb R \setminus A$ , then I know that $f'$ is ...
0
votes
1answer
19 views

Intervals of integers modulo n

Do the following related concepts appear anywhere in literature? Denoting an "interval" in the integers modulo $n$ by $[i,j] = \{i, i+1, \dotsc, j\}$. For example, in modulo 6, $[5,3] = ...
5
votes
3answers
481 views

Finding a bijective function between an open disk and the open square

How can I find a bijective function between these two sets? $$\{(x,y)\in\mathbb{R}^2 \,|\, x^2+y^2<1\}, \quad (-1,1) \times (-1,1) .$$ I already thought of first writing between 2nd and set ...
1
vote
2answers
32 views

How do I find the type of relation on an infinite set?

Imagine I'm given a set A = {∅, {∅}, {{∅}}, {{{∅}}},…} where ∅ is empty-set. Then I also have a relation on that set (actually on its power set) defined as: $R \subseteq \wp(A) \times \wp(A)$, where ...
1
vote
1answer
26 views

Find bijective correspondence between the sets

Find bijective correspondence between the set of all functions of $X$ in the set $\left\{ 0,1 \right\}$ and the power set of set $X$ and find $| 2 ^ X |$, if $| X | = n.$ My thoughts: ...
0
votes
1answer
39 views

How to show venn diagram?

How to show the following sets by Venn diagrams? Case 1: $$A=\{1,2,B\},B =\{3,4\}$$ Case 2: $$A=\{1,2,3,4\}, B=\{3,4\}$$
-2
votes
1answer
46 views

How many elements are in the set $S^S$, where $S=\{a,b\}$? [on hold]

If set $S =\{a,b\}$, then how many elements will be in set $S^S$? Here $S^S$ is {Set S is Exponent of S}. Do we need to do cross product like $S*S$ when it says $(S^S)$. Please advise.
0
votes
2answers
39 views

Proof in set theory

Let $A,B,C$ -- subsets in some fixed set. Prove that $A \cap B \subseteq C$ iff $A \subseteq \overline{B} \cup C$. Have no ideas how to prove this. On the language of definitions we have $$x ...
0
votes
0answers
29 views

How do I prove this assertion? [duplicate]

Let $A$ be countable union of countably infinite sets. Then $A$ is also countable.
-1
votes
2answers
33 views

Sets cardinality definition

I have a question about cardinality definition. How can we formally define cardinality for finite set using only maps from natural numbers to the set? UPD One says that the cardinality can be ...
1
vote
2answers
26 views

A simple way to know whether a well-ordered set has a subset of a certain type

Following my last question, Does $\Bbb R-\Bbb Q$ have a well ordered subset of type $\omega\cdot\omega$, I would like to have better tools to look at a set and know what order types can it have. I ...
3
votes
1answer
35 views

Cardinality of all linear transformations from $\Bbb R^3$ to $\Bbb R^2$

I tried to calculate the cardinality of all linear transformations from $\Bbb R ^3$ to $\Bbb R^2$. This is my answer- I would like to know how to formalize it better. A transformation is defined in ...
3
votes
1answer
57 views

Isomorphic or equal?

Let $\sim_n$ be the usual equivalence relation of congruence modulo $n$ in $\mathbb{Z}$, i.e., for $a,b\in\mathbb{Z}$, $a\sim_nb\Leftrightarrow a-b=k\cdot n$ for some $k\in\mathbb{Z}$. For $n=0$ the ...
0
votes
1answer
36 views

Problems with this Cartesian Product definition

Supposed I do not define ordered pair in the usual Kuratowski way $(x,y) = \{\{x\},\{x,y\}\}$. I left the ordered pair undefined but with the propriety $(x,y) = (x',y') \iff x=x'\text{ and }y=y'$. ...
3
votes
1answer
55 views

Does $\Bbb R-\Bbb Q$ have a well ordered subset of type $\omega\cdot\omega$

Does $\Bbb R- \Bbb Q$ have a well ordered subset of type $\omega\cdot\omega$? I thought of taking the subset to be A={$n\cdot \sqrt{m}:n\in\Bbb N,m\in P$} where P is the set of all prime numbers, ...
1
vote
1answer
56 views

Cantor-Bernstein Proof

Currently, I am studying Set Theory, and have come to the point of proving the Cantor-Bernstein Theorem (if $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$). Now, I am studying from Jech and ...
4
votes
2answers
113 views

Is the cardinality of $\mathbb{Z^R}$=$\mathbb{R^Z}$?

Previously in this question, we have found that $\mathbb{R^Z}$ is uncountable and its multiset of components, denoted by $$K = \{ (..., 0, 0, w, 0, 0, ... ) : w \in \mathbb{R} \}$$ where for each ...
2
votes
2answers
66 views

Can we define $ℝ^A$ where A is uncountable?

The question is pretty straightforward. How can we define the expression $ℝ^A$ when $A$ is an uncountable set? For example what is defined by forms such as $ℝ^ℝ$ or $ℝ^ℂ$? If $A$ is countable,then ...
1
vote
0answers
45 views

How to translate set propositions involving power sets and cartesian products, into first-order logic statements?

As seen from an earlier question of mine one can translate between set algebra and logic, as long as they speak about elements (a named set A is the same as {x ∣ x ∈ A}). However I've stumbled upon ...
0
votes
2answers
23 views

partial functions basics

$f: \mathbb{Z} \to\mathbb{N}$ is defined as $$ f(x)= \begin{cases} 2x-1, & \text{$x \gt 0$} \\ -2x, & \text{$x \le 0$} \end{cases} $$ one to one proof f is onto proof ...
-1
votes
1answer
29 views

Functions from $\{w,x,y,z\}$ to $\{a,b,c\}$

I'm having some problems understanding how functions and Big-O notation works... I've checked a couple of other threads here but still unsure Let's say I have $A = \{w, x, y, z\}$ and $B = \{a, b, ...
0
votes
0answers
37 views

What is the correct mathematical notation for a finite set?

My random variable $y$ belongs to a finite set of real numbers. I am writing a document and I need to write something like $y\in \mathbb{R}$. what should I put next to $\mathbb{R}$ which shows that ...
2
votes
0answers
53 views

Set Theory Notation: What does it mean to “\” one set with another? [duplicate]

What does the "\" operator mean in the above context?
2
votes
3answers
32 views

Elementary set theory notation verification

Reading Velleman's "How To Prove It" I came across the following expression: $$ x \in\bigcup\{\mathscr P(A)\mid A\in \mathcal F\} $$ such that $\mathcal F$ is a family of sets, $A$ is a set, and ...
2
votes
1answer
24 views

Show that $dim(X,\succeq)\leq |X^2|$ when $X$ is finite

I am trying to prove that when $(X,\succeq)$ is a finite preorder, the $dim(X,\succeq)\leq |X^2|$. Here's the full context (Exercise 11 (a)): My idea of resolution was to show that any set of ...
1
vote
1answer
26 views

Bringing ordinals to standard polynomial form

By the definition of multiplication and addition of ordinals, the following rules follow- Multiplication- $n\cdot\omega=\omega$ while $\omega\cdot n > \omega$ Addition- $n+\omega=\omega$ while ...