Questions tagged [elementary-set-theory]
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, differences and complements, De Morgan's laws, Venn diagrams, relations and functions, countability and uncountability, etc. More advanced topics should use (set-theory) instead.
27,468
questions
0
votes
0
answers
11
views
Existence and uniqueness of the equivalence closure
Given a relation $R \subseteq B \times B $, show the existence and uniqueness of the closure of R under the properties that define an equivalence relation. Does the order in which the closures of ...
0
votes
0
answers
7
views
Banach Decomposition Theorem from Fixpoint Theorem
Let $A$ be a set. Knowing that every monotone set function $F: \mathcal{P}(A)\to\mathcal{P}(A)$ (in the sense that $X\subseteq Y\subseteq A\implies F(X)\subseteq F(Y)$) has a fixpoint, prove the ...
- 41
0
votes
0
answers
21
views
Monotone set function in a set
Let $A$ be a set and let $F:\mathcal{P}(A)\to \mathcal{P}(A)$ a monotone function, i.e. if $X\subseteq Y\subseteq A$, then $F(X)\subseteq F(Y)$. Let $Z=\bigcup \{X\subseteq A|X\subseteq F(X)\}$. It ...
- 41
0
votes
1
answer
46
views
Understanding the Union Axiom. Proving $x \cup y := \{z: z\in x \lor z\in y\}$ is a set.
Hi guys I'm really new to set theory and I'm trying to well understand the Union Axiom.
First of all, the Union Axiom state the following (at least this is the definition I have):
$$\forall \,x\ \...
- 191
0
votes
1
answer
60
views
Is there a set of functions that span all "nice" functions?
I have been reading as to why there are elementary functions that have non-elementary antiderivatives and I have come to the conclusion that our notion of "elementary" functions is somewhat ...
- 521
1
vote
1
answer
36
views
If the Sets $A=\{x|x>4\ or\ x<0\}$, $B=\{x | ax-1>0\}$, and $A\cup B=A$, find the values of $a$.
Question:
If the Sets $A=\{x|x>4\ or\ x<0\}$, $B=\{x | ax-1>0\}$, and $A\cup B=A$, find the values of $a$.
My Working:
If $A\cup B=A$, then we have $B \subset A$.
If $B = \varnothing$, $ax-1\...
- 925
-2
votes
0
answers
58
views
order property vs. antisymmetric property
The definition of order property is well known:for a first-order theory $T$ the order property means that for some first-order formula $\phi(\bar{x},\bar{y})$ linearly orders in $M$ some infinite $\...
- 3,935
0
votes
1
answer
46
views
Image and preimage definition
I got the following very basic question:
Why is an image - in contrast to a preimage - defined by using the existential quantifier?
Let $f\colon A \to B$ be a mapping and $M$ a subset of $A$ and $N$ ...
- 3
1
vote
2
answers
96
views
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$ [closed]
For any sets $A, B, C$ within a universal $U$ set, prove that $A\cup B \subseteq C$ iff $(A \cup C)\cap (B \cup C) = U$
Confused on how to do this, any help would be great.
Correction: Accidentally ...
- 37
0
votes
1
answer
64
views
Indexed sets Prove $(\bigcap_iA_i)^c=\bigcup_i A_i^c $
Here i my approach. I stuggle to get the curly brackets in.
Attempt:
$\bigcup_i A_i^c=({x: \exists i \in I, x \in A_i})^c $
$={x: \exists i \in I, x \not \in A_i}$
How can I proceed here? I dont see ...
- 235
1
vote
0
answers
49
views
Finite tuples of infinite set
Let $U$ be an infinite set. Let $A$ be the set $U^{<\omega}$ of finite tuples of elements of $U$, i.e. $f\in A$ is of the form $(i_0,…,i_n)$ for $i_j\in U,j\leq n$, and $n\in \omega$.
Let $A\cup \{...
- 41
1
vote
0
answers
55
views
Show that a monotone function has a fixpoint
Let $F:\mathcal{P}(A)\to\mathcal{P}(A)$ be a monotone function, i.e. $X\subseteq Y\subseteq A$ implies $F(X)\subseteq F(Y)$. Show that it has a greatest fixpoint (i.e. a fixpoint $X$ such that for ...
- 41
2
votes
1
answer
28
views
Set notation iterating two variables over different lengths
How does one interpret the following set notation:
$$
\{(x_i,y_j): i=1,...,4,j=1,...,6\}
$$
- 23
3
votes
1
answer
94
views
Why is there no negative infinity in the extended complex plane?
I'm reading Ravi Agarwal's "Introduction to Complex Analysis". He says this:
It is often convenient to add the element $\infty$ to $\mathbb{C}$. The enlarged set
$\mathbb{C} \cup \{\infty\}$...
- 155
0
votes
0
answers
26
views
Real Analysis Set Theory Related Question
I have no idea what this set would be $$-A = \{ t \in \mathbb{R}: -t \in A \}$$. I'm thinking that it means it's all negative real numbers in the set $-A$. Furthermore, I don't know what $A$ would be.
1
vote
1
answer
31
views
Symmetric difference of a set and its n-th preimage
I have a question about the following statement:
Let $X$ be a set and $f:X\to X$ a map, then for any subset $A\subset X$ and all $n\in\mathbb{N}$
$$A\triangle f^{-n}(A)\subseteq\bigcup_{i=0}^{n-1}f^{-...
- 11
1
vote
0
answers
66
views
Possible Bijection Between Natural and Real Numbers [duplicate]
I'm studying the Cantor diagonal argument showing that there isn't any function $f:\mathbb N \to \mathbb R$ in one-to-one with each other and accepted it.
But, thinking about it for awhile, I thought ...
0
votes
1
answer
81
views
I’m very confused on why the writer says that his definitions (inverse, composite, etc) would be true for any “set”… [closed]
enter image description here
I’m very confused on why the writer says that his definitions (inverse, composite, etc) would be true for any “set”… as this would not be the case right? As only relations ...
0
votes
0
answers
30
views
List all the elements of $\{C \in \mathcal{P}(\{0,1,2\}) : \{0,1\} \nsubseteq C\}$.
I'm just really confused about what {0,1} not being contained in C would mean. Does it mean that the answer is all the elements of the powerset except for {0,1}, or does it mean the answer is all the ...
- 1
-3
votes
0
answers
79
views
I dont understand the writers confusing use of "Set" as opposed to a "Relation". [closed]
enter image description hereenter image description hereenter image description here
I dont understand the writers confusing use of "Set" as opposed to a "Relation". My only guess ...
- 1
0
votes
1
answer
35
views
Question about a proof that addition from the left preserves the order of ordinals
I found the following proof that ordinal addition from the left preserves strict inequalities (see b)).
I am having trouble understanding the limit stage. The proof uses the inequality
$\gamma + \...
- 975
-4
votes
0
answers
27
views
I have tried proving this but I still couldn't get it [closed]
I was given two distinct sets, A and B. If A is a subset of B, prove that B is not a subset of A and that A is not equal to B.
1
vote
0
answers
38
views
Confusion on Authors use of the word into as opposed to onto
The function G, which is a mapping of B -> A by the definition in the screenshot should be a mapping from B onto A because all members of B would always mapped to A Right?
- 21
0
votes
1
answer
17
views
What type of relation wrt arbitrary elements of a generic set exists between particular (distinct, not-nec unique) elements of that set?
What type of relation wrt ane arbitrary element of a generic (ostensibly non‑ordered) set exists between particular (distinct, not necessarily unique) elements of that set? I.e.(e.g.): $𝑥∈\{𝚡₁,…,𝚡...
1
vote
2
answers
23
views
Proving by induction how many elements are in the $n$-ary cartesian product between the two same sets.
Here's a question that has been bugging me for a while.
Let $A$ be a set such that $A = \{a, b\}$. Then, $A_1 = A$, $\;A_2 = A \times A$, and for $n \in \mathbb{N}$, $A_n = A_{n-1} \times A$. How ...
- 33
1
vote
0
answers
42
views
Prove $A^c \setminus B^c=B \setminus A$ [duplicate]
Prove $A^c \setminus B^c=B \setminus A$
Attempt:
let $A^c = \{ x:x \in U, x \not \in A\}$ and let $B^c = \{ x:x \in U, x \not \in B\}$ and $ B \setminus A =\{x:x \in B, x \not \in A\}$
Dont know how ...
- 235
0
votes
1
answer
53
views
What are the basics for notation used in cardinal arithmetic?
If $S$ and $T$ are sets, which of the following would you say is $T^{S}$?
$T^{S}$ is the set of all functions from $S$ to $T$.
$T^{S}$ is the Cartesian product of $T$ taken $\begin{vmatrix} S \end{...
- 919
1
vote
0
answers
17
views
Possible errors in a proof concerned with irreflexivity and asymmetry
I'm trying to prove that asymmetric relation R would also be irreflexive. My proof is as follows:
Suppose R is not irreflexive. Then a is related to a by R for some a. Then either a is not related to ...
- 43
1
vote
1
answer
39
views
$S$ is any non empty set and $2^S$ is the power set of $S$. True or False for the following
$S$ is any non empty set and $2^S$ is the power set of $S$.
let $S = \{ 1,2 \}$. Then the power set $P(S) = \{\{1,2\}, \{1\}, \{2\}, \emptyset \}$ where P(S) contains $2^2=4$ elements.
True or False ...
- 235
3
votes
2
answers
47
views
Prove or disprove. $\bigcup_{i\in I} \bigcap_{j\in J} C_{i,j} = \bigcap_{j\in J} \bigcup_{i\in I} C_{i,j}.$ [duplicate]
Let $\{ C_{i,j} : i\in I \text{ and } j\in J \}$ be a family of sets. Assume the set $I$ (of indices $i$) is arbitrary, non-empty, and non-enumerable. Similarly, assume the set $J$ (of indices $j$) is ...
- 14k
0
votes
0
answers
21
views
Notation regarding a set with two disjoint properties
I'm trying to write the solution to the following equation in set builder notation
$$\max\{|x_1|,|x_2| \}=1$$ So far, I've come up with:
$$\big\{ (x_1,x_2) \in \mathbb{R}^2: \big(|x_1|=1, -1\le x_2 \...
1
vote
0
answers
28
views
How to think about distence or closeness between various intersecting and non-intersecting sets?
Edit: I want to add more context. I'm interested in toying around with mathematical modeling of something, where it is helpful to represent the things I'm modeling with sets whose elements are points. ...
- 87
1
vote
1
answer
26
views
Give an example of a relation $R$ on the given set $A$ that has the properties described: $A=\mathbb Q$, $R$ is both symmetric and anti-symmetric
$A=\mathbb Q$, $R$ is both symmetric and anti-symmetric
What I have is "$R = \{(a, b)~ |~ a, b \in \mathbb Q~ ,~ a = b\}$". I just want to double check if my logic is correct and if not, ...
- 13
1
vote
0
answers
38
views
For any three relations prove the $ (T \circ S) \circ R = T \circ (S \circ R) $ [duplicate]
Prove: For any three relations $R \subset W \times X$, $S \subset X \times Y$, and $T \subset Y \times Z$, $(T \circ S) \circ R = T \circ (S \circ R)$.
(image link)
Attempted Proof: suppose $ (a,b) ...
- 235
0
votes
0
answers
37
views
Notation: x randomly chosen with weights from set S
I have implemented $\epsilon$-greedy policy in the context of reinforcement learning in Python code:
...
- 1
0
votes
1
answer
54
views
composition relations in Set Theory
I have provided my solution and I see there are subtle differences to those provide in picture. Is my solution equivalent? Which is more rigorously correct?
\begin{align}
(S \circ R)^{-1} & = \...
- 235
1
vote
0
answers
46
views
Kuratowski's definition of ordered pairs: proving $(x,y) = (u,v) \iff x=u \text{ and } y=v$
I'm new to set theory and I need to prove the following:
$(x,y) = (u,v) \iff x=u,y=v$ where $(x,y) = \{\{x\},\{x,y\}\}$ as in Kuratowski's definition of ordered pairs.
Now, I think I got the right to ...
- 191
0
votes
0
answers
23
views
$\overline{F}:A/R\to A/R$ such that $\overline{F}([x]_R)=[F(x)]_R$ uniqueness extremely trivial im confused?
Assume that $R$ is an equivalence relation on $A$ and that $F:A\to A$. If $F$ is compatible with $R$, then there exists a unique $\overline{F}:A/R\to A/R$ such that $$\overline{F}([x]_R)=[F(x)]_R$$
...
- 170
3
votes
1
answer
297
views
Is this exercise from Tao's Analysis 1 erroneous?
On page 68 of the fourth edition of Tao's Analysis 1, is Exercise $3.5.12$, the first part of which I believe is erroneous. The exercise is stated as follows:
(Note: $n++$ refers to the successor of $...
- 435
0
votes
0
answers
39
views
Injective function from N (naturals) to Q?
In this video (https://www.youtube.com/watch?v=Vp570S6Plt8) at 11:17, the speaker says that their argument proves that the size of infinity of Q is less than the size of infinity of N. This makes ...
- 1
1
vote
1
answer
35
views
Resources for "Bell Machover"
Recently, I've been reading through A Course In Mathematical Logic by John Bell and Moshé Machover. However, it's not always the easiest book to understand. What might be some good supplements to have ...
- 91
0
votes
1
answer
30
views
Proving $C = \{ x \in \mathbb R^n\colon Ax = b\}$is closed, for some $A \in \mathbb R^{m \times n}$ and $b \in \mathbb R^m$ s.t. system is feasible.
Consider the set
$$ C = \{ x \in \mathbb R^n\colon Ax = b \}, $$
where $A$ is some matrix in $\mathbb R^{m \times n}$ and $b \in \mathbb R^m$ such that the system is feasible. I aim to prove such set ...
- 1,171
1
vote
1
answer
26
views
Sets that are half-satisfied
Let $S=\{1,2,\dots,n\}$ and $A_1,\dots,A_k\subseteq S$. Assume that, among the sets $A_i$'s, $1$ appears as least as frequently as $2$, which appears as least as frequently as $3$, etc.
Let $B = \{2,4,...
- 2,587
0
votes
0
answers
50
views
is there a function $f: \mathbb{Q} \rightarrow \mathbb{N}$ that is surjective but not injective?
I would like to know, is there a function
$$f: \mathbb{Q} \rightarrow \mathbb{N}$$
that is surjective but not injective?
I am rather new to the principle of cardinality. I know that $\mathbb{Q}$ has ...
- 19
1
vote
1
answer
43
views
The geometric realisation $|\Gamma|_I$ of a graph $(\Gamma, I)$
Prove that the geometric realisation $|\Gamma|_I$ of a graph $(\Gamma, I)$ is the topological space $$|\Gamma|_I = E\times [0,1]\vert \sim$$where $\sim$ is the equivalence relation generated by the ...
- 85
1
vote
0
answers
32
views
Using theorem to prove a collection $\left \{ x:\phi (x) \right \}$ is not set.
As I was reading Set Theory: A First Course, I encountered a theorem in the page 31 that allows to prove if a given class $\left \{ x:\phi (x) \right \}$ is a set. It goes as follows:
Theorem 2.1.3 ...
- 43
1
vote
1
answer
33
views
Is it true that $x (\bigcap\limits_{\alpha \in A} T_\alpha) \neq \bigcap_{\alpha \in A} (x T_\alpha)$?
I want to show that the intersection of normal subgroups are normal subgroup in direct way.
It means that if $T_\alpha$'s are normal subgroups of a group $G$, then I want to show that
$$x (\bigcap\...
- 1,183
0
votes
2
answers
34
views
Transitive, Symmetric and Antisymmetric for relations.
Determining whether a relation is reflexive is straightforward, as it is for symmetric and transitive.
But considering how strict the criteria, does it mean that any relation that simply fails the (P) ...
- 55
1
vote
2
answers
203
views
How to use $\uparrow$ to define an explicit bijective mapping $f:\varepsilon_{1}\rightarrow\mathbb{N}$?
The map $f:\varepsilon_{1}\rightarrow\mathbb{N}$ which I am trying to define has to send $\varepsilon_{0}$ to some natural number. Since $\varepsilon_{0}=\omega\uparrow^{2}\omega$, a potential ...
- 3,484
1
vote
1
answer
55
views
Does there exist a group $G$ with a proper subgroup $K$ in which for all $a, b \in G - K$ such that $ab \neq e$, we have $ab \in G - K$? [closed]
I am currently studying group theory and I asked myself various questions, though I was able to solve almost all of them, I could not answer the following one:
Does there exist a group $G$ with a ...
- 145