This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

2
votes
2answers
31 views

Opposite of a function being bijective?

A function is bijective if it is both surjective and injective. Is there a term for when a function is both not surjective and not injective?
0
votes
2answers
21 views

Can a surjective function have an element in the domain not mapped to the codomain?

I have seen a lot of definitions for surjectivity stating that every element in the codomain must be mapped to something in the domain. But does the opposite also have to hold true for a function to ...
3
votes
0answers
14 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
0
votes
2answers
44 views

Suppose A and B are finite sets and $f : A \rightarrow B$ is surjective. Is it possible that |A| < |B|?

I am trying to understand better what surjective functions is from a set $A$ to a set $B$, and from what I understood, it basically means this: A function is subjective (onto) from set $A$ to set ...
0
votes
1answer
19 views

Is $A∩B^c∩C^c = A-[A∩(B∪C)] $ ? (Set Theory)

I'm studying set operations. The example problem is: Find a simpler expression of $[(A∪B)∩(A∪C)∩(B^c∩C^c)]$ assuming all three sets intersect. The answer I came up with is $A∩B^c∩C^c$, while the ...
0
votes
2answers
40 views

can the empty set be an element of a group?

is the following group legal: $x = \{1,2,\emptyset\}$? If so, is $P(x) = \{ \emptyset, \{1\}, \{2\}, \{1,2\}, \{\emptyset\}, \{1, \emptyset\}, \{2,\emptyset\}, \{1,2,\emptyset\} \}$ ? When I write ...
3
votes
2answers
91 views

Confusion about the definition of function

Yesterday I was talking to one of my friends about the definition of function. The formal definition of function is given by Cartesian Products but my friend's question was whether it is possible to ...
2
votes
2answers
36 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
1
vote
1answer
32 views

What is the cardinality of the class of $0$ in $\mathbb{R}$?

What is the cardinality of the class of $0$ in $\mathbb{R}$? In other words: what is the cardinality of the class of all rational Cauchy sequences that converge to $0$?
4
votes
6answers
385 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
0
votes
2answers
32 views

Set theory and logic proof

Problem: Prove that if the sets $A,B,C \in U$, where $U$ is a universal set, then $A \cap B = A \cup B$ if and only if $A = B$ My attempt:We can show that $A \cap B = A \cup B$ if $A = B$ with the ...
3
votes
2answers
57 views

How do I prove that there doesn't exist a set whose power set is countable? [duplicate]

I don't even know where to begin on this one. Let $A$ be a countable set. In other words, $|A| = |\mathbb{N}|$. I'm trying to prove that there doesn't exist an $x$ such that $\mathcal{P}x = A$. ...
1
vote
2answers
50 views

How do I prove that for any set $A$, $|A| < |\mathbb{N}|$ implies that $A$ is finite?

Here's what I've tried so far. Let $A$ be a set and suppose $|A| < |\mathbb{N}|$. By the definition of less than for cardinalities (I'm reading out of Hrbacek's Introduction to Set Theory), this ...
3
votes
2answers
24 views

Given a set $A$, how do I prove that there exists a set of all sets $x$ such that $\bigcup x=A$?

I am working with Zermelo-Fraenkel axioms. Specifically, I am allowed to assume the Axiom of Pair, Axiom Schema of Comprehension, Axiom of Union, and Axiom of Power Set, etc. (not yet allowed to use ...
1
vote
1answer
28 views

Proof on $\bigcup A=\varnothing\Rightarrow\forall a\in A, a=\varnothing$

Is this proof valid? $\textbf{Claim: }\bigcup A=\varnothing\Rightarrow\forall a\in A, a=\varnothing$ Proof. Let us suppose that there was an $x\in A$ where $x\neq\varnothing$. Since $x\in \bigcup A ...
0
votes
3answers
47 views

How to come up with bijections?

Is there a good technique for finding bijections in general? Like between the integers and the natural numbers or between [0,1) and (0,1).
4
votes
2answers
41 views

example of uncountable set

I am looking for simple proofs of uncountable sets: I know a set is said to be uncountable if there is no injective function from the set to the natural numbers. I know the set of real numbers is ...
1
vote
1answer
31 views

Definiton of function

Are these two statements true about the definition of a function f from A into B For every element a in A, there exists at least one element b in B such that f(a)=b For every element a in A, there ...
2
votes
2answers
74 views

How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...
0
votes
1answer
29 views

Properties of infinity and Pi

Are the decimal points after Pi a countable infinity or uncountable? Can I just map the first decimal point to the first natural number and nth decimal to nth natural number?
1
vote
1answer
29 views

For all set A, B, and C if $(A \cap B) \cup C \subset A \cap (B \cup C)$ then $C \subset A$?

For all set A, B, and C if $(A \cap B) \cup C \subset A \cap (B \cup C)$ then $C \subset A$? Is this a theorem or a false proposition? Help!
1
vote
3answers
43 views

Is $g$ the unique function with this property?

Prove/Disprove: Let $A$ and $B$ be sets and let $f : A \to B$ be a function. If there is a function $g : B \to A$ such that $g\circ f = \operatorname{id}_A$, then $g$ is the unique function with this ...
0
votes
3answers
17 views

Proving a surjective function by given property

Suppose $f:E\rightarrow F$ and for any $A\subset F,A=f(f^{-1}(A))$. Show that f is surjective. What i have tried is $$\text{Let }y\in A $$ $$\{y\}\subset A$$ $$\{y\}= f(f^{-1}{\{y\})}$$ And i stuck ...
11
votes
4answers
917 views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change ...
4
votes
3answers
121 views

Munkres Section 10: How are these order types different?

Let $\mathbb{Z}^+$ denote the set of all positive integers in the usual order, let $n$ be a positve integer, and let the following sets have the dictionary order: $\{1, \ldots, n \} \times ...
0
votes
1answer
40 views

If a function from set $A$ to $B$ is one-to-one, is the function from $P(A)$ to $P(B)$ one-to-one as well?

If $f$ is a function from set $A$ to set $B$, define the function $S_f$ from $2^A$ to $2^B$ by $$S_f(X) = f(X)$$ for each subset $X$ of $A$. If a function $f$ from set $A$ to $B$ is one-to-one, is ...
0
votes
1answer
50 views

Construction of real numbes

How do I prove that the set of real numbers is the set of the power set of the set of natural numbers ? I can understand that the set of reals is uncountable and the set of Natural Numbers is ...
3
votes
0answers
32 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
2
votes
2answers
54 views

How are some infinities larger than other infinities

I heard an expressions, some infinities are larger than others recently, and they stated that it was proved to be so. I haven't been able to find this proof, and ...
0
votes
1answer
32 views

Prove that if $\: \forall_{t \in \mathbb{R}} \: \overline{\overline{A}}_t = c$ then $\overline{\overline{\bigcup_{t \in \mathbb{R}} \: A_t}} = c$

Prove that if $\: \forall_{t \in \mathbb{R}} \: \overline{\overline{A}}_t$ is equal to cardinality $c$, then $\:\overline{\overline{\bigcup_{t \in \mathbb{R}} \: A_t}}$ is also equal to cardinality ...
4
votes
2answers
45 views

Show that $A \subseteq B$ if and only if every subset of A is a subset of B.

Let $A$ and $B$ be sets. Show that $A \subseteq B$ if and only if every subset of $A$ is a subset of $B$. So I know I have to prove this in both directions but this is what I got so far: If if every ...
-2
votes
2answers
39 views

Relation on the set of all real numbers

I need a relation on $\mathbb R$ that is transitive and reflexive, not symmetric. should I just make sets $A,B$ with numbered elements and then create ordered pairs that fit the description?
2
votes
0answers
64 views

Counterexample to an implication

Denote $\bar{A}$ a complement of $A$ in a set $\Omega$ and $A \Delta B = A/B \cup B/A$ the symmetric difference of $A, B$. It is claimed that for a map $\phi := \Omega \rightarrow \lbrace 0, 1 ...
-1
votes
1answer
70 views

Set theory, really struglling, some REAL help please. :)

First I understand power sets. I understand that if we have the power set $X^Y$ such that $X = \{3,2\}$ and $Y = \{1,6\}$ then the power set contains 4 elements $f(3) = 1$, $f(2) = 1$...etc NOW onto ...
-1
votes
2answers
35 views

Equivalence relations and classes

Define an equivalence relation on ℝ. Determine the equivalence classes [0] and [1] according to the equivalence relation. relation R={(x,y)|x²=y²}=[w] For all x in Reals: ...
3
votes
5answers
86 views

Find a bijection from $\mathbb R$ to $\mathbb R-\mathbb N$

Find a bijection from $\mathbb R \to \mathbb R-\mathbb N$. I want to set my function up such that all natural numbers get mapped to $n+.1$ and reals of the form $n+.1$ to $2n+.1$ is this correct?
0
votes
1answer
34 views

Number of elements of the nth power set of the empty set?

Let n be a natural number find #℘ⁿ(∅) where ℘ⁿ means the n-th power set. I know that it has 2ⁿ where n is the number of elements. Other than this I don't know ...
1
vote
1answer
47 views

Relations on the set of Real Numbers

I need a relation on ℝ that is neither reflexive, nor symmetric, nor transitive. I thought of a ~ b where a=b²+1 (mostly) Not reflexive because: a² ≠ a² + 1 (mostly) Not ...
5
votes
3answers
40 views

Power set of Set differences

Assume that $\mathcal P(A-B)= \mathcal P(A)$. Prove that $A\cap B = \varnothing$. What I did: I tried proving this directly and I got stuck. Let $X$ represent a nonempty set, and let ...
1
vote
1answer
35 views

Is function $f$ also uniformly continuous?

I've been thinking on the following problem lately: Let $(X,d)$ be a metric space and $f_1,f_2,...,f_n: X \rightarrow \mathbb{R}$ and $f(x) = \max\{f_1(x),f_2(x),...,f_n(x) \}$,$x\in X$ If the ...
-7
votes
1answer
41 views

What can we say about the set $\cap U_i$? [on hold]

Let $U_1\supset U_2 \supset......$ be a decresing sequence of open sets in Euclidian 3 space $\mathbb R^3.$ What can we say about the set $\cap U_i$? A. It is infinite. B. It is ...
1
vote
2answers
34 views

An explicative definition of what is meant by $\{A_i\}_{i\in I}$?

What does $\{A_i\}_{i\in I}$ mean exactly? I know it's an index, but what exactly is that?
3
votes
2answers
65 views

logic and set theory proof : $|A \cap B| <|A^C|$

Prove that if $A$ and $B$ are sets then $|A \cap B| <|A^C|$. I'm not sure how I should start this proof. Normally I would turn the proof into set theory notation, but I'm not sure if that works or ...
1
vote
1answer
37 views

The cardinality of power set $2^A$ is strictly bigger then cardinality of a set $A$.

Actually the proof is obvious for finite sets. Because we can easily proof with induction. But it doesn't seem so for infinite ones. I know that there is a proof using diagonal argument and ...
0
votes
1answer
16 views

How to determine whether a given relation on a finite set is transitive?

On $R = \left \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(4,5),(5,5) \right \}$ Not reflexive because (3,3) and (4,4) are missing? Not symmetric because (2,1) ,(3,2), (4,3), (5,4) are missing? Not ...
1
vote
1answer
24 views

Prove that $[a]_X \subseteq [a]_Y$ .

Let $X,Y$ be two equivalence relations defined on a set $A.$ Show that $X \cup Y$ be the equivalence relation iff $[a]_X \subseteq [a]_Y$ (or $[a]_Y \subseteq [a]_X$). Here $[a]_{X(Y)}$ denotes the ...
0
votes
1answer
23 views

functions composition and surjective functions

Given $$(f◦g)(x)=x$$ (from R to R for any x in R) And $g(x)$ is onto! does it mean that also $$(g◦f)(x)=x$$ It seems like it does but how can I prove it?
0
votes
2answers
50 views

Is it possible to find the $n$th digit of $\pi$ (in base $10$)?

Is it possible that there exists some function $f:\mathbb N_1\to \{0,1,2,3,4,5,6,7,8,9\}$, where $$f(1)=\color{red}1, f(2)=\color{red}4, f(3)=\color{red}1, f(4)=\color{red}5, f(5)=\color{red}9, ...
2
votes
3answers
37 views

Proving if $A \subseteq B$ and $A \nsubseteq C$ then $B \nsubseteq C$

This is one of the problem I have been solving in Velleman's How to prove book: Prove that if $A \subseteq B$ and $A \nsubseteq C$ then $B \nsubseteq C$ This is my solution: Suppose $A ...
1
vote
1answer
23 views

Power set of the complement vs. complement of the power set [on hold]

So I can't figure out the way to proof this Power set of the complement vs. complement of the power set question. I tried proofing it using contrapositive but I couldn't get it. Let A and B be subsets ...